Sparse approximate inverse smoothers for geometric and algebraic multigrid Original Research Article

Sparse approximate inverses are considered as smoothers for geometric and algebraic multigrid methods. They are based on the SPAI-Algorithm [M.J. Grote, T. Huckle, SIAM J. Sci. Comput. 18 (1997) 838–853], which constructs a sparse approximate inverse M of a matrix A, by minimizing I−MA in the Frobenius norm. This leads to a new hierarchy of inherently parallel smoothers: SPAI-0, SPAI-1, and SPAI(ε). For geometric multigrid, the performance of SPAI-1 is usually comparable to that of Gauss–Seidel smoothing. In more difficult situations, where neither Gauss–Seidel nor the simpler SPAI-0 or SPAI-1 smoothers are adequate, further reduction of ε automatically improves the SPAI(ε) smoother where needed. When combined with an algebraic coarsening strategy [J.W. Ruge, K. Stüben, in: S.F. McCormick (Ed.), Multigrid Methods, SIAM, 1987, pp. 73–130] the resulting method yields a robust, parallel, and algebraic multigrid iteration, easily adjusted even by the non-expert. Numerical examples demonstrate the usefulness of SPAI smoothers, both in a sequential and a parallel environment. Essential advantages of the SPAI-smoothers are: improved robustness, inherent parallelism, ordering independence, and possible local adaptivity.