On the Algebraic Construction of Multilevel
Transfer Operators



Christian Wagner



IWR, Universität Heidelberg, INF 368, D-69120 Heidelberg, Germany
phone: ++49-6221-548866, fax: ++49-6221-548860
email: christian.wagner@iwr.uni-heidelberg.de



The standard way to construct coarse grids for algebraic multilevel methods is a heuristic labeling of the nodes as C- and F-nodes. While the F-nodes are eliminated, the C-nodes built the coarse grid. After that, in a separate step, prolongation and restriction operators are constructed.

The basic idea of our new approach is to determine for each node those pairs of nodes which allow an optimal interpolation of the considered node. These pairs of neighbor nodes (in some cases only one node) are called parent nodes. A theoretical analysis shows that the problem of finding these parent nodes for the node i can be reduced to a minimization problem of the form

minimize ||Y z||

where Y is a sort of a smoothing operator and z is allowed to have aside from zi=-1 only two non-zero entries. Additionally, a filter condition (z,t)=0 with a given test vector t can be imposed. The minimization problem can be solved locally and is therefore relatively cheap. These non-zero entries will be the coefficients in the prolongation/restriction operators and the corresponding nodes are the parent nodes.

After the possible pairs of parent node have been determined, the nodes are labeled as C- and F-nodes such that each F-node can be interpolated using these pairs of parent nodes and the already computed coefficients. Additionally, a simple heuristic algorithm tries to minimize the number of C-nodes and the number of edges in the coarse grid graph.

The construction scheme has been generalized to systems of partial differential equations using a point-block approach. The multilevel algorithm has been parallelized and shows (almost) mesh size independent convergence for standard model problems. Realistic numerical experiments confirm the efficiency of the presented algorithm.