Waveform relaxation with fast direct methods as preconditioner

For a restricted class of parabolic PDEs one can devise a practical numeric al solver with a parallel complexity that is theoretically optimal. The met hod uses a multidimensional FFT to decouple the unknowns in the spatial dom ain into independent scalar ODEs. These are discretized to give recurrence relations in the time dimension solved by parallel cyclic reduction. This i s the FFT/CR algorithm. We discuss the use of FFT/CR as a preconditioner to iteratively solve more general parabolic PDEs. This approach naturally lea ds to a waveform relaxation scheme. Waveform relaxation was developed as an iterative method for solving large systems of ODEs. It is the continuous-i n-time analogue of stationary iterative methods for linear algebraic equati ons. Using the FFT/CR solver as a preconditioner preserves most of the pote ntial for concurrency that accounts for the attractiveness of waveform rela xation with simple preconditioners like Jacobi or red-black Gauss-Seidel, w hile showing an important advantage: the convergence rate of the resulting iteration is independent of the mesh size used in the spatial discretizatio n. The method can be accelerated by applying an appropriate scaling of the system before preconditioning.