2019
Journal article
Open Access
Inexact Arnoldi residual estimates and decay properties for functions of non-Hermitian matrices
Pozza S., Simoncini V.
Computational Mathematics Inexact Arnoldi algorithm Matrix functions FOS: Mathematics Computer Networks and Communications Banded matrices Decay bound Arnoldi algorithm Faber polynomials Banded matrice Faber polynomial 65F60 Mathematics - Numerical Analysis 65F10 Decay bounds Software Applied Mathematics Numerical Analysis (math.NA)
This paper derives a priori residual-type bounds for the Arnoldi approximation of a matrix function together with a strategy for setting the iteration accuracies in the inexact Arnoldi approximation of matrix functions. Such results are based on the decay behavior of the entries of functions of banded matrices. Specifically, a priori decay bounds for the entries of functions of banded non-Hermitian matrices will be exploited, using Faber polynomial approximation. Numerical experiments illustrate the quality of the results.
Source: BIT (Nord. Tidskr. Inf-Behandl.) 59 (2019): 969–986. doi:10.1007/s10543-019-00763-6
Publisher: Institutionen for informationsbehandling, Lunds Universitet., Lund, Svezia
[1] B. Beckermann. Image num´erique, GMRES et polynoˆmes de Faber. C. R. Acad. Sci. Paris, Ser. I, 340(11):855-860, 2005.
[2] B. Beckermann and L. Reichel. Error estimates and evaluation of matrix functions via the Faber transform. SIAM J. Numer. Anal., 47(5):3849-3883, Jan 2009.
[3] M. Benzi and P. Boito. Decay properties for functions of matrices over C∗-algebras. Linear Algebra and its Applications, 456:174-198, Sep 2014.
[4] M. Benzi, P. Boito, and N. Razouk. Decay properties of spectral projectors with applications to electronic structure. SIAM Review, 55(1):3-64, Feb 2013.
[5] M. Benzi and G. H. Golub. Bounds for the entries of matrix functions with applications to preconditioning. BIT Numerical Mathematics, 39(3):417-438, 1999.
[6] M. Benzi and N. Razouk. Decay bounds and O(n) algorithms for approximating functions of sparse matrices. Electronic Transactions on Numerical Analysis, 28:16-39, 2007.
[7] M. Benzi and V. Simoncini. Decay bounds for functions of Hermitian matrices with banded or Kronecker structure. SIAM Journal on Matrix Analysis and Applications, 36(3):1263- 1282, Jan 2015.
[8] S. Bernstein. Sur les fonctions absolument monotones. Acta Mathematica, 52(1):1-66, 1929.
[9] C. Canuto, V. Simoncini, and M. Verani. On the decay of the inverse of matrices that are sum of Kronecker products. Linear Algebra and its Applications, 452:21-39, Jul 2014.
[10] C. C. Cowen and E. Harel. An effective algorithm for computing the numerical range. https://www.math.iupui.edu/ ccowen/Downloads/33NumRange.html, 1995.
[11] M. Crouzeix. Numerical range and functional calculus in Hilbert space. Journal of Functional Analysis, 244(2):668-690, Mar 2007.
[12] N. Del Buono, L. Lopez, and R. Peluso. Computation of the exponential of large sparse skewsymmetric matrices. SIAM Journal on Scientific Computing, 27(1):278-293, Jan 2005.
[13] S. G. Demko. Inverses of band matrices and local convergence of spline projections. SIAM Journal on Numerical Analysis, 14(4):616-619, 1977.
[14] V. Druskin and L. Knizhnerman. Extended Krylov subspaces: approximation of the matrix square root and related functions. SIAM J. Matrix Anal. Appl., 19(3):755-771 (electronic), 1998.
[15] 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:1875-1898, 2011.
[16] V. Eijkhout and B. Polman. Decay rates of inverses of banded M-matrices that are near to Toeplitz matrices. Linear Algebra and its Applications, 109:247-277, 1988.
[17] S. W. Ellacott. Computation of Faber series with application to numerical polynomial approximation in the complex plane. Mathematics of Computation, 40(162):575-587, April 1983.
[18] R. Freund. On polynomial approximations to fa(z) = (z − a)−1 with complex a and some applications to certain non-hermitian matrices. Approx. Theory and Appl., 5:15-31, 1989.
[19] N. J. Higham. Functions of Matrices: Theory and Computation. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2008.
[20] A. Iserles. How large is the exponential of a banded matrix? New Zealand Journal of Mathematics, 29:177-192, 2000.
[21] L. Knizhnerman and V. Simoncini. Convergence analysis of the Extended Krylov Subspace Method for the Lyapunov equation. Numerische Mathematik, 118(3):567-586, 2011.
[22] N. Mastronardi, M. K.-P. Ng, and E. E. Tyrtyshnikov. Decay in functions of multiband matrices. SIAM Journal on Matrix Analysis and Applications, 31(5):2721-2737, Jan 2010.
[23] The MathWorks, Inc. MATLAB 7, r2013b edition, 2013.
[24] M. Merkle. Analytic Number Theory, Approximation Theory, and Special Functions: In Honor of Hari M. Srivastava, chapter Completely Monotone Functions: A Digest, pages 347-364. Springer New York, New York, NY, 2014.
[25] G. Meurant. A review on the inverse of symmetric tridiagonal and block tridiagonal matrices. SIAM Journal on Matrix Analysis and Applications, 13(3):707-728, 1992.
[26] S. Pozza and V. Simoncini. On the convergence of Krylov subspace solvers and decay pattern of banded matrices, 2016. In preparation.
[27] R. F. Rinehart. The equivalence of definitions of a matric function. The American Mathematical Monthly, 62(6):395-414, 1955.
[28] P. K. Suetin. Series of Faber polynomials. Gordon and Breach Science Publishers, 1998. Translated from the 1984 Russian original by E. V. Pankratiev [E. V. Pankrat′ev].
[29] J. van den Eshof, A. Frommer, T. Lippert, K. Schilling, and H. van der Vorst. Numerical methods for the QCD overlap operator. I: Sign-function and error bounds. Comput. Phys. Commun., 146(2):203-224, 2002.
[30] H. Wang. The Krylov Subspace Methods for the Computation of Matrix Exponentials. PhD thesis, Department of Mathematics, University of Kentucky, 2015.
[31] H. Wang and Q. Ye. Error Bounds for the Krylov Subspace Methods for Computations of Matrix Exponentials. ArXiv e-prints, Mar 2016. arXiv:1603.07358.
[32] Q. Ye. Error bounds for the Lanczos methods for approximating matrix exponentials. SIAM J. Numer. Anal., 51(1):68-87, Jan 2013.
[2] B. Beckermann and L. Reichel. Error estimates and evaluation of matrix functions via the Faber transform. SIAM J. Numer. Anal., 47(5):3849-3883, Jan 2009.
[3] M. Benzi and P. Boito. Decay properties for functions of matrices over C∗-algebras. Linear Algebra and its Applications, 456:174-198, Sep 2014.
[4] M. Benzi, P. Boito, and N. Razouk. Decay properties of spectral projectors with applications to electronic structure. SIAM Review, 55(1):3-64, Feb 2013.
[5] M. Benzi and G. H. Golub. Bounds for the entries of matrix functions with applications to preconditioning. BIT Numerical Mathematics, 39(3):417-438, 1999.
[6] M. Benzi and N. Razouk. Decay bounds and O(n) algorithms for approximating functions of sparse matrices. Electronic Transactions on Numerical Analysis, 28:16-39, 2007.
[7] M. Benzi and V. Simoncini. Decay bounds for functions of Hermitian matrices with banded or Kronecker structure. SIAM Journal on Matrix Analysis and Applications, 36(3):1263- 1282, Jan 2015.
[8] S. Bernstein. Sur les fonctions absolument monotones. Acta Mathematica, 52(1):1-66, 1929.
[9] C. Canuto, V. Simoncini, and M. Verani. On the decay of the inverse of matrices that are sum of Kronecker products. Linear Algebra and its Applications, 452:21-39, Jul 2014.
[10] C. C. Cowen and E. Harel. An effective algorithm for computing the numerical range. https://www.math.iupui.edu/ ccowen/Downloads/33NumRange.html, 1995.
[11] M. Crouzeix. Numerical range and functional calculus in Hilbert space. Journal of Functional Analysis, 244(2):668-690, Mar 2007.
[12] N. Del Buono, L. Lopez, and R. Peluso. Computation of the exponential of large sparse skewsymmetric matrices. SIAM Journal on Scientific Computing, 27(1):278-293, Jan 2005.
[13] S. G. Demko. Inverses of band matrices and local convergence of spline projections. SIAM Journal on Numerical Analysis, 14(4):616-619, 1977.
[14] V. Druskin and L. Knizhnerman. Extended Krylov subspaces: approximation of the matrix square root and related functions. SIAM J. Matrix Anal. Appl., 19(3):755-771 (electronic), 1998.
[15] 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:1875-1898, 2011.
[16] V. Eijkhout and B. Polman. Decay rates of inverses of banded M-matrices that are near to Toeplitz matrices. Linear Algebra and its Applications, 109:247-277, 1988.
[17] S. W. Ellacott. Computation of Faber series with application to numerical polynomial approximation in the complex plane. Mathematics of Computation, 40(162):575-587, April 1983.
[18] R. Freund. On polynomial approximations to fa(z) = (z − a)−1 with complex a and some applications to certain non-hermitian matrices. Approx. Theory and Appl., 5:15-31, 1989.
[19] N. J. Higham. Functions of Matrices: Theory and Computation. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2008.
[20] A. Iserles. How large is the exponential of a banded matrix? New Zealand Journal of Mathematics, 29:177-192, 2000.
[21] L. Knizhnerman and V. Simoncini. Convergence analysis of the Extended Krylov Subspace Method for the Lyapunov equation. Numerische Mathematik, 118(3):567-586, 2011.
[22] N. Mastronardi, M. K.-P. Ng, and E. E. Tyrtyshnikov. Decay in functions of multiband matrices. SIAM Journal on Matrix Analysis and Applications, 31(5):2721-2737, Jan 2010.
[23] The MathWorks, Inc. MATLAB 7, r2013b edition, 2013.
[24] M. Merkle. Analytic Number Theory, Approximation Theory, and Special Functions: In Honor of Hari M. Srivastava, chapter Completely Monotone Functions: A Digest, pages 347-364. Springer New York, New York, NY, 2014.
[25] G. Meurant. A review on the inverse of symmetric tridiagonal and block tridiagonal matrices. SIAM Journal on Matrix Analysis and Applications, 13(3):707-728, 1992.
[26] S. Pozza and V. Simoncini. On the convergence of Krylov subspace solvers and decay pattern of banded matrices, 2016. In preparation.
[27] R. F. Rinehart. The equivalence of definitions of a matric function. The American Mathematical Monthly, 62(6):395-414, 1955.
[28] P. K. Suetin. Series of Faber polynomials. Gordon and Breach Science Publishers, 1998. Translated from the 1984 Russian original by E. V. Pankratiev [E. V. Pankrat′ev].
[29] J. van den Eshof, A. Frommer, T. Lippert, K. Schilling, and H. van der Vorst. Numerical methods for the QCD overlap operator. I: Sign-function and error bounds. Comput. Phys. Commun., 146(2):203-224, 2002.
[30] H. Wang. The Krylov Subspace Methods for the Computation of Matrix Exponentials. PhD thesis, Department of Mathematics, University of Kentucky, 2015.
[31] H. Wang and Q. Ye. Error Bounds for the Krylov Subspace Methods for Computations of Matrix Exponentials. ArXiv e-prints, Mar 2016. arXiv:1603.07358.
[32] Q. Ye. Error bounds for the Lanczos methods for approximating matrix exponentials. SIAM J. Numer. Anal., 51(1):68-87, Jan 2013.
Metrics
Back to previous page
BibTeX entry
@article{oai:it.cnr:prodotti:434144,
title = {Inexact Arnoldi residual estimates and decay properties for functions of non-Hermitian matrices},
author = {Pozza S. and Simoncini V.},
publisher = {Institutionen for informationsbehandling, Lunds Universitet., Lund, Svezia},
doi = {10.1007/s10543-019-00763-6 and 10.48550/arxiv.1605.01595},
journal = {BIT (Nord. Tidskr. Inf-Behandl.)},
volume = {59},
pages = {969–986},
year = {2019}
}
0000-0003-1529-8420
