Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$36,000.00

High Performance Algorithms for Sparse and Structured Symbolic Computations

FY 2015-16

Summary
This proposal describes a comprehensive program of research into the design, analysis and implementation of algorithms for foundational problems in symbolic mathematical computation. These are the algorithms that make commercial mathematical software like Maple and Mathematica run. They allow us to manipulate and solve large and complex sets of equations exactly, even when some quantities are unknown and left as variables. My research will centre on four specific areas: algorithms for sparse polynomials, approximate polynomial computation, symbolic sparse linear algebra, and algorithms for matrices of differential and difference operators. A common thread of the described projects is a focus on exploiting sparsity, the existence of lots of zeros or ""holes"". In other words, if a very large problem we wish to solve has a very succinct description, we want to use this to make our algorithms run more quickly. Our algorithms and software will help computers treat the enormous equations that now challenge us in symbolic mathematical computation and its many applications. They will allow us to handle noisy and approximate data in a robust and verifiable way, and to discover and represent the underlying structure. And they will extend the reach of symbolic computing software, like Maple, to address the most difficult and important industrial, scientific and mathematical problems. The projects all involve extensive collaboration and training of students for future positions in academia and industry. The algorithmic advances will be published in top scientific venues and implemented in symbolic algebra software such as Maple, SAGE and LinBox, and will be openly available for all.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
155376-2013
Name nom
Giesbrecht, Mark
Department département
Computer Science, David R. Cheriton School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2013
Award amount
36000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à 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
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
Partie
3
Nb partie
5
Application title
High Performance Algorithms for Sparse and Structured Symbolic Computations
Keyword
NSERC
Application summary
This proposal describes a comprehensive program of research into the design, analysis and implementation of algorithms for foundational problems in symbolic mathematical computation. These are the algorithms that make commercial mathematical software like Maple and Mathematica run. They allow us to manipulate and solve large and complex sets of equations exactly, even when some quantities are unknown and left as variables. My research will centre on four specific areas: algorithms for sparse polynomials, approximate polynomial computation, symbolic sparse linear algebra, and algorithms for matrices of differential and difference operators. A common thread of the described projects is a focus on exploiting sparsity, the existence of lots of zeros or ""holes"". In other words, if a very large problem we wish to solve has a very succinct description, we want to use this to make our algorithms run more quickly. Our algorithms and software will help computers treat the enormous equations that now challenge us in symbolic mathematical computation and its many applications. They will allow us to handle noisy and approximate data in a robust and verifiable way, and to discover and represent the underlying structure. And they will extend the reach of symbolic computing software, like Maple, to address the most difficult and important industrial, scientific and mathematical problems. The projects all involve extensive collaboration and training of students for future positions in academia and industry. The algorithmic advances will be published in top scientific venues and implemented in symbolic algebra software such as Maple, SAGE and LinBox, and will be openly available for all.