Point-block multilevel methods

M. Griebel

Institut für Informatik, Technische Universität München, Arcisstrasse 21, D-8000 München 2


Recently, a new concept for the development of multigrid and BPX-like multilevel algorithms had been presented (see [GRI91c]). There, instead of a basis approach on the finest grid and the acceleration of the basic iteration by a MG-coarse grid correction or a BPX-type preconditioner a generating system was used to allow a non-unique level wise decomposed representation of the solution. The degrees of freedom are associated to the nodal basis functions of all levels under consideration. Now, the Galerkin approach leads to a semidefinite linear system with unknowns on all levels. The generalized condition number of this system is of the order O(1). Its solution is non-unique but in some sense equivalent to the unique solution of the standard problem on the finest grid.

Furthermore, it was shown that traditional iterative methods for the semidefinite system are equivalent to modern elaborated multilevel methods which exhibit optimal convergence properties. The conjugate gradient method (with appropriate diagonal scaling) for the semidefinite system is equivalent to the BPX-conjugate gradient method for the fine grid system. Gauss-Seidel type iterations for the semidefinite system are equivalent to certain multigrid methods. For details see [GRI91c]. This methods are level-oriented and can be considered as a level-block technique. An outer iteration switches from level to level and an inner iteration operates on the specific grid.

Now, we consider the semidefinite system from a different point of view. We group together all unknowns which belong to different levels but are associated to one grid point. This results in point-oriented methods and can be considered as a point-block technique. Now, an outer iteration switches form grid point to grid point. The local system that belongs to all basis functions of different levels centered in one grid point can be solved either directly or by an inner iteration that runs over all levels that are associated to the grid point under consideration. Furthermore, grid points can be grouped together to form subdomains. In this sense we get some sort of simple domain decomposition method which exhibits MG-type convergence properties.

We report the results of numerical experiments regarding the convergence rates of these new algorithms. It turns out that we obtain convergence rates and efficiencies for the new point-block ML-method which are superior to that of standard ML-algorithms. As the point-block method allows directly a interpretation in terms of domain decomposition its parallelization is straightforward. In contrast to the parallelization of a multilevel method where communication has to take place on all levels to maintain good convergence rates, our point-block approach needs substantially less communication due to its domain decomposition qualities. In this sense, our new method is superior to other parallel multigrid and multilevel methods.


[GRI91c] Michael Griebel, Multilevel algorithms considered as iterative methods on indefinite systems, TU München, Institut f. Informatik, TUM-I9143; SFB-Report 342/29/91 A. Also: Proceedings of the Copper Mountain Conference on Iterative Methods, April 9-14, 1992, Colorado, USA, 1991.