Fast Algorithms and Libraries for 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.