Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Simon Fraser University

$96,000.00

Fast Algorithms and Libraries for Polynomials.

EF 2023-24

Résumé
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.
Programme
Discovery Grants Program - Individual
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2019-04441
Name nom
Monagan, Michael
Department département
Mathematics - Mathematics
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2019
Award amount
96000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2705
Research subject group en
Information technology
Research subject group fr
Software and development
Research subject en
Technologie de l'information
Research subject fr
Logiciels et développement
Application title
Fast Algorithms and Libraries for Polynomials.
Keyword
Computer Algebra; Computer Algebra Systems; High Performance Computing; Maple, Magma; Multivariate Polynomial Factorization; Multivariate Polynomial Greatest Common Divisors; Parallel Algorithms; Sparse Multivariate Polynomial Interpolation
Application summary
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.