Grant: Discovery Grants Program - Individual
University of Waterloo
$26,000.00
Preconditioning for linear systems arising in modeling and optimization
FY 2009-10
Summary
A central problem in scientific computing is the solution of large systems of linear equations. Linear equations arise as a subproblem in practically every branch of computational science and engineering, including solid mechanics, fluid mechanics, electromagnetics, astrophysics, chemistry, solid and high energy physics, as well as in all manner of optimization and statistical problems. Problems as disparate as designing automobile or aircraft engines, scheduling work crews at a large company, or developing next-generation imaging devices all require solving linear equations. Indeed, for many of these problems, solving linear equations is the most computationally intensive step.
Since the 1970s, asymptotic considerations have increasingly favored iterative methods for solving very large linear systems. The key to efficiency of iterative methods is the selection of a good preconditioner. A preconditioner is defined as a matrix that approximates the system under consideration and yet is easy to solve.
In our previous work with graduate students and colleagues, we have discovered several new families of preconditioner, the most recent and perhaps most exciting being based on underlying graph structure (i.e., information about how the variables underlying the scientific problem are interconnected). I propose to develop novel methods for preconditioning for many applications in optimization and scientific modeling. I also plan to apply these preconditioners to practical scientific problems.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
341718-2007
Name nom
Vavasis, Stephen
Department département
Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2009
Competition year année de concours
2007
Award amount
26000
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
405
Area of application group en
Environment
Area of application group fr
Environnement
Area of application en
Modelling and mathematical simulation of natural processes
Area of application fr
Modélisation et simulation mathématique des processus naturels
Research subject code
2715
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Optimization
Research subject fr
Optimisation
Partie
3
Nb partie
5
Application title
Preconditioning for linear systems arising in modeling and optimization
Keyword
NA
Application summary
A central problem in scientific computing is the solution of large systems of linear equations. Linear equations arise as a subproblem in practically every branch of computational science and engineering, including solid mechanics, fluid mechanics, electromagnetics, astrophysics, chemistry, solid and high energy physics, as well as in all manner of optimization and statistical problems. Problems as disparate as designing automobile or aircraft engines, scheduling work crews at a large company, or developing next-generation imaging devices all require solving linear equations. Indeed, for many of these problems, solving linear equations is the most computationally intensive step.
Since the 1970s, asymptotic considerations have increasingly favored iterative methods for solving very large linear systems. The key to efficiency of iterative methods is the selection of a good preconditioner. A preconditioner is defined as a matrix that approximates the system under consideration and yet is easy to solve.
In our previous work with graduate students and colleagues, we have discovered several new families of preconditioner, the most recent and perhaps most exciting being based on underlying graph structure (i.e., information about how the variables underlying the scientific problem are interconnected). I propose to develop novel methods for preconditioning for many applications in optimization and scientific modeling. I also plan to apply these preconditioners to practical scientific problems.