Fast Algorithms and Libraries for Polynomials.

多项式的快速算法和库。

• 批准号: RGPIN-2019-04441
• 负责人: Monagan, Michael
• 金额: $ 3.5万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=689683
• 关键词: 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，Mathematica，Magma和Sage，是用于进行涉及公式和数字的数学计算的大型计算机程序。 工业界和学术界的科学家和工程师使用这些程序来解决涉及大型公式的数学问题，这些公式无法用手轻松完成。本研究计划集中于计算机代数系统所做的三个中心计算，即 **（1）计算多项式的多项式最大公约数（GCD）在许多变量具有不同种类的系数。GCD用于简化涉及分数的公式。 在许多应用程序中，计算GCD是最耗时的部分。 研究的重点是多项式，其中有代数数，如sqrt（2）和代数函数，如sqrt（t）存在。(2)开发多变量多项式因式分解的快速算法。因式分解多项式是在涉及公式的许多计算中使用的关键工具。我们已经找到了一种新的方法，我们认为这将使我们能够开发出一种快速的并行算法。(3)研究并改进了求解多项式方程组的狄克逊结式法。 这种方法包括构造一个多项式矩阵并计算其行列式。我们要使用的工具是稀疏多项式插值。研究的另一个方面是开发和实现充分利用现代硬件能力的并行算法。 今天，现代计算机通常具有4个或更多个处理器（核心）。 在每个处理器中，有一个向量处理器，它基本上是一个迷你并行处理器，可以一次执行4个算术运算。因此，一台典型的计算机可以同时进行16个或更多的操作。该研究旨在建立一个多变量多项式计算工具库，可以利用这种并行计算能力，并使用这些工具来加速（1），（2）和（3）中的计算。除了在科学会议上与其他人交流研究结果外，我们计划通过将其集成到Maple计算机代数系统和/或将其作为开源库提供，使我们开发的最佳软件可供任何想要使用它的人使用。 Maplesoft是开发Maple的公司，总部位于安大略滑铁卢。*