Smoother dependent interpolation for AMG

Menno Verbeek* and Jane Cullum+

*Mathematical Institute, Utrecht University, P.O.Box 80.010, 3508 TA Utrecht, The Netherlands
+MS B256, CIC-3, Los Alamos National Laboratory, Los Alamos, NM 87545, USA


In the Ruge-Stüben variants of Algebraic Multigrid (AMG), the interpolation matrix P is determined from the linear system matrix A only. However, for AMG to work efficiently, P should be chosen such, that the coarse grid correction damps the errors that are not damped by the smoother, the so called algebraically smooth errors. Therefore, not only the matrix A, but also the choice of smoother determines what is algebraically smooth. This suggests using not only A, but also the smoother, to determine the interpolation P.

Errors in the span of the columns in P are removed exactly by a (2-level) coarse grid correction. Thus, we would like this span to contain the algebraically smooth errors. To achieve this, we assume that algebraically smooth vectors have the same local behaviour with different, geometrically smooth, amplitudes or modes. This is not an uncommon situation for partial differential equations with simple smoothers. We use this local behaviour to generate a sparse P that represents this local behaviour, and thus approximately spans the algebraically smooth vectors.

To obtain the local behaviour, we use an approximation to the largest eigenvector of the smoother error operator. We correct a ``linear'' interpolation to make it exact for this algebraically smooth vector. We also explore the possibilities of using multiple smooth vectors to construct an interpolation matrix P.

Results of numerical experiments, including transport problems from the ASCI program and electromagnetic boundary integral problems, will be presented.