An Algorithm with Polylog Parallel Complexity for Solving
Parabolic Partial Differential Equations

G. Horton
Lehrstuhl füt;r Rechnerstrukturen (IMMD 3)
Universität;t Erlangen-N&uulmt;rnberg
Martensstrasse 3
D-8520 Erlangen
Federal Republic of Germany

S. Vandewalle
Department of Computer Science
Katholieke Universiteit Leuven
Celestijnenlaan 200A
B-3001 Leuven (Heverlee)

Patrick Worley
Mathematical Sciences Section
Oak Ridge National Laboratory
P.O. Box 2008
Oak Ridge, Tennessee 37831-6367


The standard numerical algorithms for solving parabolic partial differential equations are inherently sequential in the time direction. This paper describes an algorithm for the time-accurate solution of certain classes of parabolic partial differential equations that can be parallelized in both time and space. It has a serial complexity that is proportional to the serial complexities of the best known algorithms. The algorithm is a variant of the multigrid waveform relaxation method where the scalar ordinary differential equations that make up the kernel of computation are solved using a cyclic reduction type algorithm. Experimental results obtained on a massively parallel multiprocessor are presented.

Contributed July 30, 1993.