Parallel multigrid algorithms on CM-5

Solutions to partial differential equations are required in many engineering applications. The multigrid method is an iterative technique for speeding up the solution of these equations. The authors describe a parallel implementation of the multigrid method on the Connection Machine CM-5 architecture. An analytic model is presented for estimating the computation and communication times of the multigrid algorithm. The times predicted by the analytic model are within 5% of the results obtained from CM-5. Results demonstrate that the communication overhead incurred by the parallel multigrid algorithm is relatively small compared to the computation time. Consequently, implementations of the multigrid algorithm on the CM-5 easily achieve processor efficiencies near 100%.