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

                          Graham Horton          (1)
                          Stefan Vandewalle      (2)
                          Patrick Worley         (3)


                                   ABSTRACT

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.


(1) Lehrstuhl f\"ur Rechnerstrukturen (IMMD 3)
    Universit\"at Erlangen-N\"urnberg
    Martensstrasse 3
    D-8520 Erlangen
    Federal Republic of Germany

    E-mail: graham@immd3.informatik.uni-erlangen.de

(2) Department of Computer Science
    Katholieke Universiteit Leuven
    Celestijnenlaan 200A
    B-3001 Leuven (Heverlee)
    Belgium

    E-mail: stefan@cs.kuleuven.ac.be

(3) Mathematical Sciences Section
    Oak Ridge National Laboratory
    P.O. Box 2008
    Oak Ridge, Tennessee 37831-6367
    USA

    E-mail: worley@msr.epm.ornl.gov