Overview

The multigrid method is one of the fastest methods for solving systems of equations involving a large number of unknowns. The method is due to Fedorenko, who formulated it first as a two-grid method [1961], and then later as a multigrid method [1964]. He showed that the algorithm requires only (n) operations, where n is the number of unknowns. Bachvalov [1966] continued the study for difference equations, and allowed nonconstant coefficients. A. Brandt was the first to discover in the mid-seventies that the multigrid method is considerably better than other known methods, even for values of n which occur in actual problems. Nearly at the same time, the multigrid method was discovered independently by Hackbusch [1976], whose approach also led to a simplification of the concepts involved.

Our starting point is the observation that in solving a system of equations, we should use different methods for the high frequency (oscillating) and low frequency (smooth) parts. The idea of the multigrid method is to combine two different methods to get an algorithm which will be effective on the entire spectrum.

Classical iterative methods work essentially by smoothing, i.e. they quickly eliminate the high-frequency parts of the error function. The low frequency parts of the functions can then be computed relatively well on a coarser grid. Although we cannot strictly separate the low and high frequency parts, we are able to get iterative methods whose rate of convergence (i.e. error reduction factors) are in the range from 1/20...