THE MULTIGRID PRECONDITIONED CONJUGATE GRADIENT METHOD

Osamu Tatebe

Department of Information Science
University of Tokyo
Tokyo, JAPAN


SUMMARY

A multigrid preconditioned conjugate gradient method (MGCG method),
which uses the multigrid method as a preconditioner of the PCG method,
is proposed. The multigrid method has inherent high parallelism and
improves convergence of long wave length components, which is
important in iterative methods. By using this method as a
preconditioner of the PCG method, an efficient method with high
parallelism and fast convergence is obtained. First, it is considered
a necessary condition of the multigrid preconditioner in order to
satisfy requirements of a preconditioner of the PCG method. Next
numerical experiments show a behavior of the MGCG method and that the
MGCG method is superior to both the ICCG method and the multigrid
method in point of fast convergence and high parallelism. This fast
convergence is understood in terms of the eigenvalue analysis of the
preconditioned matrix. From this observation of the multigrid
preconditioner, it is realized that the MGCG method converges in very
few iterations and the multigrid preconditioner is a desirable
preconditioner of the conjugate gradient method.