Multigrid Smoothing with Explicit Approximate Inverse Stencils
Oliver Bröker (ETH Zürich)
Approximate inverses based on Frobeniusnorm minimization [4] have
been shown to yield good smoothers in (algebraic) multigrid
[1,2,3]. This approach offers some degrees of freedom, mainly the
sparsity pattern of the inverse, and thus potential improvement. The
essential advantage of the approach is the smoothing efficiency,
coupled with high parallelism.
We investigate this smoother class for stencil based problems,
including the Laplacian, the MehrstellenOperator,
convectiondiffusion equations, mixedderivatives, the
Helmholtzoperator and the biharmonicoperator. Exploiting regular
grid structures enables us to compute explicit formulas and may render
the initialization and storage of an approximate inverse unnecessary.
Critical values in the construction of an efficient multigrid scheme
are the smoothing, the twogrid and the threegridfactor
[5]. Analyzing these factors for the various stencils shows that in
some cases Frobeniusnorm minimization yields a near optimal smoother,
while for others not even convergence is obtained. We show that in
most cases approximate inverse stencil entries with better
smoothingfactor and overall convergence properties can be found and
propose several strategies to construct such values.
We conclude the talk with numerical results on large problems.
[1] O. Broeker
Parallel Algebraic Multigrid with Sparse Approximate Inverses
Dissertation No. 15129, ETH Zurich, 2003/May
[2] O. Broeker and M.J. Grote
Sparse Approximate Inverse Smoothers for Geometric and Algebraic Multigrid
Applied Numerical Mathematics, Vol. 41, Number 1, pp. 6180, 2002/Mar
[3] O. Broeker, M.J. Grote, C. Mayer, A. Reusken
Robust Parallel Smoothing for Multigrid Via Sparse Approximate Inverses
SIAM Journal on Scientific Computing, Vol. 23, Number 4, pp. 13961417, 2001/Oct
[4] M.J. Grote and T. Huckle
Parallel Preconditioning with Sparse Approximate Inverses
SIAM J. of Scientific Computing, Vol. 18, Number 3, pp. 838853, 1997/May
[5] R. Wienands and W. Joppich
Practical Fourier Analysis for Multigrid Methods
CRC Press, 2004/Nov
