The Frequency Decomposition Multi-Grid Algorithm

Multi-grid methods are known as very fast solvers of a large class of discretised partial differential equations. However, the multi-grid method cannot be understood as a fixed algorithm. Usually, the components of the multi-grid iteration have to be adapted to the given problem and sometimes the problems are modified into those acceptable for multi-grid methods. In particular, the smoothing iteration is the most delicate part of the multi-grid process.An iteration is called a robust one, if it works for a sufficiently large class of problems. Attempts have been made to construct robust multi-grid iterations by means of sophisticated smoothing processes (cf. Wesseling [6], [3, p.222]). In particular, robust methods should be able to solve singular perturbation problems. Examples of such problems are the anisotropic equations of the next subsection, the convection-diffusion equation and others (cf. Hackbusch [3,§10]).To overcome the problem of robustness we propose a new multi-grid variant.lt is called the frequency decomposition multi-grid algorithm since different parts of the frequency spectrum are treated by different respective coarse-grid corrections. This explains that we need more than one coarse grid and further prolongations and restrictions. It is to be emphasized that the smoothing procedure may be very simple (e.g. the GauB-Seidel iteration). Nevertheless, we claim that the resulting multi-grid algorithm is suited not only to the anisotropic equations described below but also for many other singular perturbation problems. We describe the application to the anisotropic problem since this simplifies the choice of the prolongations and restrictions. Other applications possibly require the matrix-dependent prolongation (cf. Hackbusch[3,§10.31)