Grant: Discovery Grants Program - Individual
University of Waterloo
$25,000.00
Multilevel methods for scientific computing
FY 2010-11
Summary
This project develops new computer algorithms of 'divide-and-conquer'-type for two important scientific computing applications. The algorithms are made efficient by exploiting representations of the problems on multiple levels with successively coarser resolution.
The first problem deals with the organization and retrieval of large amounts of information, for instance the importance ranking of web pages for search engine queries. Efficient multilevel methods will be derived for so-called Markov chain problems, which provide a model for importance ranking.
The second problem deals with the simulation of highly nonlinear systems of equations, for example models of complex fluid flow around airplanes or in planetary atmospheres. Efficient multilevel methods will be developed for these nonlinear systems, by explicitly isolating the nonlinear singularities from the smooth part of the solution.
The multilevel algorithms to be developed proceed in an iterative way by improving an initial guess of the problem solution over successive cycles. The improvements in each cycle are made efficient by reducing error components with different scales on appropriate progressively coarser levels in a recursive way. This approach can lead to a speedup of several orders of magnitude, compared with more conventional methods.
The dramatically improved algorithmic efficiency of these multilevel methods will contribute to advancing technological capabilities in our increasingly information-based economy, and will help to extend the boundaries of our scientific understanding, for example in the field of extrasolar planetary atmospheres.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
311947-2008
Name nom
DeSterck, Hans
Department département
Applied Mathematics
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2010
Competition year année de concours
2008
Award amount
25000
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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
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
Multilevel methods for scientific computing
Keyword
NSERC
Application summary
This project develops new computer algorithms of 'divide-and-conquer'-type for two important scientific computing applications. The algorithms are made efficient by exploiting representations of the problems on multiple levels with successively coarser resolution.
The first problem deals with the organization and retrieval of large amounts of information, for instance the importance ranking of web pages for search engine queries. Efficient multilevel methods will be derived for so-called Markov chain problems, which provide a model for importance ranking.
The second problem deals with the simulation of highly nonlinear systems of equations, for example models of complex fluid flow around airplanes or in planetary atmospheres. Efficient multilevel methods will be developed for these nonlinear systems, by explicitly isolating the nonlinear singularities from the smooth part of the solution.
The multilevel algorithms to be developed proceed in an iterative way by improving an initial guess of the problem solution over successive cycles. The improvements in each cycle are made efficient by reducing error components with different scales on appropriate progressively coarser levels in a recursive way. This approach can lead to a speedup of several orders of magnitude, compared with more conventional methods.
The dramatically improved algorithmic efficiency of these multilevel methods will contribute to advancing technological capabilities in our increasingly information-based economy, and will help to extend the boundaries of our scientific understanding, for example in the field of extrasolar planetary atmospheres.