Large simulations in diverse application areas such as fluid dynamics, elasticity, groundwater flow, etc., require the solution of large systems of linear equations with up to several billions of unknowns. Fortunately, these matrix systems tend to be sparse: only a small number of nonzero elements are present per matrix row. By employing iterative multilevel techniques ('multigrid'), nearly 'optimal' solvers can be constructed, for which the number of computer operations is linearly proportional to the number of unknowns (recall that for the basic Gaussian elimination algorithm, the execution time scales as the third power of the number of unknowns!) One such a successful multilevel algorithm is the 'Algebraic Multigrid' or AMG algorithm.

However, this AMG algorithm does not perform well in all cases: for large problems in 3D, the memory use and the so-called setup time grow strongly as a function of the number of unknowns: the algorithm does not scale well!

The goal of this project is to develop new 'coarsening' and 'interpolation' algorithms, in order to reduce memory use and execution time of the AMG algorithm for difficult problems in 3D. See 'Reducing Complexity in Algebraic Multigrid' [ppt] for some more background and some initial results we have obtained. This project may possibly also involve performance optimization (efficient use of the computer cache) of the AMG algorithm.

This project requires a thorough study of (algebraic) multigrid theory, the development and implementation (in C) of new algorithms, and performance and scaling tests on serial and parallel computers. The project involves close collaboration with Computational Mathematicians and Computer Scientists at the Center for Applied Scientific Computing of the US Lawrence Livermore National Laboratory in California. You will be expected to spend several summer months at the Livermore Laboratory. Large parallel computers with more than 1,000 processors at the Livermore lab will be used, and parallel computing resources available in Ontario's SHARCNET will be used as well.

This topic is suitable for a PhD or Master's thesis project. A solid background in numerical analysis and numerical linear algebra is a plus. Please contact Hans De Sterck if you are interested.

Created by Hans De Sterck.
Department of Applied Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada.
Phone: 1-519-888-4567 ext 7550, Fax: 1-519-746-4319, E-mail: hdesterck@math.uwaterloo.ca.
Office: MC 5016. campus map