Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$52,000.00

New and efficient algorithms for computer algebra

FY 2024-25

Summary
My long-term goals are to design, analyse and implement algorithms for solving, in an exact manner, important mathematical problems. The main objectives of this proposal are coming from real algebraic geometry (inspired by motion planning) and number theory (computational aspects of Drinfeld modules); see items 4 and 5 below. To solve these high-level questions, some intermediate problems will be considered. They address fundamental operations in computer algebra, and are important in their own right; these are items 1-3. 1. Modular composition. Many questions with polynomials in one or two variables admit efficient solutions (e.g., polynomial multiplication or division), but this is not the case for modular composition: given polynomials f, g and h, this computes the remainder f(g) mod h. The first objective is to develop and implement efficient algorithms for modular composition in one or two variables. Apart from applications (e.g., to field arithmetics), this will play a role in items 2 and 5 below. 2. Polynomials in two variables. The second objective is to develop efficient algorithms for solving polynomial equations in two variables. They are of high interest in computer aided design; within this proposal, they play a part in the objectives described in items 4 and 5. 3. Determinantal systems of equations. The third intermediate objective is to give algorithms to solve the following kind of problem: given equations f1,..,fs, together with a matrix M with polynomial entries, describe all points at which all equations vanish, and where M has a prescribed rank. The algorithm described in item 4 rest heavily on this operation; beyond the framework of this proposal, solving determinantal systems also has applications in optimisation or cryptology. 4. Real algebraic geometry. Algorithms in real geometry are one of the main objectives in this proposal. Typical questions are whether two points in a configuration space can be continuously connected, or how many connected components there are. Roadmaps are a cornerstone of algorithms for such questions: these are curves traced on our configuration space, which connect the starting point to the destination. My objective is to contribute improved algorithms for computing and using roadmaps, using the results on bivariate and determinantal systems from items 2 and 3. 5. Algorithmic aspects of Drinfeld modules. Drinfeld modules are algebraic constructions dating from the 1970s, whose theory shows a striking similarity with that of elliptic curves. There is a growing interest for algorithms for Drinfeld modules; my last objective is developing their algorithmic toolkit, using results on modular composition and bivariate polynomials from items 1 and 2. All items in this proposal involve HQP training, at the Masters and PhD levels. Trainees will grow their algorithmic and mathematical skills and contribute to software implementation, allowing them to find positions in academia or the ICT sector.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2023-03463
Name nom
Schost, Eric
Department département
Cheriton School of Computer Science
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2023
Award amount
52000
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
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2714
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Mathematics of computing
Research subject fr
Mathématiques de l'informatique
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
New and efficient algorithms for computer algebra
Keywords
computer algebra; algorithm design; complexity; systems of polynomial equations; real algebraic geometry
Application summary
My long-term goals are to design, analyse and implement algorithms for solving, in an exact manner, important mathematical problems. The main objectives of this proposal are coming from real algebraic geometry (inspired by motion planning) and number theory (computational aspects of Drinfeld modules); see items 4 and 5 below. To solve these high-level questions, some intermediate problems will be considered. They address fundamental operations in computer algebra, and are important in their own right; these are items 1-3. 1. Modular composition. Many questions with polynomials in one or two variables admit efficient solutions (e.g., polynomial multiplication or division), but this is not the case for modular composition: given polynomials f, g and h, this computes the remainder f(g) mod h. The first objective is to develop and implement efficient algorithms for modular composition in one or two variables. Apart from applications (e.g., to field arithmetics), this will play a role in items 2 and 5 below. 2. Polynomials in two variables. The second objective is to develop efficient algorithms for solving polynomial equations in two variables. They are of high interest in computer aided design; within this proposal, they play a part in the objectives described in items 4 and 5. 3. Determinantal systems of equations. The third intermediate objective is to give algorithms to solve the following kind of problem: given equations f1,..,fs, together with a matrix M with polynomial entries, describe all points at which all equations vanish, and where M has a prescribed rank. The algorithm described in item 4 rest heavily on this operation; beyond the framework of this proposal, solving determinantal systems also has applications in optimisation or cryptology. 4. Real algebraic geometry. Algorithms in real geometry are one of the main objectives in this proposal. Typical questions are whether two points in a configuration space can be continuously connected, or how many connected components there are. Roadmaps are a cornerstone of algorithms for such questions: these are curves traced on our configuration space, which connect the starting point to the destination. My objective is to contribute improved algorithms for computing and using roadmaps, using the results on bivariate and determinantal systems from items 2 and 3. 5. Algorithmic aspects of Drinfeld modules. Drinfeld modules are algebraic constructions dating from the 1970s, whose theory shows a striking similarity with that of elliptic curves. There is a growing interest for algorithms for Drinfeld modules; my last objective is developing their algorithmic toolkit, using results on modular composition and bivariate polynomials from items 1 and 2. All items in this proposal involve HQP training, at the Masters and PhD levels. Trainees will grow their algorithmic and mathematical skills and contribute to software implementation, allowing them to find positions in academia or the ICT sector.