Skip to main content
SpringerLink
Log in

Superlinear convergence of the rational Arnoldi method for the approximation of matrix functions

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Abstract

A superlinear convergence bound for rational Arnoldi approximations to functions of matrices is derived. This bound generalizes the well-known superlinear convergence bound for the conjugate gradient method to more general functions with finite singularities and to rational Krylov spaces. A constrained equilibrium problem from potential theory is used to characterize a max-min quotient of a nodal rational function underlying the rational Arnoldi approximation, where an additional external field is required for taking into account the poles of the rational Krylov space. The resulting convergence bound is illustrated at several numerical examples, in particular, the convergence of the extended Krylov method for the matrix square root.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Beckermann, B.: A note on the convergence of Ritz values for sequences of matrices. Technical Report ANO 408, Labo Paul Painlevé, Université de Lille I, France (2000)

  2. Beckermann B.: On a conjecture of E.A. Rakhmanov. Constr. Approx. 16, 427–448 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  3. Beckermann, B.: Discrete orthogonal polynomials and superlinear convergence of Krylov subspace methods in numerical linear algebra. In: Marcellan, F., Van Assche, W. (eds.) Orthogonal Polynomials and Special Functions. Lecture Notes in Mathematics, vol. 1883, pp. 119–185. Springer, Berlin (2006)

  4. Beckermann B., Gryson A.: Extremal rational functions on symmetric discrete sets and superlinear convergence of the ADI method. Constr. Approx. 32, 393–428 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  5. Beckermann B., Güttel S., Vandebril R.: On the convergence of rational Ritz values. SIAM J. Matrix Anal. Appl. 31, 1740–1774 (2010)

    Article  MATH  Google Scholar 

  6. Beckermann B., Kuijlaars A.B.J.: On the sharpness of an asymptotic error estimate for conjugate gradients. BIT 41, 856–867 (2001)

    Article  MathSciNet  Google Scholar 

  7. Beckermann B., Kuijlaars A.B.J.: Superlinear convergence of conjugate gradients. SIAM J. Numer. Anal. 39, 300–329 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  8. Beckermann B., Kuijlaars A.B.J.: Superlinear CG convergence for special right-hand sides. Electron. Trans. Numer. Anal. 14, 1–19 (2002)

    MathSciNet  MATH  Google Scholar 

  9. Beckermann B., Reichel L.: Error estimation and evaluation of matrix functions via the Faber transform. SIAM J. Numer. Anal. 47, 3849–3883 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  10. Bultheel, A., González-Vera, P., Hendriksen, E., Njåstad, O.: Orthogonal rational functions. In: Cambridge Monographs on Applied and Computational Mathematics, vol. 5. Cambridge University Press, Cambridge (1999)

  11. Buyarov V., Rakhmanov E.A.: Families of equilibrium measures with external field on the real axis. Sb. Math. 190, 791–802 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  12. Calvetti D., Reichel L., Zhang Q.: Iterative exponential filtering for large discrete ill-posed problems. Numer. Math. 83, 535–556 (1999)

    MathSciNet  MATH  Google Scholar 

  13. Coussement J., Van Assche W.: A continuum limit of relativistic Toda lattice: asymptotic theory of discrete Laurent orthogonal polynomials with varying recurrence coefficients. J. Phys. A 38, 3337–3366 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  14. Deckers, K., Bultheel, A.: Rational Krylov sequences and orthogonal rational functions. Tech. Rep. TW499, Katholieke Universiteit Leuven, Departement Computerwetenschappen (2008)

  15. Dragnev P.D., Saff E.B.: Constrained energy problems with applications to orthogonal polynomials of a discrete variable. Journal d’Analyse Mathématique 72, 223–259 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  16. Driscoll T.A., Toh K.-C., Trefethen L.N.: From potential theory to matrix iterations in six steps. SIAM Rev. 40, 547–578 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  17. Druskin V., Knizhnerman L.: Two polynomial methods of calculating functions of symmetric matrices. USSR Comput. Maths. Math. Phys. 29, 112–121 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  18. Druskin V., Knizhnerman L.: Extended Krylov subspaces: approximation of the matrix square root and related functions. SIAM J. Matrix Anal. Appl. 19, 775–778 (1998)

    Article  MathSciNet  Google Scholar 

  19. Druskin V., Lieberman C., Zaslavsky M.: On adaptive choice of shifts in rational Krylov subspace reduction of evolutionary problems. SIAM J. Sci. Comput. 32, 2485–2496 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  20. Ericsson, T.: Computing functions of matrices using Krylov subspace methods. Technical Report, Department of Computer Science, Chalmers University of Technology, Sweden (1990)

  21. Gallopoulos E., Saad Y.: Efficient solution of parabolic equations by Krylov approximation methods. Numer. Linear Algebra Appl. 13, 1236–1264 (1992)

    MathSciNet  MATH  Google Scholar 

  22. Greenbaum A., Strakoš Z.: Predicting the behavior of finite precision Lanczos and conjugate gradient computations. SIAM J. Matrix Anal. Appl. 13, 121–137 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  23. Gryson, A.: Minimisation d’énergie sous contraintes. Applications en algèbre linéaire et en contrôle linéaire, PhD Thesis, University of Lille (2009)

  24. Güttel, S.: Rational Krylov methods for operator functions. PhD Thesis, Technische Universität Bergakademie Freiberg (2010)

  25. Güttel, S., Knizhnerman, L.: Automated parameter selection for rational Arnoldi approximation of Markov functions. Proc. Appl. Math. Mech. (2011, to appear)

  26. Helsen S., Kuijlaars A.B.J., Van Barel M.: Convergence of the isometric Arnoldi process. SIAM J. Matrix Anal. Appl. 26, 782–809 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  27. Higham N.J.: Functions of Matrices: Theory and Computation. SIAM, Philadelphia (2008)

    Book  MATH  Google Scholar 

  28. Kac M., Murdock W.L., Szegő G.: On the eigenvalues of certain Hermitian forms. Indiana Univ. Math. J. 2, 767–800 (1953)

    Article  MATH  Google Scholar 

  29. Knizhnerman L., Simoncini V.: A new investigation of the extended Krylov subspace method for matrix function evaluations. Numer. Linear Algebra Appl. 17, 615–638 (2010)

    MathSciNet  MATH  Google Scholar 

  30. Knizhnerman L., Simoncini V.: Convergence analysis of the extended Krylov subspace method for the Lyapunov equation. Numer. Math. 118, 567–586 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  31. Kuijlaars A.B.J.: Which eigenvalues are found by the Lanczos method?. SIAM J. Matrix Anal. Appl. 22, 306–321 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  32. Kuijlaars A.B.J.: Convergence analysis of Krylov subspace iterations with methods from potential theory. SIAM Rev. 48, 3–40 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  33. Lanczos C.: An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Res. Nat. Bur. Standards 45, 225–280 (1950)

    MathSciNet  Google Scholar 

  34. Meurant G., Strakoš Z.: The Lanczos and conjugate gradient algorithms in finite precision arithmetic. Acta Numer. 15, 471–542 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  35. Nikishin, E.M., Sorokin, V.N.: Rational approximations and orthogonality. Transl. Amer. Math. Soc., vol. 92, Providence (1991)

  36. Parlett B.N.: The Symmetric Eigenvalue Problem. Prentice-Hall, Englewood Cliffs (1980)

    MATH  Google Scholar 

  37. Rakhmanov E.A.: Equilibrium measure and the distribution of zeros on the extremal polynomials of a discrete variable. Sb. Math. 187, 1213–1228 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  38. Ruhe A.: Rational Krylov sequence methods for eigenvalue computation. Lin. Alg. Appl. 58, 391–405 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  39. Ruhe, A.: Rational Krylov algorithms for nonsymmetric eigenvalue problems. In: Golub, G.H., Greenbaum, A., Luskin, M. (eds.) Recent Advances in Iterative Methods. IMA Volumes in Mathematics and its Applications, pp. 149–164. Springer, New York (1994)

  40. Saad Y.: Analysis of some Krylov subspace approximations to the exponential operator. SIAM J. Numer. Anal. 29, 209–228 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  41. Saad Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. SIAM, Philadelphia (2003)

    Book  MATH  Google Scholar 

  42. Saff E.B., Totik V.: Logarithmic Potentials with External Fields. Springer, Berlin (1997)

    MATH  Google Scholar 

  43. Walsh, J.L.: Interpolation and Approximation by Rational Functions in the Complex Domain, 5th edn. Amer. Math. Soc., Providence (1969)

Download references

Author information

Authors and Affiliations

  1. Laboratoire Painlevé UMR 8524, UFR Mathématiques, Université des Sciences et Technologies de Lille, 59655, Villeneuve d’Ascq Cedex, France

    Bernhard Beckermann

  2. Section de mathématiques, Université de Genève, 1211, Geneva, Switzerland

    Stefan Güttel

Authors
  1. Bernhard Beckermann
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Stefan Güttel
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bernhard Beckermann.

Additional information

The work of the second author was partially supported by the Swiss National Science Foundation.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Beckermann, B., Güttel, S. Superlinear convergence of the rational Arnoldi method for the approximation of matrix functions. Numer. Math. 121, 205–236 (2012). https://doi.org/10.1007/s00211-011-0434-8

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00211-011-0434-8

Mathematics Subject Classification (2010)

Search

Navigation