×

New matrix function approximations and quadrature rules based on the Arnoldi process. (English) Zbl 1464.65043

Summary: The Arnoldi process can be applied to inexpensively approximate matrix functions of the form \(f ( A ) v\) and matrix functionals of the form \(v^\ast ( f ( A ) )^\ast g ( A ) v\), where \(A\) is a large square non-Hermitian matrix, \(v\) is a vector, and the superscript \(^\ast\) denotes transposition and complex conjugation. Here \(f\) and \(g\) are analytic functions that are defined in suitable regions in the complex plane. This paper reviews available approximation methods and describes new ones that provide higher accuracy for essentially the same computational effort by exploiting available, but generally not used, moment information. Numerical experiments show that in some cases the modifications of the Arnoldi decompositions proposed can improve the accuracy of \(v^\ast ( f ( A ) )^\ast g ( A ) v\) about as much as performing an additional step of the Arnoldi process.

MSC:

65F60 Numerical computation of matrix exponential and similar matrix functions
15A16 Matrix exponential and similar functions of matrices
65D32 Numerical quadrature and cubature formulas

Software:

hlib; blgaussexp
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Golub, G. H.; Van Loan, C. F., Matrix Computations (2013), Johns Hopkins University Press · Zbl 1268.65037
[2] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), SIAM: SIAM Philadelphia · Zbl 1002.65042
[3] Higham, N. J., Functions of Matrices (2008), SIAM: SIAM Philadelphia · Zbl 1167.15001
[4] Hochbruck, M.; Lubich, C., On Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 34, 1911-1925 (1997) · Zbl 0888.65032
[5] Benzi, M.; Klymko, C., Total communicability as a centrality measure, J. Complex Netw., 1, 1-26 (2013)
[6] Calvetti, D.; Kim, S.; Reichel, L., Quadrature rules based on the Arnoldi process, SIAM J. Matrix Anal. Appl., 26, 765-781 (2005) · Zbl 1078.65019
[7] Calvetti, D.; Reichel, L., Lanczos-based exponential filtering for discrete ill-posed problems, Numer. Algorithms, 29, 45-65 (2002) · Zbl 0997.65068
[8] De la Cruz Cabrera, O.; Matar, M.; Reichel, L., Analysis of directed networks vis the matrix exponential, J. Comput. Appl. Math., 355, 182-192 (2019) · Zbl 1417.90041
[9] Druskin, V.; Knizhnerman, L.; Zaslavsky, M., Solution of large scale evolutionary problems using rational Krylov subspaces with optimized shifts, SIAM J. Sci. Comput., 31, 3760-3780 (2009) · Zbl 1204.65042
[10] Gallopoulos, E.; Saad, Y., Efficient solution of parabolic equations by Krylov approximation methods, SIAM J. Sci. Stat. Comput., 13, 1236-1264 (1992) · Zbl 0757.65101
[11] Saad, Y., Analysis of some Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 29, 209-228 (1992) · Zbl 0749.65030
[12] Beckermann, B.; Reichel, L., Error estimation and evaluation of matrix functions vis the Faber transform, SIAM J. Numer. Anal., 47, 3848-3883 (2009) · Zbl 1204.65041
[13] Freund, R. W.; Hochbruck, M., Gauss quadratures associated with the Arnoldi process and the Lanczos algorithm, (Moonen, M. S.; Golub, G. H.; De Moor, B. L.R., Linear Algebra for Large Scale and Real Time Application (1993), Kluwer: Kluwer Dordrecht), 377-380
[14] Druskin, V. L.; Knizhnerman, L. A., Two polynomial methods for the computation of functions of symmetric matrices, USSR Comput. Math. Math. Phys., 29, 112-121 (1989) · Zbl 0719.65035
[15] Börm, S., Efficient Numerical Methods for Non-Local Operators: \( \mathcal{H}^2\)-Matrix Compression, Algorithms and Analysis. Vol. 14 (2010), European Mathematical Society · Zbl 1208.65037
[16] H2Lib, http://www.h2lib.org/, 2015-2020.
[17] Strakoš, Z.; Tichý, P., On efficient numerical approximation of the bilinear form \(c^\ast A^{- 1} b\), SIAM J. Sci. Comput., 33, 565-587 (2011) · Zbl 1227.65033
[18] Fika, P.; Mitrouli, M.; Roupa, P., Estimates for the bilinear form \(x^T A^{- 1} y\) with applications to linear algebra problems, Electron. Trans. Numer. Anal., 43, 70-89 (2014) · Zbl 1302.65100
[19] Alqahtani, H.; Reichel, L., Simplified anti-Gauss quadrature rules with applications in linear algebra, Numer. Algorithms, 77, 577-602 (2018) · Zbl 1390.41036
[20] Eshghi, N.; Reichel, L.; Spalević, M., Enhanced matrix function approximation, Electron. Trans. Numer. Anal., 47, 197-205 (2017) · Zbl 1392.65019
[21] Fenu, C.; Martin, D.; Reichel, L.; Rodriguez, G., Block Gauss and anti-Gauss quadrature with application to networks, SIAM J. Matrix Anal. Appl., 34, 1655-1684 (2013) · Zbl 1425.65063
[22] Golub, G. H.; Meurant, G., Matrices, Moments and Quadrature with Applications (2010), Princeton University Press: Princeton University Press Princeton · Zbl 1217.65056
[23] Brezinski, C.; Fika, P.; Mitrouli, M., Moments of a linear operator on a Hilbert space, with applications to the trace of the inverse of matrices and the solution of equations, Numer. Linear Algebra Appl., 19, 937-953 (2012) · Zbl 1289.15014
[24] Brezinski, C.; Fika, P.; Mitrouli, M., Estimations of the trace of powers of positive self-adjoint operators by extrapolation of the moments, Electron. Trans. Numer. Anal., 39, 144-155 (2012) · Zbl 1287.65042
[25] Greengard, L.; Rokhlin, V., A new version of the fast multipole method for the Laplace equation in three dimensions, Acta Numer., 6, 229-269 (1997) · Zbl 0889.65115
[26] Paige, C. C.; Parlett, B. N.; Van der Vorst, H. A., Approximate solutions and eigenvalue bounds from Krylov subspaces, Numer. Linear Algebra Appl., 2, 115-133 (1995) · Zbl 0831.65036
[27] van den Eshof, J.; Frommer, A.; Lippert, T.; Schilling, K.; van der Vorst, H. A., Numerical methods for the QCD overlap operator, I. Sign-function and error bounds, Comput. Phys. Comm., 146, 203-224 (2002) · Zbl 1008.81508
[28] Frommer, A.; Lund, K.; Szyld, D. B., Block Krylov subspace methods for functions of matrices II: Modified block FOM, SIAM J. Matrix Anal. Appl., 41, 804-837 (2020) · Zbl 1441.65051
[29] Frommer, A.; Lund, K.; Schweitzer, M.; Szyld, D. B., The Radau-Lanczos method for matrix functions, SIAM J. Matrix Anal. Appl., 38, 710-732 (2017) · Zbl 1371.65042
[30] Wonham, W. M., Linear Multivariate Control: A Geometric Approach (1985), Springer: Springer New York · Zbl 0609.93001
[31] Calvetti, D.; Lewis, B.; Reichel, L., On the selection of poles in the single input pole placement problem, Linear Algebra Appl., 302-303, 331-345 (1999) · Zbl 0986.93033
[32] Mehrmann, V.; Xu, H., An analysis of the pole placement problem. I. The single-input case, Electron. Trans. Numer. Anal., 4, 89-105 (1996) · Zbl 0890.65036
[33] Saad, Y., Projection and deflation methods for partial pole assignment in linear state feedback, IEEE Trans. Automat. Control, AC-33, 290-297 (1988) · Zbl 0641.93031
[34] Benzi, M.; Boito, P., Matrix functions in network analysis, GAMM-Mitt., 43, Article e202000012 pp. (2020)
[35] Estrada, E.; Higham, D. J., Network properties revealed through matrix functions, SIAM Rev., 52, 696-714 (2010) · Zbl 1214.05077
[36] Biological Networks Data Sets of Newcastle University. Available at http://www.biological-networks.org/.
[37] Marcelino, J.; Kaiser, M., Critical paths in a metapopulation model of H1N1: Effiently delaying influenza spreading through flight cancellation, PLoS Curr., 4 (2012), e4f8c9a2e1fca8
[38] Du, K.; Duintjer Tebbens, J.; Meurant, G., Any admissible harmonic Ritz value set is possible for GMRES, Electron. Trans. Numer. Anal., 47, 37-56 (2017) · Zbl 1372.65107
[39] Schweitzer, M., Any finite convergence curve is possible in the initial iterations of restarted FOM, Electron. Trans. Numer. Anal., 45, 133-145 (2016) · Zbl 1338.65086
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.