Fast Algorithms and Libraries for Polynomials.

计算机代数系统，如Maple、数学、Magma和Sage，都是大型计算机程序，用于进行涉及公式和数字的数学计算。工业界和学术界的科学家和工程师使用这些程序来解决数学问题，这些问题涉及手工难以完成的大公式。*本研究方案集中在计算机代数系统所做的三项中心计算，即*(1)计算具有不同系数的多变量多项式的多项式最大公约数(GCDS)。GCD用于简化涉及分数的公式。在许多应用中，计算GCDS是最耗时的部分。研究的重点是具有像SQRT(2)这样的代数数和像SQRT(T)这样的代数函数的多项式。*(2)开发更快的多元多项式因式分解算法。分解多项式是许多涉及公式的计算中使用的关键工具。我们发现了一种新的方法，我们认为这将使我们能够开发一种快速的并行算法。(3)研究和改进用于求解(多项式)方程组的Dixon结式方法。这种方法包括构造多项式矩阵和计算其行列式。我们将要使用的工具是稀疏多项式插值。*研究的另一个方面是开发和实现充分利用现代硬件能力的并行算法。今天，现代计算机通常有4个或更多的处理器(核心)。在每个处理器中，有一个向量处理器，它基本上是一个小型并行处理器，一次可以做4次算术运算。因此，一台典型的计算机可以同时进行16次或更多的操作。这项研究的目的是建立一个工具库，用于计算多元多项式，可以利用这种并行计算能力，并使用这些工具来加快(1)、(2)和(3)的计算速度。*除了在科学会议上与其他人交流研究结果外，我们计划通过将我们开发的最好的软件集成到Maple计算机代数系统和/或将其作为开放源代码库提供给任何想要使用它的人。Maplesoft是开发Maple的公司，总部设在安大略省滑铁卢。

Computer Algebra Systems, like Maple, Mathematica, Magma and Sage, are large computer programs for doing mathematical calculations involving formulas as well as numbers. Scientists and engineers in industry and academia use these programs for solving mathematical problems which involve large formulas that cannot easily be done by hand.******This research proposal focuses on three central computations that Computer Algebra Systems do, namely******(1) Computing polynomial greatest common divisors (GCDs) for polynomials in many variables with different kinds of coefficients. GCDs are used to simplify formulas which involve fractions. In many applications computing GCDs is the most time consuming part. The research focuses on polynomials which have algebraic numbers like the sqrt(2) and algebraic functions like sqrt(t) present.******(2) Developing faster algorithms for factoring polynomials in many variables. Factoring polynomials is a key tool used in many calculations involving formulas. We have found a new approach which we think will enable us to develop a fast parallel algorithm.******(3) Studying and improving the Dixon resultant method which is used to solve a system of (polynomial) equations. This method involves constructing a matrix of polynomials and computing its determinant. The tool we are going to use to do this is sparse polynomial interpolation.******Another aspect of the research is to develop and implement parallel algorithms that fully utilize modern hardware capabilities. Today, modern computers have typically 4 or more processors (cores). Within each processor, there is a vector processor, which is basically a mini parallel processor that can do 4 arithmetic operations at a time. Thus a typical computer can do 16 or more operations simultaneously. The research aims to build a library of tools for computing with polynomials in many variables which can take advantage of this parallel computing capability and use those tools to speed up the computations in (1), (2) and (3).******In addition to communicating the research results with others at scientific conferences, we plan to make the best software that we develop accessible to anyone who wants to use it by either integrating it into the Maple Computer Algebra System and/or making it available as an open source library. Maplesoft, the company that develops Maple, is based in Waterloo Ontario.*****