IWR, Universität Heidelberg, INF 368,
D-69120 Heidelberg, Germany
phone: ++49-6221-548866, fax: ++49-6221-548860
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
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.