Abstract
We discuss preconditioning and overlapping of waveform relaxation methods for sparse linear differential systems. It is demonstrated that these techniques significantly improve the speed of convergence of the waveform relaxation iterations resulting from application of various modes of block Gauss-Jacobi and block Gauss-Seidel methods to differential systems. Numerical results are presented for linear systems resulting from semi-discretization of the heat equation in one and two space variables. It turns out that overlapping is very effective for the system corresponding to the one-dimensional heat equation and preconditioning is very effective for the system corresponding to the two-dimensional case.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A. Bellen and M. Zennaro,The use of Runge-Kutta formulae in waveform relaxation methods, Appl. Numer. Math., 11 (1993), pp. 95–114.
A. Bellen, Z. Jackiewicz and M. Zennaro,Contractivity of waveform relaxation Runge-Kutta iterations and related limit methods for dissipative systems in the maximum norm, SIAM J. Numer. Anal., 31 (1994), pp. 499–523.
K. Burrage,Parallel and Sequential Methods for Ordinary Differential Equations, Oxford University Press, Oxford, 1995.
K. Burrage, Z. Jackiewicz and R. Renaut,The performance of preconditioned waveform relaxation techniques for pseudospectral methods, to appear in Numerical Methods for Partial Differential Equations.
P. E. Crouch and R. Grossman,Numerical integration of ordinary differential equations on manifolds, J. Nonlinear Science, 3 (1993), pp. 1–33.
A. Frommer and B. Pohl,A comparison result for multisplittings based on overlapping blocks and its application to waveform relaxation methods, Research Report No. 93-05, Seminar für Angewandte Mathematik, ETH, Zürich, Switzerland, 1993.
E. Gallopoulos and Y. Saad,On the parallel solution of parabolic equations. In Proc. ACM SIGARCH-89, 1989, pp. 17–28.
Z. Jackiewicz and B. Owren,Convergence analysis of waveform relaxation methods using pseudospectra, Preprint Numerics No. 2/1995, Department of Mathematics, The University of Trondheim, Trondheim, Norway.
R. Jeltsch and B. Pohl,Waveform relaxation with overlapping systems, Research Report No. 91-02, Seminar für Angewandte Mathematik, ETH, Zürich, Switzerland, 1991.
B. Leimkuhler,Estimating waveform relaxation convergence, SIAM J. Sci. Comput., 14 (1993), pp. 872–889.
B. Leimkuhler and A. Ruehli,Rapid convergence of waveform relaxation, Appl. Numer. Math., 11 (1993), pp. 211–224.
E. Lelarasmee,The waveform relaxation methods for the time domain analysis of large scale nonlinear dynamical systems. Ph.D. Thesis, University of California, Berkeley, California, 1982.
E. Lelarasmee, A. Ruehli and A. Sangiovanni-Vincentelli,The waveform relaxation method for time domain analysis of large scale integrated circuits, IEEE Trans. on CAD of IC and Syst., 1 (1982), pp. 131–145.
I. Lie and R. Skålin,Relaxation based integration by Runge-Kutta methods and its application to the moving finite element method, preprint.
Ch. Lubich,Chebyshev acceleration of Picard-Lindelöf iteration, BIT, 32 (1991), pp. 535–538.
U. Miekkala and O. Nevanlinna,Convergence of dynamic iteration methods for initial value problems, SIAM J. Sci. Stat. Comput., 8 (1987), pp. 459–482.
U. Miekkala and O. Nevanlinna,Sets of convergence and stability regions, BIT, 27 (1987), pp. 557–584.
O. Nevanlinna,Remarks on Picard-Lindelöf iteration, Part I, BIT, 29 (1989), pp. 328–346.
O. Nevanlinna,Remarks on Picard-Lindelöf iteration, Part II, BIT, 29 (1989), pp. 535–562.
O. Nevanlinna,Linear acceleration of Picard-Lindelöf iteration, Numer. Math., 57 (1990), pp. 147–156.
R. B. Sidje,Parallel algorithms for large sparse exponentials. Ph.D. Thesis, INRIA, Rennes, France, 1994.
R. D. Skeel,Waveform iteration and the shifted Picard splitting, SIAM J. Sci. Stat. Comput., 10 (1989), pp. 756–776.
R. E. Spilling,Dynamic iteration and the pseudospectral method, Student Report, Division of Mathematical Sciences, Norwegian Institute of Technology, Trondheim, Norway, 1993.
B. Pohl,On the convergence of the discretized multisplitting waveform relaxation algorithm, Appl. Numer. Math., 11 (1993), pp. 251–258.
S. Vandewalle,Parallel Multigrid Waveform Relaxation for Parabolic Problems, B.G. Teubner, Stuttgart, 1993.
J. K. White and A. Sangiovanni-Vincentelli,Relaxation Techniques for the Simulation of VLSI Circuits, Kluwer Academic Publishers, Boston, Dordrecht, Lancaster, 1987.
J. K. White, A. Sangiovanni-Vincentelli, F. Odeh and A. Ruehli,Waveform relaxation: Theory and practice, Trans. Soc. Computer Simulation, 2 (1985), pp. 95–133.
Author information
Authors and Affiliations
Additional information
The work of the second author was supported by the National Science Foundation under grant NSF DMS 92-08048.
Rights and permissions
About this article
Cite this article
Burrage, K., Jackiewicz, Z., Nørsett, S.P. et al. Preconditioning waveform relaxation iterations for differential systems. Bit Numer Math 36, 54–76 (1996). https://doi.org/10.1007/BF01740544
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01740544