Krylov approximations for matrix square roots in stiff boundary value problems
HTML articles powered by AMS MathViewer
- by Bernhard A. Schmitt PDF
- Math. Comp. 58 (1992), 191-212 Request permission
Abstract:
Recently, we proposed an algebraic difference scheme, with extended stability properties, for linear boundary value problems involving stiff differential equations of first order. Here, an efficient approximation scheme is presented for matrix square roots, which provides the stabilization of that scheme in case of stiffness. It combines the use of low-rank matrix approximations from projections onto Krylov subspaces with an accelerated sign iteration for the matrix square root. The Krylov approximation, being accurate in eigenspaces with large eigenvalues, preserves the stability of the scheme, and the $O({n^3})$ square root computation need be performed only in lower dimension. Operation counts and numerical results show that the effort for the numerical scheme is essentially proportional to the number of stiff components, but not to the norm of the coefficient matrix. Approximation properties of low-rank Krylov matrices, which may be of independent interest, are analyzed.References
-
J. Albrecht, Quadratisch konvergente Iterationsverfahren zur Berechnung von ${A^{1/2}}$ und ${A^{ - 1}}$, Internat. Ser. Numer. Math., vol. 32, Birkhäuser, Basel-Stuttgart, 1976, pp. 9-15.
- U. Ascher and R. Weiss, Collocation for singular perturbation problems. II. Linear first order systems without turning points, Math. Comp. 43 (1984), no. 167, 157–187. MR 744929, DOI 10.1090/S0025-5718-1984-0744929-2
- I. Babuška and V. Majer, The factorization method for the numerical solution of two-point boundary value problems for linear ODEs, SIAM J. Numer. Anal. 24 (1987), no. 6, 1301–1334. MR 917454, DOI 10.1137/0724085
- Åke Björck, A block $QR$ algorithm for partitioning stiff differential systems, BIT 23 (1983), no. 3, 329–345. MR 705000, DOI 10.1007/BF01934462
- Ȧke Björck and Sven Hammarling, A Schur method for the square root of a matrix, Linear Algebra Appl. 52/53 (1983), 127–140. MR 709347, DOI 10.1016/0024-3795(83)80010-X
- Peter N. Brown and Alan C. Hindmarsh, Matrix-free methods for stiff systems of ODEs, SIAM J. Numer. Anal. 23 (1986), no. 3, 610–638. MR 842647, DOI 10.1137/0723039
- Luca Dieci, Michael R. Osborne, and Robert D. Russell, A Riccati transformation method for solving linear BVPs. II. Computational aspects, SIAM J. Numer. Anal. 25 (1988), no. 5, 1074–1092. MR 960867, DOI 10.1137/0725062 W. H. Enright and M. S. Kamel, Automatic partitioning of stiff systems and exploiting the resulting structure, ACM Trans. Math. Software 4 (1979), 127-136.
- C. W. Gear and Y. Saad, Iterative solution of linear equations in ODE codes, SIAM J. Sci. Statist. Comput. 4 (1983), no. 4, 583–601. MR 725654, DOI 10.1137/0904040 G. H. Golub and C. F. van Loan, Matrix computations, North Oxford Academic, London, 1986.
- Heinz-Otto Kreiss, N. K. Nichols, and David L. Brown, Numerical methods for stiff two-point boundary value problems, SIAM J. Numer. Anal. 23 (1986), no. 2, 325–368. MR 831622, DOI 10.1137/0723023
- R. M. M. Mattheij and G. W. M. Staarink, An efficient algorithm for solving general linear two-point BVP, SIAM J. Sci. Statist. Comput. 5 (1984), no. 4, 745–763. MR 765204, DOI 10.1137/0905053
- Gunter H. Meyer, Continuous orthonormalization for boundary value problems, J. Comput. Phys. 62 (1986), no. 1, 248–262. MR 825899, DOI 10.1016/0021-9991(86)90109-9
- J. D. Roberts, Linear model reduction and solution of the algebraic Riccati equation by use of the sign function, Internat. J. Control 32 (1980), no. 4, 677–687. MR 595962, DOI 10.1080/00207178008922881
- Y. Saad, Variations on Arnoldi’s method for computing eigenelements of large unsymmetric matrices, Linear Algebra Appl. 34 (1980), 269–295. MR 591435, DOI 10.1016/0024-3795(80)90169-X
- Y. Saad, Krylov subspace methods for solving large unsymmetric linear systems, Math. Comp. 37 (1981), no. 155, 105–126. MR 616364, DOI 10.1090/S0025-5718-1981-0616364-6
- Bernhard A. Schmitt, An algebraic approximation for the matrix exponential in singularly perturbed boundary value problems, SIAM J. Numer. Anal. 27 (1990), no. 1, 51–66. MR 1034920, DOI 10.1137/0727004
- Bernhard A. Schmitt and Karl-Heinz Schild, Error estimation and mesh adaptation for an algebraic difference scheme in stiff BVPs, Numerical treatment of differential equations (Halle, 1989) Teubner-Texte Math., vol. 121, Teubner, Stuttgart, 1991, pp. 152–161. MR 1128348 B. T. Smith et al., Matrix eigensystem routines—EISPACK Guide, Lecture Notes in Comput. Sci., Springer, Berlin-New York, 1976.
- J. M. Varah, Alternate row and column elimination for solving certain linear systems, SIAM J. Numer. Anal. 13 (1976), no. 1, 71–75. MR 411199, DOI 10.1137/0713008
- Homer F. Walker, Implementation of the GMRES method using Householder transformations, SIAM J. Sci. Statist. Comput. 9 (1988), no. 1, 152–163. MR 922869, DOI 10.1137/0909010
- David M. Young, Iterative solution of large linear systems, Academic Press, New York-London, 1971. MR 0305568
Additional Information
- © Copyright 1992 American Mathematical Society
- Journal: Math. Comp. 58 (1992), 191-212
- MSC: Primary 65L10; Secondary 34A65, 65F30
- DOI: https://doi.org/10.1090/S0025-5718-1992-1106980-7
- MathSciNet review: 1106980