PARALLEL MULTIGRID ALGORITHMS ON CM-5

Solutions to partial differential equations are required in many engin eering applications. The multigrid method is an iterative technique fo r speeding up the solution of these equations. The authors describe a parallel implementation of the multigrid method on the connection mach ine CM-5 architecture. An analytic model is presented for estimating t he computation and communication times of the multigrid algorithm. The times predicted by the analytic model are within 5% of the results ob tained from CM-5. Results demonstrate that the communication overhead incurred by the parallel multigrid algorithm is relatively small compa red to the computation time. Consequently, implementations of the mult igrid algorithm on the CM-5 easily achieve processor efficiencies near 100%.