Robust and Parallel Smoothing for Algebraic Multigrid

Description

Algebraic multigrid (AMG) was first introduced in the early 1980's. Recently there has been a major resurgence of interest in the field of algebraic multilevel methods, largely due to the need to solve increasingly larger systems with hundreds of millions or billions of unknowns, on unstructured grids. The size of these problems dictates the use of large-scale parallel processing, which in turn requires algorithms that scale with the problem size. Multigrid methods are well known to be scalable for elliptic problems on regular grids. However, modern applications usually involve extremely complex geometries, making structured geometric grids extremely difficult to use. Application code designers are turning in increasing numbers to very large unstructured grids, and AMG is often seen as the most promising method for solving large-scale problems in this context.

Any efficient multigrid algorithm relies on the complementary interplay of smoothing and coarse grid correction. The (original) AMG algorithm uses the (simple) Gauss-Seidel iteration as a smoother, but determines the coarse "grid" space in a sophisticated way to improve robustness of the method. Since Gauss-Seidel is inherently sequential, it is complicated to parallelize AMG. Moreover, if the iteration fails to converge, there is no automatic way to improve on the smoother. Here we propose and study the usefulness of smoothers based on sparse approximate inverses (SPAI). Not only inherently parallel, their preformance can also easily be adjusted even by a non-expert. Thus we aim for a more general and inherently parallel algebraic multigrid method.

Contacts

Prof. M. Grote (grote@sam.math.ethz.ch), O. Broeker and Prof. W. Gander (ETHZ).