Simoens, Jo; Vandewalle, Stefan Waveform relaxation with fast direct methods as preconditioner. (English) Zbl 0969.65085 SIAM J. Sci. Comput. 21, No. 5, 1755-1773 (2000). 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. Reviewer: Gisbert Stoyan (Budapest) Cited in 3 Documents 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 Keywords:semidiscretization; waveform relaxation; dynamic iteration; fast Fourier transform; parallel computation; preconditioning; numerical examples; linear parabolic equation; complexity; implicit linear multistep method; banded Toeplitz systems; cyclic reduction; convergence PDFBibTeX XMLCite \textit{J. Simoens} and \textit{S. Vandewalle}, SIAM J. Sci. Comput. 21, No. 5, 1755--1773 (2000; Zbl 0969.65085) Full Text: DOI