×

High-performance computation of the exponential of a large sparse matrix. (English) Zbl 1480.65104

Summary: Computation of the large sparse matrix exponential has been an important topic in many fields, such as network and finite-element analysis. The existing scaling and squaring algorithm (SSA) is not suitable for the computation of the large sparse matrix exponential as it requires more memory and has a higher computational cost than is actually needed. By introducing two novel concepts, i.e., real bandwidth and \(\varepsilon\)-bandwidth, to measure the sparsity of the matrix, the sparsity of the matrix exponential is analyzed. It is found that for every matrix computed in the squaring phase of the SSA, a corresponding sparse approximate matrix exists. To obtain the sparse approximate matrix, a new filtering technique based on forward error analysis is proposed. Combining the filtering technique with the idea of keeping track of the incremental part, a competitive algorithm is developed for the large sparse matrix exponential. Due to the filtering technique, the proposed method can greatly alleviate the overscaling problem. Three sets of numerical experiments, including one large matrix with a dimension larger than \(2\times 10^6\), are conducted. The numerical experiments show that, compared with the expm function in MATLAB, the proposed algorithm can provide higher accuracy at lower computational cost and with less memory.

MSC:

65F60 Numerical computation of matrix exponential and similar matrix functions
65F50 Computational methods for sparse matrices
15A16 Matrix exponential and similar functions of matrices
15A60 Norms of matrices, numerical range, applications of functional analysis to matrix theory
05C82 Small world graphs, complex networks (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] A. H. Al-Mohy and N. J. Higham, A new scaling and squaring algorithm for the matrix exponential, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 970-989, https://doi.org/10.1137/09074721X. · Zbl 1194.15021
[2] A. H. Al-Mohy and N. J. Higham, Computing the action of the matrix exponential, with an application to exponential integrators, SIAM J. Sci. Comput., 33 (2011), pp. 488-511, https://doi.org/10.1137/100788860. · Zbl 1234.65028
[3] P. Bader, S. Blanes, and F. Casas, Computing the matrix exponential with an optimized Taylor polynomial approximation, Mathematics, 7 (2019), p. 1174, https://doi.org/10.3390/math7121174.
[4] M. Benzi and P. Boito, Decay properties for functions of matrices over C\textsuperscript*-algebras, Linear Algebra Appl., 456 (2013), pp. 174-198, https://doi.org/10.1016/j.laa.2013.11.027. · Zbl 1314.47020
[5] M. Benzi and G. H. Golub, Bounds for the entries of matrix functions with applications to preconditioning, BIT, 39 (1999), pp. 417-438, https://doi.org/10.1023/A:1022362401426. · Zbl 0934.65054
[6] M. Benzi and N. Razouk, Decay bounds and \({O(n)}\) algorithms for approximating functions of sparse matrices, Electron. Trans. Numer. Anal., 28 (2007), p. 16, https://doi.org/10.1007/978-88-470-0665-2_19. · Zbl 1171.65034
[7] D. A. Bini and B. Meini, On the exponential of semi-infinite quasi-Toeplitz matrices, Numer. Math., 141 (2019), pp. 319-351, https://doi.org/10.1007/s00211-018-1006-y. · Zbl 1407.15036
[8] Y. Cheng and Z. Ai, Consolidation analysis of transversely isotropic layered saturated soils in the Cartesian coordinate system by extended precise integration method, Appl. Math. Model., 40 (2016), pp. 2692-2704, https://doi.org/10.1016/j.apm.2015.09.085. · Zbl 1452.76232
[9] E. Defez, J. Ibán͂ez, J. Sastre, J. Peinado, and P. Alonso, A new efficient and accurate spline algorithm for the matrix exponential computation, J. Comput. Appl. Math., 337 (2018), pp. 354-365, https://doi.org/10.1016/j.cam.2017.11.029. · Zbl 1398.65091
[10] L. Dieci and A. Papini, Conditioning of the exponential of a block triangular matrix, Numer. Algorithms, 28 (2001), pp. 137-150, https://doi.org/10.1023/A:1014071202885. · Zbl 0992.65042
[11] E. Estrada and D. J. Higham, Network properties revealed through matrix functions, SIAM Rev., 52 (2010), pp. 696-714, https://doi.org/10.1137/090761070. · Zbl 1214.05077
[12] Q. Gao, F. Wu, H. W. Zhang, W. X. Zhong, W. P. Howson, and F. W. Williams, A fast precise integration method for structural dynamics problems, Struct. Eng. Mech., 43 (2012), pp. 1-13, https://doi.org/10.12989/sem.2012.43.1.001.
[13] N. J. Higham, The scaling and squaring method for the matrix exponential revisited, SIAM Rev., 2005 (2005), pp. 747-764, https://doi.org/10.1137/090768539. · Zbl 1178.65040
[14] N. J. Higham, Functions of Matrices: Theory and Computation, SIAM, Philadelphia, 2008, https://doi.org/10.1137/1.9780898717778. · Zbl 1167.15001
[15] N. J. Higham and A. H. Al-Mohy, Computing matrix functions, Acta Numer., 19 (2010), pp. 159-208, https://doi.org/10.1017/S0962492910000036. · Zbl 1242.65090
[16] A. Iserles, How large is the exponential of a banded matrix?, NZ J. Math., 29 (2000), pp. 177-192. · Zbl 0968.22016
[17] S. Kolodziej, M. Aznaveh, M. Bullock, J. David, T. Davis, M. Henderson, Y. Hu, R. Sandstrom, T. A. Davis, and Y. Hu, The SuiteSparse Matrix Collection website interface, J. Open Source Softw., 4 (2019), p. 1244, https://doi.org/10.21105/joss.01244.
[18] I. T. Koponen and M. Nousiainen, Concept networks of students’ knowledge of relationships between physics concepts: Finding key concepts and their epistemic support, Appl. Netw. Sci., 3 (2018), https://doi.org/10.1007/s41109-018-0072-5.
[19] D. Kressner and R. Luce, Fast computation of the matrix exponential for a Toeplitz matrix, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 23-47, https://doi.org/10.1137/16M1083633. · Zbl 1386.65131
[20] C. Moler and C. V. Loan, Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later, SIAM Rev., 45 (2003), pp. 3-49, https://doi.org/10.1137/S00361445024180. · Zbl 1030.65029
[21] R. A. Rossi and N. K. Ahmed, The network data repository with interactive graph analytics and visualization, in Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
[22] P. Ruiz, J. Sastre, J. Ibán͂ez, and E. Defez, High performance computing of the matrix exponential, J. Comput. Appl. Math., 291 (2016), pp. 370-379, https://doi.org/10.1016/j.cam.2015.04.001. · Zbl 1329.65092
[23] R. K. Saha and J. R. Boriotti, Truncation and round-off errors in computation of matrix exponentials, Int. J. Control, 33 (1981), pp. 137-147, https://doi.org/10.1080/00207178108922910. · Zbl 0464.93038
[24] J. Sastre, J. Ibán͂ez, and E. Defez, Boosting the computation of the matrix exponential, Appl. Math. Comput., 340 (2019), pp. 206-220, https://doi.org/10.1016/j.amc.2018.08.017. · Zbl 1429.65093
[25] J. Sastre, J. Ibán͂ez, E. Defez, and P. Ruiz, Accurate matrix exponential computation to solve coupled differential models in engineering, Math. Comput. Model., 54 (2011), pp. 1835-1840, https://doi.org/10.1016/j.mcm.2010.12.049. · Zbl 1235.65042
[26] J. Sastre, J. Ibán͂ez, P. Ruiz, and E. Defez, Accurate and efficient matrix exponential computation, Int. J. Comput. Math., 91 (2014), pp. 97-112, https://doi.org/10.1080/00207160.2013.791392. · Zbl 1291.65139
[27] J. Shao, X. Ma, S. Yin, and J. Wang, Conformal precise-integration time-domain method for analyzing electromagnetic fields in fine-structured device with moving 3-D part, IEEE Trans. Microw. Theory Tech., 66 (2018), pp. 3200-3209, https://doi.org/10.1109/TMTT.2018.2829169.
[28] R. Sidje, Expokit: A software package for computing matrix exponentials, ACM Trans. Math. Softw., 24 (1998), pp. 130-156, https://doi.org/10.1145/285861.285868. · Zbl 0917.65063
[29] W. H. Steeb and Y. Hardy, Exponential of a matrix, a nonlinear problem, and quantum gates, J. Math. Phys., 56 (2015), p. 012201, https://doi.org/10.1063/1.4905382. · Zbl 1305.81059
[30] H. D. Vo and R. B. Sidje, Approximating the large sparse matrix exponential using incomplete orthogonalization and Krylov subspaces of variable dimension, Numer. Linear Algebra, 24 (2017), e2090, https://doi.org/10.1002/nla.2090. · Zbl 1424.65063
[31] H. Wang and Q. Ye, Error bounds for the Krylov subspace methods for computations of matrix exponentials, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 155-187, https://doi.org/10.1137/16M1063733. · Zbl 1365.65136
[32] M. F. Wang and F. Au, Precise integration methods based on Lagrange piecewise interpolation polynomials, Int. J. Numer. Methods Eng., 77 (2009), pp. 998-1014, https://doi.org/10.1002/nme.2444. · Zbl 1183.74370
[33] F. Wu, Q. Gao, and W. X. Zhong, Fast precise integration method for hyperbolic heat conduction problems, Appl. Math. Mech. Engl. Ed., 34 (2013), pp. 791-800, https://doi.org/10.1007/s10483-013-1707-6.
[34] T. Zhang, B. Fang, Y. Y. Tang, Z. Shang, and B. Xu, Generalized discriminant analysis: A matrix exponential approach, IEEE Trans. Syst. Man. Cybern. B, 40 (2010), pp. 186-97, https://doi.org/10.1109/TSMCB.2009.2024759.
[35] W. X. Zhong, On precise integration method, J. Comput. Appl. Math., 163 (2004), pp. 59-78, https://doi.org/10.1016/j.cam.2003.08.053. · Zbl 1046.65053
[36] W. X. Zhong and F. W. Williams, A precise time step integration method, P. I. Mech. Eng. C.-J. Mec., 208 (1994), pp. 427-430, https://doi.org/10.1243/PIME_PROC_1994_208_148_02.
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.