×

zbMATH — the first resource for mathematics

Approximation of functions of large matrices with Kronecker structure. (English) Zbl 1365.65134
This paper derives a computational strategy – based on Krylov methods – to evaluate matrix functions \(f({\mathcal A}) b\) effectively and efficiently where \({\mathcal A} = M_1 \otimes I + I \otimes M_2\) is a two term sum of Kronecker products, \(f\) is a regular function and \(b\) represents a low rank vectorized matrix. Specific examples involve derivations or numerical tests and comparisons with earlier methods for square root functions, exponential functions, the matrix inverse function, matrix sine and cosine functions, graph and network analyses, and for completely monotonic functions. Some convergence results are included, as well as a guide on how to deal similarly with multiterm Kronecker sums. The numerical experiments show the savings in memory and computer time when exploiting a Kronecker sum structure.

MSC:
65F60 Numerical computation of matrix exponential and similar matrix functions
65F50 Computational methods for sparse matrices
65D15 Algorithms for approximation of functions
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Bapat, R.B.: Graphs and Matrices, Universitext, Springer. London; Hindustan Book Agency, New Dehli (2010) · Zbl 1215.05028
[2] Bartels, RH; Stewart, GW, Algorithm 432: solution of the matrix equation \(AX+XB=C\), Comm. ACM, 15, 820-826, (1972) · Zbl 1372.65121
[3] Beckermann, B, An error analysis for rational Galerkin projection applied to the Sylvester equation, SIAM J. Numer. Anal., 49, 2430-2450, (2011) · Zbl 1244.65057
[4] Beckermann, B; Kressner, D; Tobler, C, An error analysis of Galerkin projection methods for linear systems with tensor product structure, SIAM J, Numer. Anal., 51, 3307-3326, (2013) · Zbl 1287.65032
[5] Beckermann, B; Reichel, L, Error estimation and evaluation of matrix functions via the Faber transform, SIAM J. Numer. Anal., 47, 3849-3883, (2009) · Zbl 1204.65041
[6] Benzi, M; Klymko, C, Total communicability as a centrality measure, J. Complex Netw., 1, 124-149, (2013)
[7] Benzi, M; Simoncini, V, Decay bounds for functions of matrices with banded or Kronecker structure, SIAM J. Matrix Anal. Appl., 36-3, 1263-1282, (2015) · Zbl 1323.15005
[8] Druskin, V; Knizhnerman, L, Extended Krylov subspaces: approximation of the matrix square root and related functions, SIAM J. Matrix Anal. Appl., 19, 755-771, (1998) · Zbl 0912.65022
[9] Druskin, V; Knizhnerman, L; Simoncini, V, Analysis of the rational Krylov subspace and ADI methods for solving the Lyapunov equation, SIAM J. Numer. Anal., 49, 1875-1898, (2011) · Zbl 1244.65060
[10] 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
[11] Eiermann, M; Ernst, O, A restarted Krylov subspace method for the evaluation of matrix functions, SIAM J. Numer. Anal., 44, 2481-2504, (2006) · Zbl 1129.65019
[12] Estrada, E; Hatano, N; Benzi, M, The physics of communicability in complex networks, Phys. Rep., 514, 89-119, (2012)
[13] Frommer, A; Güttel, S; Schweitzer, M, Convergence of restarted Krylov subspace methods for Stieltjes functions of matrices, SIAM J. Matrix Anal. Appl, 35, 1602-1624, (2014) · Zbl 1316.65040
[14] Frommer, A; Güttel, S; Schweitzer, M, Efficient and stable Arnoldi restarts for matrix functions based on quadrature, SIAM J. Matrix Anal. Appl., 35, 661-683, (2014) · Zbl 1309.65050
[15] Frommer, A; Simoncini, V; Schilders, WHA (ed.); Vorst, HA (ed.); Rommes, J (ed.), Matrix functions, (2008), Heidelberg
[16] Gavrilyuk, IP; Hackbusch, W; Khoromskij, BN, \(\fancyscript{H}\)-matrix approximation for the operator exponential with applications, Numer. Math., 92, 83-111, (2002) · Zbl 1005.65113
[17] Gavrilyuk, IP; Hackbusch, W; Khoromskij, BN, Tensor-product approximation to the inverse and related operators in high-dimensional elliptic problems, Computing, 74, 131-157, (2005) · Zbl 1071.65032
[18] Gradshteyn, I.S., Ryzhik, I.M.: Table of Integrals, Series, and Products, 7th edn. Academic Press, New York (2007) · Zbl 1208.65001
[19] Grasedyck, L, Existence and computation of low-rank approximations for large systems of tensor product structure, Computing, 72, 247-265, (2004) · Zbl 1058.65036
[20] Güttel, S, Rational Krylov approximation of matrix functions: numerical methods and optimal pole selection, GAMM Mitt., 36, 8-31, (2013) · Zbl 1292.65043
[21] Hackbusch, W, Numerical tensor calculus, Acta Numer., 23, 651-742, (2014) · Zbl 1396.65091
[22] Hackbusch, W; Khoromskij, BN, Low-rank Kronecker-product approximation to multi-dimensional nonlocal operators. II: HKT representation of certain operators, Computing, 76, 203-225, (2006) · Zbl 1087.65050
[23] Hale, N; Higham, NJ; Trefethen, LN, Computing \(A^α \), \(\log (A)\), and related matrix functions by contour integrals, SIAM J. Numer. Anal., 46, 2505-2523, (2008) · Zbl 1176.65053
[24] Hansen, P.C., Nagy, J.G., O’Leary, D.P.: Deblurring Images: Matrices, Spectra, and Filtering. Society for Industrial and Applied Mathematics, Philadelphia (2006) · Zbl 1112.68127
[25] Higham, N.J.: Functions of Matrices—Theory and Computation. SIAM, Philadelphia (2008) · Zbl 1167.15001
[26] Hochbruck, M; Lubich, C, On Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 34, 1911-1925, (1997) · Zbl 0888.65032
[27] Hochbruck, M; Lubich, C, Exponential integrators for quantum-classical molecular dynamics, BIT Numer. Math., 39, 620-645, (1999) · Zbl 0985.81002
[28] Hochbruck, M; Ostermann, A, Exponential integrators, Acta Numer., 19, 209-286, (2010) · Zbl 1242.65109
[29] Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press, Cambridge (1991) · Zbl 0729.15001
[30] Knizhnerman, L, Calculus of functions of unsymmetric matrices using arnoldi’s method, Comput. Math. Math. Phys., 31, 1-9, (1991) · Zbl 0774.65021
[31] 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) · Zbl 1240.65154
[32] Knizhnerman, L; Simoncini, V, Convergence analysis of the extended Krylov subspace method for the Lyapunov equation, Numer. Math., 118, 567-586, (2011) · Zbl 1230.65055
[33] Kressner, D; Tobler, C, Krylov subspace methods for linear systems with tensor product structure, SIAM J. Matrix Anal. Appl., 31, 1688-1714, (2010) · Zbl 1208.65044
[34] The MathWorks. Matlab 7.0. The Mathworks, Inc., Natick, MA (2014)
[35] Moler, C; Loan, C, Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later, SIAM Rev., 45, 3-49, (2003) · Zbl 1030.65029
[36] Ng, M.K.: Iterative Methods for Toeplitz Systems. Oxford University Press, Oxford (2004) · Zbl 1059.65031
[37] Palitta, D., Simoncini, V., Matrix-equation-based strategies for convection-diffusion equations. pp. 1-19 (2015) doi:10.1007/s10543-015-0575-8 (to appear in BIT Numer. Math.) · Zbl 1341.65042
[38] V. Simoncini, Computational Methods for Linear Matrix Equations, Technical report, Alma Mater Studiorum—Università di Bologna (2013) (to appear in SIAM Review) · Zbl 1386.65124
[39] Simoncini, V; Druskin, V, Convergence analysis of projection methods for the numerical solution of large Lyapunov equations, SIAM J. Numer. Anal., 47, 828-843, (2009) · Zbl 1195.65058
[40] Taylor, A; Higham, DJ, CONTEST: A controllable test matrix toolbox for MATLAB, ACM Trans. Math. Softw., 35, 26:1-26:17, (2009)
[41] Widder, D.V.: The Laplace Transform. Princeton University Press, Princeton (1946) · Zbl 0060.24801
[42] Yang, C; Xu, J-M, Reliability of interconnection networks modeled by Cartesian product digraphs, Networks, 52, 202-205, (2008) · Zbl 1162.90416
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.