# 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
##### Software:
Algorithm 432; CONTEST; Matlab; mftoolbox; testmatrix
Full Text:
##### References:
  Bapat, R.B.: Graphs and Matrices, Universitext, Springer. London; Hindustan Book Agency, New Dehli (2010) · Zbl 1215.05028  Bartels, RH; Stewart, GW, Algorithm 432: solution of the matrix equation $$AX+XB=C$$, Comm. ACM, 15, 820-826, (1972) · Zbl 1372.65121  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  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  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  Benzi, M; Klymko, C, Total communicability as a centrality measure, J. Complex Netw., 1, 124-149, (2013)  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  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  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  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  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  Estrada, E; Hatano, N; Benzi, M, The physics of communicability in complex networks, Phys. Rep., 514, 89-119, (2012)  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  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  Frommer, A; Simoncini, V; Schilders, WHA (ed.); Vorst, HA (ed.); Rommes, J (ed.), Matrix functions, (2008), Heidelberg  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  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  Gradshteyn, I.S., Ryzhik, I.M.: Table of Integrals, Series, and Products, 7th edn. Academic Press, New York (2007) · Zbl 1208.65001  Grasedyck, L, Existence and computation of low-rank approximations for large systems of tensor product structure, Computing, 72, 247-265, (2004) · Zbl 1058.65036  Güttel, S, Rational Krylov approximation of matrix functions: numerical methods and optimal pole selection, GAMM Mitt., 36, 8-31, (2013) · Zbl 1292.65043  Hackbusch, W, Numerical tensor calculus, Acta Numer., 23, 651-742, (2014) · Zbl 1396.65091  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  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  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  Higham, N.J.: Functions of Matrices—Theory and Computation. SIAM, Philadelphia (2008) · Zbl 1167.15001  Hochbruck, M; Lubich, C, On Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 34, 1911-1925, (1997) · Zbl 0888.65032  Hochbruck, M; Lubich, C, Exponential integrators for quantum-classical molecular dynamics, BIT Numer. Math., 39, 620-645, (1999) · Zbl 0985.81002  Hochbruck, M; Ostermann, A, Exponential integrators, Acta Numer., 19, 209-286, (2010) · Zbl 1242.65109  Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press, Cambridge (1991) · Zbl 0729.15001  Knizhnerman, L, Calculus of functions of unsymmetric matrices using arnoldi’s method, Comput. Math. Math. Phys., 31, 1-9, (1991) · Zbl 0774.65021  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  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  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  The MathWorks. Matlab 7.0. The Mathworks, Inc., Natick, MA (2014)  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  Ng, M.K.: Iterative Methods for Toeplitz Systems. Oxford University Press, Oxford (2004) · Zbl 1059.65031  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  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  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  Taylor, A; Higham, DJ, CONTEST: A controllable test matrix toolbox for MATLAB, ACM Trans. Math. Softw., 35, 26:1-26:17, (2009)  Widder, D.V.: The Laplace Transform. Princeton University Press, Princeton (1946) · Zbl 0060.24801  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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.6498558,"math_prob":0.8494813,"size":8682,"snap":"2021-04-2021-17","text_gpt3_token_len":2760,"char_repetition_ratio":0.14577092,"word_repetition_ratio":0.032206118,"special_character_ratio":0.35003456,"punctuation_ratio":0.28509718,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9785043,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-01-25T04:18:34Z\",\"WARC-Record-ID\":\"<urn:uuid:132a2871-1e8b-4a14-ae30-43472299411a>\",\"Content-Length\":\"63820\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:6b867a11-621d-4374-b84c-deb2226d845a>\",\"WARC-Concurrent-To\":\"<urn:uuid:67da0727-a9eb-44d1-bb53-b70501f629af>\",\"WARC-IP-Address\":\"141.66.194.2\",\"WARC-Target-URI\":\"https://zbmath.org/?q=an:06677832\",\"WARC-Payload-Digest\":\"sha1:T4ESSD53SYNGIVY3HA5ALW74C6FSOOGS\",\"WARC-Block-Digest\":\"sha1:FJ7T4YFIF273Y6MNMQHCS5QP5OLHMUHP\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-04/CC-MAIN-2021-04_segments_1610703564029.59_warc_CC-MAIN-20210125030118-20210125060118-00130.warc.gz\"}"}