\documentstyle{siam}
\title{Domain-oriented multilevel methods}
\author{M. Griebel\\
         {Institut f\"ur Informatik, Technische Universit\"at M\"unchen},\\
                 {Arcisstrasse 21, D-8000 M\"unchen 2}}
\begin{document}
\maketitle
{\bf Abstract}
Recently, a new concept for the development of multigrid and BPX-like
multilevel algorithms had been presented.
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 (i.e., the condition number resulting from the positive eigenvalues) 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.
These 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. This can be interpreted as a multiplicative subspace correction method. 

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.

This approach can be easliy generalized to obtain a domain decomposition multilevel method.
We just group the grid points together that belong 
a subdomain.
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 for the
new domain-oriented multilevel-method which are similar to that of standard multigrid-algorithms.

In contrast to the parallelization
of a multigrid method where communication has to take place on {\em all} levels,
our point-block approach needs 
substantially less communication.
In this sense, our new method is superior to other
parallel multigrid 
methods.
Additionally we obtain by means of the semidefinite system in a natural way
an optimal $O(1)$ preconditioner for the Schur complement.

We discuss the parallelization properties of the domain-oriented method, compare it with conventional parallel multigrid methods based on domain decomposition and present the results obtained for an implementation on different parallel computers.

\end{document}