Space-time concurrent multigrid waveform relaxation

Stefan Vandewalle

Dept. of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A, B-3001 Leuven, Belgium


We shall discuss the numerical solution of parabolic partial differential equations on multicomputers. The talk will focus on space-time concurrent multigrid waveform relaxation, a method which operates concurrently in space and time. This method solves the system of ordinary differential equations generated by the method of lines.

The method is based on waveform relaxation, a highly concurrent technique for solving large systems of ordinary differential equations, and multigrid. The operations of the algorithm can be parallelized straightforwardly across space, by using a spatial grid partitioning. In addition, the method allows an efficient parallelization across time. A partitioning method or a cyclic reduction technique is applied to calculate the linear recurrence relations arising in the numerical solution of the ordinary differential equations at each grid point. Performance results will be given obtained on an Intel iPSC/860 and on the Intel Touchstone Delta. They illustrate a significant gain over a concurrent implementation of a classical time-stepping algorithm.