Katholieke Universiteit Leuven

Department of Computer Science

Celestijnenlaan 200A

B-3001 Heverlee, Belgium

Abstract

Over the last few years, fast multigrid methods have been developed
for the numerical solution of parabolic initial-boundary value problems.
These algorithms have polylog parallel complexity.
A lower bound for the complexity of any parabolic PDE solver
follows from an information-theoretical analysis:
if *N* is the number of points in the space-time grid,
the minimal time complexity
is O(*N*) on a sequential machine,
and O(log *N*) on an ideal parallel computer.

Unfortunately, we have no algorithm that can solve
a general parabolic PDE this fast.
For a restricted class of parabolic problems, however,
one can devise an algorithm that does indeed have optimal
parallel complexity.
This is the case when the parabolic operator is
separable and has constant coefficients.
The use of a multidimensional FFT to decouple the unknowns
in the spatial domain,
and parallel cyclic reduction
to solve the recurrence relations in the time dimension,
then results in an optimal direct solver:
this is the *FFT/CR* algorithm.
Linewise decoupling in space yields a variant suitable for
coarse-grain parallellism.

We discuss the use of FFT/CR as a preconditioner
to iteratively solve more general parabolic PDEs.
This approach naturally leads to a
*waveform relaxation* (WR) scheme.
Waveform relaxation was developed as an iterative method
for solving large systems of ODEs.
It is the continuous-in-time analogue of stationary iterative methods
for linear algebraic equations based on matrix splitting.
Common preconditioners are of Jacobi or Gauss-Seidel type.
Recently, preconditioning with Toeplitz matrices
was also investigated.

Using the FFT/CR solver as a preconditioner preserves most of the potential for concurrency that accounts for the attractiveness of WR with simple preconditioners (Jacobi, red-black Gauss-Seidel), while showing an important advantage: the convergence rate of the resulting WR iteration is independent of the mesh size used in the spatial discretisation. Convergence will be faster if the relative variation of the coefficients is smaller.

The talk introduces the FFT/CR algorithm and surveys some convergence properties of WR with such preconditioners. These properties are verified by numerical results.