Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Simon Fraser University

$48,000.00

Fast Algorithms and Libraries for Polynomials.

FY 2022-23

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.
Program
Discovery Grants Program - Individual
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

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
2022
Competition year année de concours
2019
Award amount
48000
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
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Installment
inst:4
Partie
1
Nb partie
5
Application title
Fast Algorithms and Libraries for Polynomials.
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.
Simon Fraser University - $48,000 Grant (2022-23) | Canada Spends