Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Krylov approximations for matrix square roots in stiff boundary value problems

Author: Bernhard A. Schmitt
Journal: Math. Comp. 58 (1992), 191-212
MSC: Primary 65L10; Secondary 34A65, 65F30
MathSciNet review: 1106980
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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.
  • [2] U. Ascher and R. Weiss, Collocation for singular perturbation problems II: Linear first order systems without turning points, Math. Comp. 43 (1984), 157-187. MR 744929 (86g:65138a)
  • [3] I. Babuška and V. Majer, The factorization method for the numerical solution of two point boundary value problems for linear ODE's, SIAM J. Numer. Anal. 24 (1987), 1301-1334. MR 917454 (88m:65114)
  • [4] A. Björck, A block QR algorithm for partitioning stiff differential systems, BIT 23 (1983), 329-345. MR 705000 (85a:65099)
  • [5] A. Björck and S. Hammarling, A Schur method for the square root of a matrix, Linear Algebra Appl. 52-53 (1983), 127-140. MR 709347 (84h:65043)
  • [6] P. N. Brown and A. C. Hindmarsh, Matrix-free methods for stiff systems of ODE's, SIAM J. Numer. Anal. 23 (1986), 610-638. MR 842647 (88g:65063)
  • [7] L. Dieci, M. R. Osborne, and R. D. Russell, A Riccati transformation method for solving linear BVPs. II: Computational aspects, SIAM J. Numer. Anal. 25 (1988), 1074-1092. MR 960867 (90b:65154)
  • [8] 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.
  • [9] C. W. Gear and Y. Saad, Iterative solution of linear equations in ODE codes, SIAM J. Sci. Statist. Comput. 4 (1983), 583-601. MR 725654 (85a:65104)
  • [10] G. H. Golub and C. F. van Loan, Matrix computations, North Oxford Academic, London, 1986.
  • [11] H. O. Kreiss, N. K. Nichols, and D. L. Brown, Numerical methods for stiff two-point boundary value problems, SIAM J. Numer. Anal. 23 (1986), 325-368. MR 831622 (87f:65090)
  • [12] R. M. M. Mattheij and G. W. Staarink, An efficient algorithm for solving general linear two-point BVPs, SIAM J. Sci. Statist. Comput. 5 (1984), 745-763. MR 765204 (86a:65076)
  • [13] G. H. Meyer, Continuous orthonormalization for boundary value problems, J. Comput. Phys. 62 (1986), 248-262. MR 825899 (87k:65101)
  • [14] J. D. Roberts, Linear model reduction and solution of the algebraic Riccati equation by use of the sign function, Internat. J. Control 32 (1980), 677-687. MR 595962 (81m:93042)
  • [15] Y. Saad, Variations on Arnoldi's method for computing eigenelements of large unsymmetric matrices, Linear Algebra Appl. 34 (1980), 269-295. MR 591435 (81m:65055)
  • [16] -, Krylov subspace methods for solving large unsymmetric linear systems, Math. Comp. 37 (1981), 105-126. MR 616364 (83j:65037)
  • [17] B. A. Schmitt, An algebraic approximation for the matrix exponential in singularly perturbed boundary value problems, SIAM J. Numer. Anal. 27 (1990), 51-66. MR 1034920 (91d:65109)
  • [18] B. A. Schmitt and K. H. Schild, Error estimation and mesh adaptation for an algebraic difference scheme in stiff BVPs, Numerical Treatment of Differential Equations, NUMDIFF-5 (K. Strehmel, ed.), Teubner-Texte Math., Band 121, Teubner, Stuttgart, Leipzig, 1991. MR 1128348
  • [19] B. T. Smith et al., Matrix eigensystem routines--EISPACK Guide, Lecture Notes in Comput. Sci., Springer, Berlin-New York, 1976.
  • [20] J. M. Varah, Alternate row and column elimination for solving linear systems, SIAM J. Numer. Anal. 13 (1976), 71-75. MR 0411199 (53:14937)
  • [21] H. F. Walker, Implementation of the GMRES method using Householder transformations, SIAM J. Sci. Statist. Comput. 9 (1988), 152-163. MR 922869 (88m:65056)
  • [22] D. M. Young, Iterative solution of large linear systems, Academic Press, 1971. MR 0305568 (46:4698)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65L10, 34A65, 65F30

Retrieve articles in all journals with MSC: 65L10, 34A65, 65F30

Additional Information

Keywords: Stiff boundary value problems, matrix square roots, Krylov subspace methods
Article copyright: © Copyright 1992 American Mathematical Society

American Mathematical Society