Waveform Relaxation with Fast Direct Solvers as Preconditioner

Jo Simoens   Stefan Vandewalle

Katholieke Universiteit Leuven
Department of Computer Science
Celestijnenlaan 200A
B-3001 Heverlee, Belgium


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.