Center for Applied Scientific Computing

Lawrence Livermore National Laboratory

P.O. Box 808, L-561

Livermore, CA 94551

Abstract

Much work has been done developing robust multigrid methods for
solving diffusion equations on structured grids, especially when
discontinuous coefficients and anisotropy are present (see e.g.,
[1-9]). However, all of these methods have relatively high
computational costs and memory costs. The goal of this work is to
develop an algorithm that is both robust *and* efficient.

We will present a method based on a modification of the multiple semicoarsened grids (MSG) method in [4]. The robustness of MSG is studied in [5], and a new, more efficient, variant is proposed in [6]. Our approach for improving efficiency is based on the relationship between the MSG algorithm, the hierarchical-basis multigrid method [10], and the sparse grids method [11,12].

The sparse grids method is actually a discretization method that considerably reduces computational and storage costs with little loss in discretization accuracy. The method uses hierarchical-basis functions defined on a subset of the MSG grids, and uses the so-called combination technique to implicitly define the discretization on the sparse grid. It is important to note that although the sparse grids method and the MSG method both provide solutions to the diffusion problem of interest, they do not solve them on the same discrete grid. We consider solving the diffusion equation with the MSG method, but with only a subset of the MSG grids. If we use the same grids as in the sparse grids method, one can think of this approach as using the sparse grids discretization to form the coarse grid problem in a two-level multigrid method. Since the sparse grids discretization is nearly as accurate as the standard Cartesian discretization, we expect this method to work well.

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.

[1] S. Schaffer, *A semi-coarsening multigrid method for elliptic
partial differential equations with highly discontinuous and
anisotropic coefficients*, SIAM J. Sci. Comput., 20 (1998),
pp. 228-242.

[2] P. N. Brown, R. D. Falgout, and J. E. Jones, *Semicoarsening
multigrid on distributed memory machines*. To appear in the SIAM
Journal on Scientific Computing special issue on the Fifth Copper
Mountain Conference on Iterative Methods. Also available as LLNL
technical report UCRL-JC-130720, 1999.

[3] W. A. Mulder, *A new multigrid approach to convection
problems*, J. Comput. Phys., 83 (1989), pp. 303--323.

[4] N. H. Naik and J. R. Rosendale, *The improved robustness of
multigrid elliptic solvers based on multiple semicoarsened grids*,
SIAM J. Numer. Anal., 30 (1993), pp. 215-229.

[5] C. W. Oosterlee and P. Wesseling, *On the robustness of a multiple
semi-coarsened grid method*, Z. Angew. Math. Mech., 75 (1995),
pp. 251-257.

[6] T. Washio and C. W. Oosterlee, *Flexible multiple semicoarsening for
three-dimensional singularly perturbed problems*, SIAM
J. Sci. Comput., 19 (1998), pp. 1646-1666.

[7] W. Hackbusch, *The frequency decomposition multi-grid method*,
in Multigrid Methods IV, Proceedings of the Fourth European Multigrid
Conference, Amsterdam, July 6-9, 1993, vol. 116 of ISNM, Basel, 1994,
Birkhauser, pp. 43-56.

[8] J. E. Dendy and C. C. Tazartes, *Grandchild of the frequency
decomposition multigrid method*, SIAM J. Sci. Comput., 16 (1995),
pp. 307--319.

[9] J. E. Dendy, *Revenge of the semicoarsening frequency
decomposition multigrid method*, SIAM J. Sci. Comput., 18 (1997),
pp. 430-440.

[10] R. E. Bank, T. Dupont, and H. Yserentant, *The hierarchical basis
multigrid method*, Numer. Math., 52 (1988), pp. 427-458.

[11] C. Zenger, *Sparse grids*, in Parallel algorithms for partial
differential equations: Proceedings of the Sixth GAMM-Seminar, Kiel,
Jan. 1990, vol. Notes on Numerical Fluid Mechanics, vol. 31, Vieweg,
Braunschweig, 1991.

[12] M. Griebel, M. Schneider, and C. Zenger, *A combination technique
for the solution of sparse grid problems*, in Proceedings of the
IMACS International Symposium on Iterative Methods in Linear Algebra,
Amsterdam, 1992, Elsevier, pp. 263-281.