Title: Multilevel Preconditioning with Applicatons in Computer Graphics and Geosciences

Speaker: Burak Aksoylu, Department of Mathematics and the Center for Computation and Technology
at LSU

Date/Time: Wednesday, June 11, 2008 at 10:00 - 11:00am (MST)

Location: CSRI Building, Room 90 (Sandia NM)

Brief Abstract: In the first part of the talk, an overview of the author's work on multilevel solver technologies will be presented. The multilevel methods of interest stem from the Bramble-Pasciak-Xu (BPX) preconditioner (also known as additive multigrid) and the wavelet-modified hierarchical basis (WHB) preconditioners.  We extend optimality results of the above methods to locally refined 2 and 3 dimensional meshes.  Utilization of such preconditioners in computer graphics applications will be presented.

In the second part of the talk, we give a detailed presentation a new preconditioner suitable for solving linear systems arising from finite element approximations of elliptic PDEs with high-contrast coefficients.  The construction of the preconditioner consists of two phases.  The first phase is an algebraic one which partitions the degrees of freedom into ``high'' and ``low'' permeability regions which may be of arbitrary geometry.  This partition yields a corresponding blocking of the stiffness matrix and hence a formula for the action of its inverse involving the inverses of both the high permeability block and its Schur complement in the original matrix. The structure of the required sub-block inverses in the high contrast case is revealed by a singular perturbation analysis (with the contrast playing the role of a large parameter). This shows that for high enough contrast each of the sub-block inverses can be approximated well by solving only systems with constant coefficients. The second phase of the algorithm involves the approximation of these constant coefficient systems using multigrid methods. The result is a general method of algebraic character which (under suitable hypotheses) can be proved to be robust with respect to both the contrast and the mesh size.

While a similar performance is also achieved in practice by algebraic multigrid (AMG) methods, this performance is still without theoretical justification.  Since the first phase of our method is comparable to the process of identifying weak and strong connections in conventional algebraic multigrid algorithms, our theory provides to some extent a theoretical justification for these successful algebraic procedures.  We demonstrate the advantageous properties of our preconditioner using experiments on model problems.  Our numerical experiments show that for sufficiently high contrast the performance of our new preconditioner is almost identical to that of the Ruge and St\"{u}ben AMG preconditioner, both in terms of iteration count and CPU-time.

CSRI POC: Mike Parks  (1414)  845-0512