×

The Radau-Lanczos method for matrix functions. (English) Zbl 1371.65042

Summary: Analysis and development of restarted Krylov subspace methods for computing \(f(A){\boldsymbol b}\) have proliferated in recent years. We present an acceleration technique for such methods when applied to Stieltjes functions \(f\) and Hermitian positive definite matrices \(A\). This technique is based on a rank-one modification of the Lanczos matrix derived from a connection between the Lanczos process and Gauss-Radau quadrature. We henceforth refer to the technique paired with the standard Lanczos method for matrix functions as the Radau-Lanczos method for matrix functions. We develop properties of general rank-one updates, leading to a framework through which other such updates could be explored in the future. We also prove error bounds for the Radau-Lanczos method, which are used to prove the convergence of restarted versions. We further present a thorough investigation of the Radau-Lanczos method explaining why it routinely improves over the standard Lanczos method. This is confirmed by several numerical experiments, and we conclude that, in practical situations, the Radau-Lanczos method is superior in terms of iteration counts and timings, when compared to the standard Lanczos method.

MSC:

65F60 Numerical computation of matrix exponential and similar matrix functions
15B57 Hermitian, skew-Hermitian, and related matrices
15B48 Positive matrices and their generalizations; cones of matrices
65D32 Numerical quadrature and cubature formulas

Software:

mftoolbox
Full Text: DOI

References:

[1] M. Afanasjew, M. Eiermann, O. G. Ernst, and S. Güttel, {\it Implementation of a restarted Krylov subspace method for the evaluation of matrix functions}, Linear Algebra Appl., 429 (2008), pp. 229-314. · Zbl 1153.65042
[2] M. Benzi, E. Estrada, and C. Klymko, {\it Ranking hubs and authorities using matrix functions}, Linear Algebra Appl., 438 (2013), pp. 2447-2474. · Zbl 1258.05067
[3] J. C. R. Bloch, A. Frommer, B. Lang, and T. Wettig, {\it An iterative method to compute the sign function of a non-Hermitian matrix and its application to the overlap Dirac operator at nonzero chemical potential}, Comput. Phys. Commun., 177 (2007), pp. 933-943. · Zbl 1196.65085
[4] V. Druskin and L. Knizhnerman, {\it Extended Krylov subspaces: Approximation of the matrix square root and related functions}, SIAM J. Matrix Anal. Appl., 19 (1998), pp. 755-771. · Zbl 0912.65022
[5] M. Eiermann and O. G. Ernst, {\it A restarted Krylov subspace method for the evaluation of matrix functions}, SIAM J. Numer. Anal., 44 (2006), pp. 2481-2504. · Zbl 1129.65019
[6] M. Eiermann, O. G. Ernst, and S. Güttel, {\it Deflated restarting for matrix functions}, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 621-641. · Zbl 1264.65070
[7] J. v. Eshof, A. Frommer, T. Lippert, K. Schilling, and H. A. v. Vorst, {\it Numerical methods for the QCD overlap operator. I. Sign-function and error bounds}, Comput. Phys. Commun., 146 (2002), pp. 203-224. · Zbl 1008.81508
[8] E. Estrada and D. J. Higham, {\it Network properties revealed through matrix functions}, SIAM Rev., 52 (2010), pp. 696-714. · Zbl 1214.05077
[9] A. Frommer, S. Güttel, and M. Schweitzer, {\it Convergence of restarted Krylov subspace methods for Stieltjes functions of matrices}, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 1602-1624. · Zbl 1316.65040
[10] A. Frommer, S. Güttel, and M. Schweitzer, {\it Efficient and stable Arnoldi restarts for matrix functions based on quadrature}, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 661-683. · Zbl 1309.65050
[11] A. Frommer and M. Schweitzer, {\it Error bounds and estimates for Krylov subspace approximations of Stieltjes matrix functions}, BIT, 56 (2016), pp. 865-892. · Zbl 1353.65038
[12] W. Gautschi, {\it Gauss-Radau formulae for Jacobi and Laguerre weight functions}, Math. Comput. Simulation, 54 (2000), pp. 403-412. · Zbl 0981.41017
[13] G. H. Golub, {\it Some modified matrix eigenvalue problems}, SIAM Rev., 15 (1973), pp. 318-334. · Zbl 0254.65027
[14] G. H. Golub and G. Meurant, {\it Matrices, Moments and Quadrature with Applications}, Princeton University Press, Princeton, NJ, 2010. · Zbl 1217.65056
[15] S. Goossens and D. Roose, {\it Ritz and harmonic Ritz values and the convergence of FOM and GMRES}, Numer. Linear Algebra Appl., 6 (1999), pp. 281-293. · Zbl 0983.65034
[16] P. Henrici, {\it Applied and Computational Complex Analysis, Vol}. 2, Wiley, New York, 1977. · Zbl 0363.30001
[17] N. J. Higham, {\it Functions of Matrices: Theory and Computation}, SIAM, Philadelphia, 2008. · Zbl 1167.15001
[18] M. Hochbruck and C. Lubich, {\it On Krylov subspace approximations to the matrix exponential operator}, SIAM J. Numer. Anal., 34 (1997), pp. 1911-1925. · Zbl 0888.65032
[19] M. Hochbruck, C. Lubich, and H. Selhofer, {\it Exponential integrators for large systems of differential equations}, SIAM J. Sci. Comput., 19 (1998), pp. 1552-1574. · Zbl 0912.65058
[20] M. Hochbruck and A. Ostermann, {\it Exponential integrators}, Acta Numerica, 19 (2010), pp. 209-286. · Zbl 1242.65109
[21] M. Ilić, I. W. Turner, and D. P. Simpson, {\it A restarted Lanczos approximation to functions of a symmetric matrix}, IMA J. Numer. Anal., 30 (2010), pp. 1044-1061. · Zbl 1220.65052
[22] A. D. Kennedy, {\it Algorithms for dynamical fermions}, preprint, , 2006.
[23] D. G. Luenberger, {\it Linear and Nonlinear Programming}, 2nd ed., Adison-Wesley, Reading, MA, 1984. · Zbl 0571.90051
[24] C. C. Paige, B. N. Parlett, and H. A. v. Vorst, {\it Approximate solutions and eigenvalue bounds from Krylov subspaces}, Numer. Linear Algebra Appl., 2 (1995), pp. 115-133. · Zbl 0831.65036
[25] Y. Saad, {\it Analysis of some Krylov subspace approximations to the matrix exponential operator}, SIAM J. Numer. Anal., 29 (1992), pp. 209-228. · Zbl 0749.65030
[26] Y. Saad, {\it Iterative Methods for Sparse Linear Systems}, 2nd ed., SIAM, Philadelphia, 2003. · Zbl 1031.65046
[27] D. P. Simpson, {\it Krylov Subspace Methods for Approximating Functions of Symmetric Positive Definite Matrices with Applications to Applied Statistics and Anomalous Diffusion}, PhD thesis, School of Mathematical Sciences, Queensland University of Technology, Brisbane, Australia, 2008.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.