×

Low-rank updates of matrix functions. II: Rational Krylov methods. (English) Zbl 1469.65086

Summary: This work develops novel rational Krylov methods for updating a large-scale matrix function \(f(A)\) when \(A\) is subject to low-rank modifications. It extends our previous work in this context on polynomial Krylov methods, for which we present a simplified convergence analysis. For the rational case, our convergence analysis is based on an exactness result that is connected to work by Bernstein and Van Loan on rank-one updates of rational matrix functions. We demonstrate the usefulness of the derived error bounds for guiding the choice of poles in the rational Krylov method for the exponential function and Markov functions. Low-rank updates of the matrix sign function require additional attention; we develop and analyze a combination of our methods with a squaring trick for this purpose. A curious connection between such updates and existing rational Krylov subspace methods for Sylvester matrix equations is pointed out.
For Part I, see [SIAM J. Matrix Anal. Appl. 39, No. 1, 539–565 (2018; Zbl 1390.15024)].

MSC:

65F60 Numerical computation of matrix exponential and similar matrix functions
15A16 Matrix exponential and similar functions of matrices
65F99 Numerical linear algebra

Citations:

Zbl 1390.15024

Software:

RKToolbox; mftoolbox
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J.-E. Andersson, Approximation of \(e^{-x}\) by rational functions with concentrated negative poles, J. Approx. Theory, 32 (1981), pp. 85-95, https://doi.org/10.1016/0021-9045(81)90106-4. · Zbl 0471.41012
[2] A. I. Aptekarev, Sharp constants for rational approximations of analytic functions, Mat. Sb., 193 (2002), pp. 3-72, https://doi.org/10.1070/SM2002v193n01ABEH000619. · Zbl 1041.30014
[3] B. Beckermann, The condition number of real Vandermonde, Krylov and positive definite Hankel matrices, Numer. Math., 85 (2000), pp. 553-577. · Zbl 0965.15003
[4] B. Beckermann, An error analysis for rational Galerkin projection applied to the Sylvester equation, SIAM J. Numer. Anal., 49 (2011), pp. 2430-2450, https://doi.org/10.1137/110824590. · Zbl 1244.65057
[5] B. Beckermann, D. Kressner, and M. Schweitzer, Low-rank updates of matrix functions, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 539-565, https://doi.org/10.1137/17M1140108. · Zbl 1390.15024
[6] B. Beckermann and L. Reichel, Error estimation and evaluation of matrix functions via the Faber transform, SIAM J. Numer. Anal., 47 (2009), pp. 3849-3883, https://doi.org/10.1137/080741744. · Zbl 1204.65041
[7] B. Beckermann and A. Townsend, Bounds on the singular values of matrices with displacement structure, SIAM Rev., 61 (2019), pp. 319-344, https://doi.org/10.1137/19M1244433. · Zbl 1441.15005
[8] P. Benner, R.-C. Li, and N. Truhar, On the ADI method for Sylvester equations, J. Comput. Appl. Math., 233 (2009), pp. 1035-1045, https://doi.org/10.1016/j.cam.2009.08.108. · Zbl 1176.65050
[9] M. Benzi and P. Boito, Matrix functions in network analysis, GAMM-Mitt., 43 (2020), e202000012, https://doi.org/10.1002/gamm.202000012. · Zbl 1314.47020
[10] C. Berg and G. Forst, Potential Theory on Locally Compact Abelian Groups, Springer, Berlin, Heidelberg, 1975. · Zbl 0308.31001
[11] M. Berljafa, S. Elsworth, and S. Güttel, A Rational Krylov Toolbox for MATLAB, Tech. report 2014.56, Manchester Institute for Mathematical Sciences, The University of Manchester, 2014.
[12] D. S. Bernstein and C. F. Van Loan, Rational matrix functions and rank-1 updates, SIAM J. Matrix Anal. Appl., 22 (2000), pp. 145-154, https://doi.org/10.1137/S0895479898333636. · Zbl 0970.65046
[13] G. Beylkin, N. Coult, and M. J. Mohlenkamp, Fast spectral projection algorithms for density-matrix computations, J. Comput. Phys., 152 (1999), pp. 32-54. · Zbl 0945.65049
[14] J. Bloch, A. Frommer, B. Lang, and T. Wettig, 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
[15] A. Boriçi, On the Neuberger overlap operator, Phys. Lett. B, 453 (1999), pp. 46-53.
[16] M. Crouzeix and D. Kressner, A Bivariate Extension of the Crouzeix-Palencia Result with an Application to Fréchet Derivatives of Matrix Functions, preprint, https://arxiv.org/abs/2007.09784, 2020.
[17] V. Druskin and L. Knizhnerman, Extended Krylov subspaces: Approximation of the matrix square root and related functions, SIAM J. Matrix Anal. Appl., 19 (1998), pp. 755-771, https://doi.org/10.1137/S0895479895292400. · Zbl 0912.65022
[18] V. Druskin, L. Knizhnerman, and V. Simoncini, Analysis of the rational Krylov subspace and ADI methods for solving the Lyapunov equation, SIAM J. Numer. Anal., 49 (2011), pp. 1875-1898, https://doi.org/10.1137/100813257. · Zbl 1244.65060
[19] S. Elsworth and S. Güttel, The block rational Arnoldi method, SIAM J. Matrix Anal. Appl., 41 (2020), pp. 365-388, https://doi.org/10.1137/19M1245505. · Zbl 1441.65047
[20] J. van den Eshof, A. Frommer, Th. Lippert, K. Schilling, and H. A. van der Vorst, Numerical methods for the QCD overlap operator. I. Sign-function and error bounds, Comput. Phys. Commun., 146 (2002), pp. 203-224. · Zbl 1008.81508
[21] E. Estrada and D. J. Higham, Network properties revealed through matrix functions, SIAM Rev., 52 (2010), pp. 696-714, https://doi.org/10.1137/090761070. · Zbl 1214.05077
[22] A. Frommer, S. Güttel, and M. Schweitzer, Convergence of restarted Krylov subspace methods for Stieltjes functions of matrices, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 1602-1624, https://doi.org/10.1137/140973463. · Zbl 1316.65040
[23] M. I. Gil’, Perturbations of functions of diagonalizable matrices, Electron. J. Linear Algebra, 20 (2010), pp. 303-313, https://doi.org/10.13001/1081-3810.1375. · Zbl 1207.15020
[24] G. H. Golub and R. Underwood, The block Lanczos method for computing eigenvalues, in Mathematical Software, III (Proc. Sympos., Math. Res. Center, Univ. Wisconsin, Madison, WI, 1977), Publ. Math. Res. Center 39, Academic Press, New York, 1977, pp. 361-377. · Zbl 0407.68040
[25] A. A. Gonchar and E. A. Rakhmanov, Equilibrium distributions and the rate of rational approximation of analytic functions, Mat. Sb. (N.S.), 134 (1987), pp. 306-352, 447. · Zbl 0645.30026
[26] S. Güttel, Rational Krylov Methods for Operator Functions, Ph.D. thesis, Fakultät für Mathematik und Informatik der Technischen Universität Bergakademie Freiberg, 2010.
[27] S. Güttel, Rational Krylov approximation of matrix functions: Numerical methods and optimal pole selection, GAMM-Mitt., 36 (2013), pp. 8-31. · Zbl 1292.65043
[28] S. Güttel and L. Knizhnerman, A black-box rational Arnoldi variant for Cauchy-Stieltjes matrix functions, BIT, 53 (2013), pp. 595-616. · Zbl 1276.65026
[29] P. Henrici, Applied and Computational Complex Analysis, Vol. 2, John Wiley & Sons, New York, 1977. · Zbl 0363.30001
[30] N. J. Higham, Functions of Matrices: Theory and Computation, SIAM, Philadelphia, 2008, https://doi.org/10.1137/1.9780898717778. · Zbl 1167.15001
[31] M. Hochbruck and A. Ostermann, Exponential integrators, Acta Numer., 19 (2010), pp. 209-286. · Zbl 1242.65109
[32] C. Jagels and L. Reichel, Recursion relations for the extended Krylov subspace method, Linear Algebra Appl., 434 (2011), pp. 1716-1732. · Zbl 1211.65039
[33] L. Knizhnerman and V. Simoncini, A new investigation of the extended Krylov subspace method for matrix function evaluations, Numer. Linear Algebra Appl., 17 (2010), pp. 615-638. · Zbl 1240.65154
[34] I. Moret and P. Novati, RD-rational approximations of the matrix exponential, BIT, 44 (2004), pp. 595-615. · Zbl 1075.65062
[35] Y. Nakatsukasa and N. J. Higham, Stable and efficient spectral divide and conquer algorithms for the symmetric eigenvalue decomposition and the SVD, SIAM J. Sci. Comput., 35 (2013), pp. A1325-A1349, https://doi.org/10.1137/120876605. · Zbl 1326.65049
[36] P. P. Petrushev and V. A. Popov, Rational Approximation of Real Functions, Encyclopedia Math. Appl., Cambridge University Press, 1988. · Zbl 0644.41010
[37] L. Reichel, Newton interpolation at Leja points, BIT, 30 (1990), pp. 332-346. · Zbl 0702.65012
[38] J. D. Roberts, Linear model reduction and solution of the algebraic Riccati equation by use of the sign function, Internat. J. Control, 32 (1980), pp. 677-687. · Zbl 0463.93050
[39] Y. Saad, Analysis of some Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 29 (1992), pp. 209-228, https://doi.org/10.1137/0729014. · Zbl 0749.65030
[40] J. Sherman and W. J. Morrison, Adjustment of an inverse matrix corresponding to a change in one element of a given matrix, Ann. Math. Statist., 21 (1950), pp. 124-127. · Zbl 0037.00901
[41] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains, IEEE Signal Process. Mag., 30 (2013), pp. 83-98, https://doi.org/10.1109/MSP.2012.2235192.
[42] V. Simoncini, A new iterative method for solving large-scale Lyapunov matrix equations, SIAM J. Sci. Comput., 29 (2007), pp. 1268-1288, https://doi.org/10.1137/06066120X. · Zbl 1146.65038
[43] V. Simoncini, Computational methods for linear matrix equations, SIAM Rev., 58 (2016), pp. 377-441, https://doi.org/10.1137/130912839. · Zbl 1386.65124
[44] A. Skripka and A. Tomskova, Multilinear Operator Integrals, Lecture Notes in Math. 2250, Springer, Cham, 2019, https://doi.org/10.1007/978-3-030-32406-3. · Zbl 1458.47003
[45] M. Stoll, A literature survey of matrix methods for data science, GAMM-Mitt., 43 (2020), e202000013, https://doi.org/10.1002/gamm.202000013.
[46] J. van den Eshof and M. Hochbruck, Preconditioning Lanczos approximations to the matrix exponential, SIAM J. Sci. Comput., 27 (2006), pp. 1438-1457, https://doi.org/10.1137/040605461. · Zbl 1105.65051
[47] G. Zolotarev, Application of elliptic functions to the problem of functions which vary the least or the most from zero, Abh. St. Petersb., 30 (1877), pp. 1-59. · JFM 09.0343.02
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.