Design and implementation of parallel multigrid algorithms.

*(English)*Zbl 0652.65076
Multigrid methods, 3rd Conf., Copper Mountain/Colo. 1987, Lect. Notes Pure Appl. Math. 110, 101-115 (1988).

[For the entire collection see Zbl 0641.00031.]

The implementation of multigrid algorithms for solving model partial differential equations on hypercubes is investigated. It is shown that one can design and map on the hypercube asymptotically optimal (with respect to the execution time) multigrid algorithms in both cases if there are many grid points per processor and if there is only one grid point per processor. Complexity estimates confirmed by experimental results on an Intel iPSC system and allowing us to predict the execution time are presented. To avoid the “idle processor problem” the authors proposed a new interesting modification of the multigrid algorithm. The basic idea of this modification consists in splitting the residual equation (before doing the coarse grid correction) appropriately into some auxiliary equations in order to keep the processors busy. The Fourier analysis of the model 1D-problem \(-u''=f\) shows that this technique additionally improves the two-grid rate in comparison with the standard two-grid method.

The implementation of multigrid algorithms for solving model partial differential equations on hypercubes is investigated. It is shown that one can design and map on the hypercube asymptotically optimal (with respect to the execution time) multigrid algorithms in both cases if there are many grid points per processor and if there is only one grid point per processor. Complexity estimates confirmed by experimental results on an Intel iPSC system and allowing us to predict the execution time are presented. To avoid the “idle processor problem” the authors proposed a new interesting modification of the multigrid algorithm. The basic idea of this modification consists in splitting the residual equation (before doing the coarse grid correction) appropriately into some auxiliary equations in order to keep the processors busy. The Fourier analysis of the model 1D-problem \(-u''=f\) shows that this technique additionally improves the two-grid rate in comparison with the standard two-grid method.

Reviewer: U.Langer

##### MSC:

65N22 | Numerical solution of discretized equations for boundary value problems involving PDEs |

65F10 | Iterative numerical methods for linear systems |

65Y05 | Parallel numerical computation |

35J05 | Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation |

68Q25 | Analysis of algorithms and problem complexity |