Title:
Coarsening by Compatible Relaxation

Speaker:
Oren Livne
Scientific Computing and Imaging Institute, 50 S Central Campus Dr., 
Room 3490, University of Utah, Salt Lake City, UT 84103
email livne@sci.utah.edu
web www.sci.utah.edu/personnel/livne.html


Abstract

Algebraic Multigrid (AMG) solvers of large sparse linear system of 
equations are based on multigrid principles but no do explicitly use the 
geometry of the grids. The emphasis in AMG is on black on procedures for 
coarsening the set of equations, relying on its algebraic relations. 
Although AMG is widely employed, e.g. for solving second-order elliptic 
discretized PDEs with disordered coefficients on unstructured grids, its 
scope is rather limited to these cases. However, AMG may be remedied, by 
systemtically understanding and improving its ingredients: relaxation, 
coarse levels and inter-level transfers. We present a novel approach for 
selecting the coarse variables for AMG. Classical AMG coarse set 
construction relies on the strength of local algebraic connections 
between variables, that are often misleading and inaccurate. 
Alternatively, our coarse set quality measure is the rate of convergence 
of compatible relaxation (CR) [Brandt, ETNA, 2000]. It also leads to a 
construction algorithm of the coarse set. We will present numerical 
examples of our algorithm for simple model problems, e.g., anistropic 
diffusion and the biharmonic operator, for which classical AMG often 
fails. This work makes it possible to assess and construct a coarse set 
of variables for a given system, prior to its actual use by an AMG 
solver. Undergoing research is focused on attaining CR rates (that play 
a similar role to the smoothing rate in geometric multigrid, predicting 
the ideal multigrid efficiency) using the "bootstrap AMG" algorithm that 
iteratively derives its coarse-to-fine interpolation operators.
Joint work with Prof. A. Brandt, Department of Applied Mathematics, 
Weizmann Institute of Science.