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.