New Advances in Algebraic Multigrid

Dr. Rob Falgout

May 25, 2001, 8 a.m. T 711

Computer simulations play an increasingly important role in scientific investigations. As a result, codes are being developed to solve complex multi-physics problems at very high resolutions. Such large-scale simulations require massively parallel computing, but this is not sufficient. One also needs scalable algorithms such as multigrid, and scalable implementations of these algorithms.

The Center for Applied Scientific Computing (CASC) at Lawrence Livermore National Laboratory is developing new algebraic multigrid (AMG) algorithms and codes for solving unstructured grid problems. AMG is well-suited for solving unstructured grid problems, and works remarkably well over a wide variety of applications. However, for some problems, AMG is not effective without certain problem-specific modifications or careful parameter tuning. To address this, CASC researchers are developing a new class of algorithms for finite element problems called AMGe. As a departure from standard AMG that only requires the system matrix, AMGe also assumes access to local element stiffness matrices. These stiffness matrices are used to construct a local measure derived from multigrid theory to determine a local representation of algebraically "smooth" error. This representation provides the basis for constructing effective interpolation and coarsening procedures. To parallelize the coarsening algorithm, a technique introduced by Luby for maximal independent set algorithms is being investigated.

In this talk, we will present the latest developments in AMGe research, including a new spectral AMGe method that is being developed. The spectral AMGe method makes almost no smoothness assumptions, and hence, promises to be very robust. We will also discuss recent findings relating Achi Brandt's compatible relaxation ideas to our AMGe measure.

This work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under contract no. W-7405-Eng-48.