Abstract
The solution of ordinary an partial differential equations using implicit linear multi-step formulas (LMF)is considered. More precisely, boundary value methods (BVMs), a class of methods based on implicit formulas will be taken into account in this paper. These methods require the solution of large and sparse linear systems \(\hat M\)x = b. Block-circulant preconditioners have been propose to solve these linear systems. By investigating the spectral condition number of \(\hat M\), we show that the conjugate gradient method, when applied to solving the normalize preconditioned system, converges in at most O(log s) steps, where the integration step size is O(1/s). Numerical results are given to illustrate the effectiveness of the analysis.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
REFERENCES
O. Axelsson and V. A. Barker, Finite Element Solution of Boundary Value Problems, Theory and Computation, Academic Press, Orlando, FL, 1984.
A. O. H. Axelsson and J. G. Verwer, Boundary value techniques for initial value problems in ordinary differential equations, Math. Comp., 45 (1985), pp. 153-171.
P. Amodio and L. Brugnano, The conditioning of Toeplitz band matrices, Math. Comput. Model., 23: 10 (1996), pp. 29-42.
D. Bertaccini, P-circulant preconditioners and the systems of ODE codes, in Iterative Methods in Scientific Computation IV, IMACS Series in Computational and Applied Mathematics, D. R. Kincaid et al., eds., IMACS, NJ, 1999, pp. 179-193.
D. Bertaccini, A Circulant Preconditioner for the systems of LMF-based ODE codes, SIAM J. Sci. Comput., 22:3 (2000), pp. 767-786.
D. Bertaccini, An analysis of circulant preconditioners for linear multistep integrators, submitted, available at URL http://www.math.unifi.it/bertaccini.
D. Bertaccini, Reliable preconditioned iterative linear solvers for some numerical integrators, Numer. Linear Algebra Appl., 8:2 (2000), pp. 111-125.
D. Bertaccini and M. K. Ng, Skew-circulant preconditioners for systems of LMF-based ODE codes, in Lecture Notes in Comp. Sci., L. Vulkov et al., eds., Springer-Verlag, New York, 2001, pp. 93-101.
A. Böttcher and S. Grudsky, On the condition numbers of large semi-definite Toeplitz matrices, Linear Algebra Appl., 279 (1998), pp. 285-301.
A. Böttcher and B. Silbermann, Introduction to large truncated Toeplitz matrices, Springer-Verlag, New York, 1998.
L. Brugnano and D. Trigiante, Solving ODE by Linear Multistep Methods: Initial and Boundary Value Methods, Gordon and Breach, Reading, UK, 1998.
T. F. Chan and K. R. Jackson, The use of iterative linear equation solvers in codes for large systems of stiff IVPs for ODEs, SIAM J. Sci. Stat. Comput., 7 (1986), pp. 378-417.
T. F. Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Stat. Comput., 9 (1988), pp. 766-771.
R. H. Chan and M. K. Ng, Conjugate gradient methods for Toeplitz systems, SIAM Review, 38:3 (1996), pp. 427-482.
R. H. Chan, M. K. Ng, and X. Jin, Circulant preconditioners for solving ordinary differential equations, in Structured matrices, D. Bini et al., eds., Nova Science Pub., to appear.
C. W. Gear and Y. Saad, Iterative solution of linear equations in ODE codes, SIAM J. Sci. Stat. Comput., 4 (1983), pp. 583-601.
E. Hairer and G. Wanner, Solving Ordinary Differentials Equations II. Stiff and Differential Algebraic Problems, Springer-Verlag, Berlin, 1991.
M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Stand., 49 (1952), pp. 409-436.
R. Horn and C. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1985.
J. D. Lambert, Numerical Methods for Ordinary Differential Systems, Wiley, Chichester, 1991.
N. M. Nachtigal, S. C. Reddy, and L. N. Trefethen, How fast are nonsymmetric matrix iterations?, SIAM J. Matr. Anal. Appl., 13 (1992), pp. 778-795.
Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7 (1986), pp. 856-869.
G. Strang, A proposal for Toeplitz matrix calculations, Stud. Appl. Math., 74 (1986), pp. 171-176.
E. E. Tyrtyshnikov, A unifying approach to some old and new theorems on distribution and clustering, Linear Algebra Appl., 232 (1996), 1-43.
H. A. van der Vorst, BICGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 10 (1992), pp. 631-644.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bertaccini, D., Ng, M.K. The Convergence Rate of Block Preconditioned Systems Arising from LMF-based ODE Codes. BIT Numerical Mathematics 41, 433–450 (2001). https://doi.org/10.1023/A:1021906926616
Issue Date:
DOI: https://doi.org/10.1023/A:1021906926616