ALGORITHMIC COMPLEXITY ANALYSIS AND NUMERICAL EXPERIMENTS FOR COMPUTING THE MATRIX EXPONENTIAL
Keywords:
Fundamental solution matrix, Matrix exponential function, Algorithmic complexity, Numerical stability, Numerical experimentAbstract
The fundamental solution matrix is a central object in the theoretical study and numerical computation of linear systems of ordinary differential equations with constant coefficients. This paper establishes a unified framework for the algorithmic complexity analysis of seven classical methods, with theoretical comparison from the perspectives of time complexity, space complexity, and numerical stability. Numerical experiments on six classes of typical test matrices are conducted, and quantitative evaluations are performed with respect to computational accuracy, running time, and robustness. The results indicate that the scaling-and-squaring method achieves optimal numerical stability; the eigenvalue decomposition method attains the highest accuracy for diagonalizable well-conditioned matrices; and the direct sum decomposition method significantly outperforms the Jordan canonical form method on non-diagonalizable matrices. A selection strategy is proposed to provide reference for teaching and engineering practice.References
[1] Moler C, Van Loan C. Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later. SIAM Review, 2003, 45(1): 3-49.
[2] Shang Y L, Zhang Q L. Representation of the exponential matrix e^(At) for solutions of first-order differential equation systems. Journal of Luoyang University, 1995, 10(4): 30-33.
[3] Blanes S, Kopylov N, Seydaoğlu M. Efficient scaling and squaring method for the matrix exponential. SIAM Journal on Matrix Analysis and Applications, 2025, 46(1): 74-93.
[4] Pozza S, Van Buggenhout N. A new Legendre polynomial-based approach for non-autonomous linear ODEs. Electronic Transactions on Numerical Analysis, 2024, 60: 292-326.
[5] Yao W A, Gao Q, Tan S J, et al. Development and extended applications of the precise integration method. Chinese Journal of Computational Mechanics, 2024, 41(1): 1-24.
[6] Higham N J. Functions of matrices: theory and computation. Philadelphia: SIAM, 2008.
[7] Golub G H, Van Loan C F. Matrix computations. 4th ed. Baltimore: Johns Hopkins University Press, 2013.
[8] Tan S J, Wu Z G, Zhong W X. Adaptive selection of parameters in the precise integration method for matrix exponentials. Chinese Journal of Theoretical and Applied Mechanics, 2009, 41(6): 961-966.
[9] Zhang H W, Zhong W X. Discussion of algorithms for computing matrix exponentials. Journal of Dalian University of Technology, 2000, 40(5): 522-525.
[10] Güttel S, Schweitzer M. Randomized sketching for Krylov approximations of large-scale matrix functions. SIAM Journal on Matrix Analysis and Applications, 2023, 44(3): 1073-1095.
[11] Guidotti N L, Martinsson P G, Acebrón J A, et al. Accelerating a restarted Krylov method for matrix functions with randomization. arXiv preprint, arXiv: 2503.22631, 2025.
[12] Zheng Y. A theorem on a matrix exponential function and its teaching method. Mathematical Theory and Applications, 2018, 38(Z2): 123-128.