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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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)
Beckermann B.: On a conjecture of E.A. Rakhmanov. Constr. Approx. 16, 427–448 (2000)
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)
Beckermann B., Gryson A.: Extremal rational functions on symmetric discrete sets and superlinear convergence of the ADI method. Constr. Approx. 32, 393–428 (2010)
Beckermann B., Güttel S., Vandebril R.: On the convergence of rational Ritz values. SIAM J. Matrix Anal. Appl. 31, 1740–1774 (2010)
Beckermann B., Kuijlaars A.B.J.: On the sharpness of an asymptotic error estimate for conjugate gradients. BIT 41, 856–867 (2001)
Beckermann B., Kuijlaars A.B.J.: Superlinear convergence of conjugate gradients. SIAM J. Numer. Anal. 39, 300–329 (2001)
Beckermann B., Kuijlaars A.B.J.: Superlinear CG convergence for special right-hand sides. Electron. Trans. Numer. Anal. 14, 1–19 (2002)
Beckermann B., Reichel L.: Error estimation and evaluation of matrix functions via the Faber transform. SIAM J. Numer. Anal. 47, 3849–3883 (2009)
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)
Buyarov V., Rakhmanov E.A.: Families of equilibrium measures with external field on the real axis. Sb. Math. 190, 791–802 (1999)
Calvetti D., Reichel L., Zhang Q.: Iterative exponential filtering for large discrete ill-posed problems. Numer. Math. 83, 535–556 (1999)
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)
Deckers, K., Bultheel, A.: Rational Krylov sequences and orthogonal rational functions. Tech. Rep. TW499, Katholieke Universiteit Leuven, Departement Computerwetenschappen (2008)
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)
Driscoll T.A., Toh K.-C., Trefethen L.N.: From potential theory to matrix iterations in six steps. SIAM Rev. 40, 547–578 (1998)
Druskin V., Knizhnerman L.: Two polynomial methods of calculating functions of symmetric matrices. USSR Comput. Maths. Math. Phys. 29, 112–121 (1989)
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)
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)
Ericsson, T.: Computing functions of matrices using Krylov subspace methods. Technical Report, Department of Computer Science, Chalmers University of Technology, Sweden (1990)
Gallopoulos E., Saad Y.: Efficient solution of parabolic equations by Krylov approximation methods. Numer. Linear Algebra Appl. 13, 1236–1264 (1992)
Greenbaum A., Strakoš Z.: Predicting the behavior of finite precision Lanczos and conjugate gradient computations. SIAM J. Matrix Anal. Appl. 13, 121–137 (1992)
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)
Güttel, S.: Rational Krylov methods for operator functions. PhD Thesis, Technische Universität Bergakademie Freiberg (2010)
Güttel, S., Knizhnerman, L.: Automated parameter selection for rational Arnoldi approximation of Markov functions. Proc. Appl. Math. Mech. (2011, to appear)
Helsen S., Kuijlaars A.B.J., Van Barel M.: Convergence of the isometric Arnoldi process. SIAM J. Matrix Anal. Appl. 26, 782–809 (2005)
Higham N.J.: Functions of Matrices: Theory and Computation. SIAM, Philadelphia (2008)
Kac M., Murdock W.L., Szegő G.: On the eigenvalues of certain Hermitian forms. Indiana Univ. Math. J. 2, 767–800 (1953)
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)
Knizhnerman L., Simoncini V.: Convergence analysis of the extended Krylov subspace method for the Lyapunov equation. Numer. Math. 118, 567–586 (2011)
Kuijlaars A.B.J.: Which eigenvalues are found by the Lanczos method?. SIAM J. Matrix Anal. Appl. 22, 306–321 (2000)
Kuijlaars A.B.J.: Convergence analysis of Krylov subspace iterations with methods from potential theory. SIAM Rev. 48, 3–40 (2006)
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)
Meurant G., Strakoš Z.: The Lanczos and conjugate gradient algorithms in finite precision arithmetic. Acta Numer. 15, 471–542 (2006)
Nikishin, E.M., Sorokin, V.N.: Rational approximations and orthogonality. Transl. Amer. Math. Soc., vol. 92, Providence (1991)
Parlett B.N.: The Symmetric Eigenvalue Problem. Prentice-Hall, Englewood Cliffs (1980)
Rakhmanov E.A.: Equilibrium measure and the distribution of zeros on the extremal polynomials of a discrete variable. Sb. Math. 187, 1213–1228 (1996)
Ruhe A.: Rational Krylov sequence methods for eigenvalue computation. Lin. Alg. Appl. 58, 391–405 (1984)
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)
Saad Y.: Analysis of some Krylov subspace approximations to the exponential operator. SIAM J. Numer. Anal. 29, 209–228 (1992)
Saad Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. SIAM, Philadelphia (2003)
Saff E.B., Totik V.: Logarithmic Potentials with External Fields. Springer, Berlin (1997)
Walsh, J.L.: Interpolation and Approximation by Rational Functions in the Complex Domain, 5th edn. Amer. Math. Soc., Providence (1969)
Author information
Authors and Affiliations
Corresponding author
Additional information
The work of the second author was partially supported by the Swiss National Science Foundation.
Rights 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
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00211-011-0434-8