Roman Wienands
On the Construction of Prolongation Operators for Multigrid

Mathematical Institute
University of Cologne
Weyertal 86-90
50931 Cologne
Germany
wienands@math.uni-koeln.de
Harald Koestler
Department of Computer Science 10, University of Erlangen-Nuremberg, Germany
Irad Yavneh
Department of Computer Science, Technion-Israel Institute of Technology

The quality of multigrid methods crucially depends on an efficient interplay between the smoothing operator ${\bf S}$ and prolongation ${\bf P}$. More precisely, the range of ${\bf S}$ should be sufficiently well represented in the range of ${\bf P}$. In the limit case of an optimal (but usually impractical) choice of ${\bf P}$ and ${\bf S}$ this means that

$${\bf S}{\bf v}= {\bf P}{\bf v}_{C} \qquad {\bf v}= \left( \begin{matrix}{\bf v}_{F} \\ {\bf v}_{C} \end{matrix} \right)$$ (1)

must hold for an arbitrary vector ${\bf v}$ where the variables and equations have been permuted such that F-variables come first. (Those variables which are to be contained in the coarse grid are commonly referred to as C-variables whereas the complementary set is related to the F-variables.)

In this talk we present a formalism for the construction of proper prolongation operators in order to accomplish the transfer from coarse to fine grids within a multigrid algorithm. The main idea is to force relation (1) only locally (i.e. at each coarse variable $i$) for a certain subset of (algebraically) smooth basis vectors ${\bf b}^{k(i)}$ $(k(i) = 1,\dots,n(i))$. Following this idea, classical matrix-dependent prolongations or prolongation operators based on smoothed aggregation can be recovered. Moreover, this rather general framework gives rise to many other variants whose complexity and accuracy can be controlled by a careful selection of basis vectors and smoothing operators, which are applied to construct ${\bf P}$. For example, geometric or other problem-dependent information can be easily exploited to tailor the prolongation to the particular application at hand.

At the end of the talk we will present numerical results for several two- and three-dimensional diffusion problems including jumping coefficients. In particular a real-world three-dimensional image segmentation problem from a medical application is discussed.