Grant: Discovery Grants Program - Individual
University of Waterloo
$32,000.00
Sparsity, complexity and practicality in symbolic mathematical computation
FY 2011-12
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 three specific areas: solving sparse linear equations with exact rational numbers as entries, algorithms for approximate or ""noisy"" polynomials, and computing with ""lacunary"" polynomials (polynomials with high degree but only a few non-zero terms). The 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.
As an example, a system of thousands of simultaneous equations, where each equation involves only three variables, should be solvable more quickly than a system where each equation involves thousands of variables. Our algorithms and software will allow us to treat the enormous and sparse equations that now challenge us in symbolic mathematical computation and its applications. I will also consider ""approximate"" equations, where some of the data involved may be imprecise or noisy (say from experimental data). I will show how to reconstruct equations to model such data which are of small size, thus making subsequent operations faster. Finally, I will explore the exciting theoretical world of ""super sparse"" or lacunary polynomials. Computing with these pushes the limits of algorithmic science, but also may lead to useful methods in practice.
The algorithmic advances will be implemented in the symbolic linear algebra software library LinBox and in the computer algebra system Maple. Both provide an avenue for broad dissemination of our methods.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
155376-2008
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
2011
Competition year année de concours
2008
Award amount
32000
Program id
RGPIN
Program nane 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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
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
4
Nb partie
5
Application title
Sparsity, complexity and practicality in symbolic mathematical 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. 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 three specific areas: solving sparse linear equations with exact rational numbers as entries, algorithms for approximate or ""noisy"" polynomials, and computing with ""lacunary"" polynomials (polynomials with high degree but only a few non-zero terms). The 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.
As an example, a system of thousands of simultaneous equations, where each equation involves only three variables, should be solvable more quickly than a system where each equation involves thousands of variables. Our algorithms and software will allow us to treat the enormous and sparse equations that now challenge us in symbolic mathematical computation and its applications. I will also consider ""approximate"" equations, where some of the data involved may be imprecise or noisy (say from experimental data). I will show how to reconstruct equations to model such data which are of small size, thus making subsequent operations faster. Finally, I will explore the exciting theoretical world of ""super sparse"" or lacunary polynomials. Computing with these pushes the limits of algorithmic science, but also may lead to useful methods in practice.
The algorithmic advances will be implemented in the symbolic linear algebra software library LinBox and in the computer algebra system Maple. Both provide an avenue for broad dissemination of our methods.