A shifted block FOM algorithm with deflated restarting for matrix exponential computations. (English) Zbl 1382.65126
Summary: The approximation of \(\exp(tA)B\), where \(A\) is a large matrix and \(B\) a block vector, is a key ingredient in many scientific and engineering computations. A powerful tool to manage the matrix exponential function is to resort to a suitable rational approximation, such as the Carathéodory-Fejér approximation, whose core reduces to solving some shifted linear systems with multiple right-hand sides. However, these shifted systems are often difficult to solve when \(tA\) has a large norm. In this paper, we propose to solve some alternatively shifted linear systems. The motivation is that the magnitudes of the poles of the rational approximation are often medium-sized, and they can be much smaller than the norm of \(tA\). We then introduce a shifted block full orthogonalization method (FOM) algorithm with deflated restarting for solving these alternatively shifted linear systems efficiently. Our method is advantageous when one has explicit access to \(A\), and \(A^{-1}\) can be computed directly. Theoretical results are given to show the rationale of the proposed strategy. The relationship between the approximations obtained from the shifted block FOM algorithm and the shifted block generalized minimal residual algorithm is also analyzed. Numerical experiments demonstrate the superiority of the proposed algorithm over many state-of-the-art algorithms for the matrix exponential.
MSC:
| 65F60 | Numerical computation of matrix exponential and similar matrix functions |
| 15A16 | Matrix exponential and similar functions of matrices |
Keywords:
matrix exponential; Carathéodory-Fejér approximation; shifted linear systems; multiple right-hand sides; full orthogonalization method; deflated restarting; algorithm; numerical experiment; generalized minimal residual algorithmReferences:
| [1] | Abdou, M.; Badr, A., On a method for solving an integral equation in the displacement contact problem, Appl. Math. Comput., 127, 65-78 (2002) · Zbl 1126.74472 |
| [2] | Al-Mohy, A.; Higham, N., Computing the action of the matrix exponential, with an application to exponential integrators, SIAM J. Sci. Comput., 33, 488-511 (2011) · Zbl 1234.65028 |
| [3] | Antoulas, A., Approximation of Large-Scale Dynamical Systems (2005), SIAM: SIAM Philadelphia · Zbl 1112.93002 |
| [4] | Archid, A.; Bentbib, A., Approximation of the matrix exponential operator by a structure-preserving block Arnoldi-type method, Appl. Numer. Math., 75, 37-47 (2014) · Zbl 1302.65116 |
| [5] | Baker, A.; Dennis, J.; Jessup, E., On improving linear solver performance: a block variant of GMRES, SIAM J. Sci. Comput., 27, 1608-1626 (2006) · Zbl 1099.65029 |
| [6] | Bakhos, T.; Saibaba, A. K.; Kitanidis, P. K., A fast algorithm for parabolic PDE-based inverse problems based on Laplace transforms and flexible Krylov solvers, J. Comput. Phys., 299, 940-954 (2015) · Zbl 1351.76047 |
| [7] | Baumann, M.; van Gijzen, M. B., Nested Krylov methods for shifted linear systems, SIAM J. Sci. Comput., 37, S90-S112 (2015) · Zbl 06502306 |
| [8] | Birk, S., Deflated Shifted Block Krylov Subspace Methods for Hermitian Positive Definite Matrices (2015), Bergische Universität Wuppertal, PhD thesis |
| [9] | Bouras, A.; Frayssé, V., Inexact matrix-vector products in Krylov methods for solving linear systems: a relaxation strategy, SIAM J. Matrix Anal. Appl., 26, 660-678 (2005) · Zbl 1075.65041 |
| [10] | Brown, P., A theoretical comparison of the Arnoldi and GMRES algorithms, SIAM J. Sci. Stat. Comput., 12, 58-78 (1991) · Zbl 0719.65022 |
| [11] | Carpenter, A.; Ruttan, A.; Varga, R., Extended numerical computations on the 1/9 conjecture in rational approximation theory, (Graves-Morris, P. R.; Saff, E. B.; Varga, R. S., Rational Approximation and Interpolation. Rational Approximation and Interpolation, Lecture Notes in Math., vol. 1105 (1984), Springer-Verlag: Springer-Verlag Berlin), 383-411 · Zbl 0553.41022 |
| [12] | Chan, R.; Jin, X., An Introduction to Iterative Toeplitz Solvers (2007), SIAM: SIAM Philadelphia · Zbl 1146.65028 |
| [13] | Darnell, D.; Morgan, R.; Wilcox, W., Deflated GMRES for systems with multiple shifts and multiple right-hand sides, Linear Algebra Appl., 429, 2415-2434 (2008) · Zbl 1153.65032 |
| [14] | 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 |
| [15] | Eiermann, M.; Ernst, O.; Güttel, S., Deflated restarting for matrix functions, SIAM J. Matrix Anal. Appl., 32, 621-641 (2011) · Zbl 1264.65070 |
| [16] | Frommer, A.; Glassner, U., Restarted GMRES for shifted linear systems, SIAM J. Sci. Comput., 19, 15-26 (1998) · Zbl 0912.65023 |
| [17] | 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 |
| [18] | 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 |
| [19] | Frommer, A.; Lund, K.; Szyld, D. B., Block Krylov subspace methods for functions of matrices, Electron. Trans. Numer. Anal., 47, 100-126 (2017) · Zbl 1372.65138 |
| [20] | Gallopoulos, E.; Saad, Y., Efficient solution of parabolic equations by polynomial approximation methods, SIAM J. Sci. Stat. Comput., 13, 1236-1264 (1992) · Zbl 0757.65101 |
| [21] | Garrappa, R.; Popolizio, M., On the use of matrix functions for fractional partial differential equations, Math. Comput. Simul., 81, 1045-1056 (2011) · Zbl 1210.65162 |
| [22] | Gohberg, I.; Semencul, A., On the inversion of finite Toeplitz matrices and their continuous analogs, Mat. Issled., 2, 201-233 (1972) · Zbl 0288.15004 |
| [23] | Golub, G. H.; Van Loan, C. F., Matrix Computations (2012), John Hopkins University Press: John Hopkins University Press Baltimore, MD |
| [24] | Gu, G.; Zhou, X.; Lin, L., A flexible preconditioned Arnoldi method for shifted linear systems, J. Comput. Math., 25, 522-530 (2007) · Zbl 1141.65356 |
| [25] | Gu, X.; Huang, T.; Yin, G.; Carpentieri, B.; Wen, C.; Du, L., Restarted Hessenberg method for solving shifted nonsymmetric linear systems, J. Comput. Appl. Math., 331, 166-177 (2017) · Zbl 1377.65042 |
| [26] | Gutknecht, M., Block Krylov Space Methods for Linear Systems with Multiple Right-Hand Sides: An Introduction, Modern Mathematical Models, Methods and Algorithms for Real World Systems (2007) |
| [27] | Gutknecht, M.; Schmelzer, T., The block grade of a block Krylov space, Linear Algebra Appl., 430, 174-185 (2009) · Zbl 1163.65015 |
| [28] | Higham, N. J., Functions of Matrices: Theory and Computation (2008), SIAM: SIAM Philadelphia · Zbl 1167.15001 |
| [29] | Higham, N. J., The scaling and squaring method for the matrix exponential revisited, SIAM Rev., 51, 747-764 (2009) · Zbl 1178.65040 |
| [30] | Hochbruck, M.; Lubich, C., On Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 34, 1911-1925 (1997) · Zbl 0888.65032 |
| [31] | Hochbruck, M.; Ostermann, A., Exponential integrators, Acta Numer., 19, 209-286 (2010) · Zbl 1242.65109 |
| [32] | Jegerlehner, B., Krylov space solvers for shifted linear systems (1996), Arxiv preprint |
| [33] | Jiang, W.; Wu, G., A thick-restarted block Arnoldi algorithm with modified Ritz vectors for large eigenproblems, Comput. Math. Appl., 60, 873-889 (2010) · Zbl 1201.65053 |
| [34] | Lee, S.; Pang, H.; Sun, H., Shift-invert Arnoldi approximation to the Toeplitz matrix exponential, SIAM J. Sci. Comput., 32, 774-792 (2010) · Zbl 1210.65079 |
| [35] | Li, Z.; Gu, G., Restarted FOM augmented with Ritz vectors for shifted linear systems, Numer. Math. J. Chin. Univ., 15, 40-49 (2006) · Zbl 1103.65037 |
| [36] | Lopez, L.; Simoncini, V., Analysis of projection methods for rational function approximation to the matrix exponential, SIAM J. Numer. Anal., 44, 613-635 (2006) · Zbl 1158.65031 |
| [37] | Lopez, L.; Simoncini, V., Preserving geometric properties of the exponential matrix by block Krylov subspace methods, BIT, 46, 813-830 (2006) · Zbl 1107.65039 |
| [38] | K. Lund, Private communication.; K. Lund, Private communication. |
| [39] | Magnus, A., Asymptotics and super asymptotics for best rational approximation error norms to the exponential function (the “1/9” problem) by the Carathéodory-Fejér method, Nonlinear Numer. Methods Ration. Approx. II, 296, 173-185 (1994) · Zbl 0809.41015 |
| [40] | Meerschaert, M.; Tadjeran, C., Finite difference approximations for fractional advection-dispersion flow equations, J. Comput. Appl. Math., 172, 65-77 (2004) · Zbl 1126.76346 |
| [41] | Meinardus, G., Approximation of Functions: Theory and Numerical Methods (1967), Springer-Verlag: Springer-Verlag New York, Inc., New York · Zbl 0152.15202 |
| [42] | Moler, C.; Van Loan, C. F., Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later, SIAM Rev., 45, 3-49 (2003) · Zbl 1030.65029 |
| [43] | Moret, I.; Novati, P., RD-rational approximations of the matrix exponential, BIT, 44, 595-615 (2004) · Zbl 1075.65062 |
| [44] | Morgan, R., Restarted block GMRES with deflation of eigenvalues, Appl. Numer. Math., 54, 222-236 (2005) · Zbl 1074.65043 |
| [45] | Niesen, J.; Wright, W., Algorithm 919: a Krylov subspace algorithm for evaluating the \(ϕ\)-functions appearing in exponential integrators, ACM Trans. Math. Softw., 38, 3, Article 22 pp. (2012) · Zbl 1365.65185 |
| [46] | Podlubny, I., Fractional Differential Equations (1999), Academic Press: Academic Press New York · Zbl 0918.34010 |
| [47] | Popolizio, M.; Simoncini, V., Acceleration techniques for approximating the matrix exponential operator, SIAM J. Matrix Anal. Appl., 30, 657-683 (2008) · Zbl 1168.65021 |
| [48] | Quarteroni, A.; Valli, A., Numerical Approximation of Partial Differential Equations (1997), Springer: Springer Berlin |
| [49] | Saad, Y., Analysis of some Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 29, 209-228 (1992) · Zbl 0749.65030 |
| [50] | Saad, Y., Iterative Methods for Sparse Linear Systems (2003), SIAM: SIAM Philadelphia · Zbl 1002.65042 |
| [51] | Saibaba, A.; Bakhos, T.; Kitanidis, P., A flexible Krylov solver for shifted systems with application to oscillatory hydraulic tomography, SIAM J. Sci. Comput., 35, A3001-A3023 (2013) · Zbl 1288.65041 |
| [52] | Sakurai, T.; Tadano, H.; Kuramashi, Y., Application of block Krylov subspace algorithms to the Wilson-Dirac equation with multiple right-hand sides in lattice QCD, Comput. Phys. Commun., 181, 113-117 (2010) · Zbl 1205.81131 |
| [53] | Sidje, R., EXPOKIT: software package for computing matrix exponentials, ACM Trans. Math. Softw., 24, 130-156 (1998) · Zbl 0917.65063 |
| [54] | Simoncini, V., Restarted full orthogonalization method for shifted linear systems, BIT, 43, 459-466 (2003) · Zbl 1033.65015 |
| [55] | Simoncini, V., The extended Krylov subspace for parameter dependent systems, Appl. Numer. Math., 60, 550-560 (2010) · Zbl 1190.65052 |
| [56] | Simoncini, V.; Szyld, D., Recent computational developments in Krylov subspace methods for linear systems, Numer. Linear Algebra Appl., 14, 1-59 (2007) · Zbl 1199.65112 |
| [57] | Soodhalter, K., Block Krylov subspace recycling for shifted systems with unrelated right-hand sides, SIAM J. Sci. Comput., 38, A302-A324 (2016) |
| [58] | Soodhalter, K., Stagnation of block GMRES and its relationship to block FOM, Electron. Trans. Numer. Anal., 46, 162-189 (2017) · Zbl 1368.65054 |
| [59] | Soodhalter, K.; Szyld, D.; Xue, F., Krylov subspace recycling for sequences of shifted linear systems, Appl. Numer. Math., 81, 105-118 (2014) · Zbl 1291.65108 |
| [60] | Tadjeran, C.; Meerschaert, M.; Scheffler, H., A second-order accurate numerical approximation for the fractional diffusion equation, J. Comput. Phys., 213, 205-213 (2006) · Zbl 1089.65089 |
| [61] | Tangman, D.; Gopaul, A.; Bhuruth, M., Exponential time integration and Chebychev discretisation schemes for fast pricing of options, Appl. Numer. Math., 58, 1309-1319 (2008) · Zbl 1151.91546 |
| [62] | Trefethen, L.; Weideman, J.; Schmelzer, T., Talbot quadratures and rational approximations, BIT, 46, 653-670 (2006) · Zbl 1103.65030 |
| [63] | Wang, H.; Wang, K.; Sircar, T., A direct \(O(N \log^2 N)\) finite difference method for fractional diffusion equations, J. Comput. Phys., 229, 8095-8104 (2010) · Zbl 1198.65176 |
| [64] | Wu, G.; Wei, Y., On analysis of projection methods for rational function approximation to the matrix exponential, SIAM J. Numer. Anal., 48, 191-197 (2010) · Zbl 1210.65096 |
| [65] | Wu, G.; Wang, Y.; Jin, X., A preconditioned and shifted GMRES algorithm for the PageRank problem with multiple damping factors, SIAM J. Sci. Comput., 34, A2558-A2575 (2012) · Zbl 1263.65037 |
| [66] | Wu, G.; Feng, T.; Wei, Y., An inexact shift-and-invert Arnoldi algorithm for Toeplitz matrix exponential, Numer. Linear Algebra Appl., 22, 777-792 (2015) · Zbl 1363.65087 |
| [67] | Wu, G.; Zhang, L.; Xu, T., A framework of the harmonic Arnoldi method for evaluating \(φ\)-functions with applications to exponential integrators, Adv. Comput. Math., 42, 505-541 (2016) · Zbl 1338.65123 |
| [68] | Yin, J.; Yin, G., Restarted full orthogonalization method with deflation for shifted linear systems, Numer. Math. Theory Methods Appl., 7, 399-412 (2014) · Zbl 1324.65067 |
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.
