×

Waveform relaxation with fast direct methods as preconditioner. (English) Zbl 0969.65085

The authors consider the numerical solution of linear parabolic equations in a rectangle with the aim to achieve optimal parallel complexity. They propose to use the fast Fourier transformation in one or both space directions and identify the differential operators for which this approach leads to a decoupling of the semidiscretized equations. In time direction, an implicit linear multistep method is assumed which, considered over all time steps, leads to banded Toeplitz systems which are solved by parallel cyclic reduction.
In case the semidiscretized equations can not be decoupled, a preconditioned waveform relaxation is proposed in which the preconditioner leads to decoupled equations (at least in one space direction). Several versions of this efficient but suboptimal method are discussed and numerical results are exhibited which show good convergence, but it becomes clear that for problems with coefficients varying over several orders of magnitude, convergence can be arbitrarily slow.

MSC:

65M20 Method of lines for initial value and initial-boundary value problems involving PDEs
65T50 Numerical methods for discrete and fast Fourier transforms
65F10 Iterative numerical methods for linear systems
65F35 Numerical computation of matrix norms, conditioning, scaling
65L06 Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations
35K15 Initial value problems for second-order parabolic equations
65Y05 Parallel numerical computation
65Y20 Complexity and performance of numerical algorithms
65M12 Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs
PDFBibTeX XMLCite
Full Text: DOI