Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$41,000.00

Efficiency, Structure and Robustness in Algebraic Computation

EF 2018-19

Résumé
This proposal describes a comprehensive program of research into the design, analysis and implementation of algorithms for foundational problems in symbolic mathematical computation. My work will both explore fundamental scientific problems and allow commercial software like Maple and Mathematica to address new applications at a scale beyond their current reach. It will allow computers 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 three specific areas: algorithms for sparse polynomials, symbolic and exact linear algebra with sparse matrices, and symbolic-numeric algorithms for approximate polynomials and matrices. A common thread in my projects is a focus on exploiting sparsity (many zeros or gaps in the descriptions of data) and succinct representations. We will develop faster methods to solve key mathematical problems with sparse data representations, explore the underlying computational complexities, and provide fast implementations which can be applied to huge problem instances arising in data science, cryptography and control systems.*Polynomials are a key tool for describing simple but fundamental mathematical functions. Discovering sparse representations, where terms with a coefficient of zero are not represented, is the classical problem of sparse interpolation. Methods have been known for 300 years, but there is still much room for improvement. Other operations with sparse polynomials such as factorization and decomposition live on the frontier of what is practical and what is intractable. Our goal is to reduce costs for sparse interpolation to near optimal, and to design efficient algorithms for manipulating sparse polynomials.*Methods for finding exact solutions to huge systems of sparse linear equations are becoming central tools for symbolic computation, and many applications are now reduced to this. We will seek new algorithms that are provably faster than any previously known, for both solving systems and classifying all possible solutions through diagonalization (Smith form).*We will address symbolic-numeric problems, allowing for inexact data and solutions in sparse interpolation and linear systems of polynomial equations. We will combine modern computer algebra methods with recent advances in sparse reconstruction and optimization to achieve faster and provably robust algorithms for problems at the nexus of scientific computing and computational algebra. *I will continue my record over the past decade of training exceptionally talented and highly qualified personnel at the Master's and PhD level, who go on to top-level positions in academia and industry. Our 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.
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2018-04950
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
2018
Competition year année de concours
2018
Award amount
41000
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
802
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
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
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
1
Nb partie
5
Application title
Efficiency, Structure and Robustness in Algebraic Computation
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. My work will both explore fundamental scientific problems and allow commercial software like Maple and Mathematica to address new applications at a scale beyond their current reach. It will allow computers 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 three specific areas: algorithms for sparse polynomials, symbolic and exact linear algebra with sparse matrices, and symbolic-numeric algorithms for approximate polynomials and matrices. A common thread in my projects is a focus on exploiting sparsity (many zeros or gaps in the descriptions of data) and succinct representations. We will develop faster methods to solve key mathematical problems with sparse data representations, explore the underlying computational complexities, and provide fast implementations which can be applied to huge problem instances arising in data science, cryptography and control systems.*Polynomials are a key tool for describing simple but fundamental mathematical functions. Discovering sparse representations, where terms with a coefficient of zero are not represented, is the classical problem of sparse interpolation. Methods have been known for 300 years, but there is still much room for improvement. Other operations with sparse polynomials such as factorization and decomposition live on the frontier of what is practical and what is intractable. Our goal is to reduce costs for sparse interpolation to near optimal, and to design efficient algorithms for manipulating sparse polynomials.*Methods for finding exact solutions to huge systems of sparse linear equations are becoming central tools for symbolic computation, and many applications are now reduced to this. We will seek new algorithms that are provably faster than any previously known, for both solving systems and classifying all possible solutions through diagonalization (Smith form).*We will address symbolic-numeric problems, allowing for inexact data and solutions in sparse interpolation and linear systems of polynomial equations. We will combine modern computer algebra methods with recent advances in sparse reconstruction and optimization to achieve faster and provably robust algorithms for problems at the nexus of scientific computing and computational algebra. *I will continue my record over the past decade of training exceptionally talented and highly qualified personnel at the Master's and PhD level, who go on to top-level positions in academia and industry. Our 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.