Fast Algorithms and Libraries for Polynomials.

多项式的快速算法和库。

• 批准号: RGPIN-2019-04441
• 负责人: Monagan, Michael
• 金额: $ 3.5万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=714020
• 关键词: Fast; Algorithms; Libraries; Polynomials.

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.

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