A MODEL AND IMPLEMENTATION OF MULTIGRID FOR MASSIVELY PARALLEL COMPUTERS

Multigrid is a fast and popular iterative method used to solve linear partial differential equations. However, because the solution of very small problems is inherent in the multigrid iteration, it is difficult to implement efficiently on a massively parallel computer. In this paper, we present a model for the efficiency of multigrid on a parallel computer that depends only on the efficiency of the smoother at each level. This model can be used to verify that it is indeed difficult to obtain extremely high efficiencies (>95%), but that it is relatively easy to obtain moderately high. efficiencies (70% to 85%). The model also indicates that moderately high efficiencies can still be achieved as the number of dimensions in the partial differential equation increases. We also present an implementation of the multigrid v-cycle that has achieved 84% efficiency on the 1,024-processor NCUBE/ten.