On the Choice of Prolongation Operators in the Multicoarse Correction Method
Sergueï SOKOL
42 av G. Coriolis
31057 Toulouse

Multigrid is a well known efficient iterative method for solving discretised elliptical PDE's. However it has limitations on some kinds of problems such as those with large jumps in coefficients or highly asymmetrical problems. These limitations were overcome by introducing matrix dependent restriction-prolongation operators. This has led to such algorithms as Black Box Multigrid, Grandchild of Frequency Decomposition Method and others. These algorithms have proved their efficiency on a set of various difficult problems, but the construction of these kinds of algorithms remains till now something purely heuristic.

In this paper, a less heuristic approach is proposed for choosing restriction-prolongation operators. It is based on the decoupling of subproblems corresponding to different coarse grids in some optimal or suboptimal way. This leads naturally to the notion of optimal or suboptimal operators. The use of the Frobenius norm as an optimality criterion is particularly advantageous, the operators can be constructed in a parallel manner, or in some cases, can be found analytically. The efficiency of the resulting algorithm is illustrated using a series of test problems.