Robust linear stability analysis and a new method for computing the action of the matrix exponential

Minghao W. Rostami, Fei Xue

Abstract: Linear stability analysis of a large-scale dynamical system requires computing the rightmost eigenvalue of a large sparse matrix $A$. To enhance the convergence to this eigenvalue, an iterative eigensolver is usually applied to a transformation of $A$ instead, which plays a similar role as a preconditioner for linear systems. Commonly used transformations such as shift-invert are unreliable and may cause convergence to a wrong eigenvalue. We propose using the exponential transformation since the rightmost eigenvalues of $A$ correspond to the dominant ones of $e^{hA}$ ($h>0$), which are easily captured by iterative eigensolvers. Numerical experiments on several challenging eigenvalue problems arising from linear stability analysis and pseudospectral analysis demonstrate the robustness of the exponential transformation at “preconditioning” the rightmost eigenvalue. The key to the efficiency of this preconditioner is a fast algorithm for approximating the action of $e^{hA}$ on a vector. We develop a new algorithm based on a rational approximation of $e^x$ with only one (repeated) pole. Compared to polynomial approximations, it converges significantly faster when the spectrum of $A$ has a wide horizontal span, which is common for matrices arising from PDEs; compared to the Krylov-type methods, our method requires considerably less memory.

Journal: SIAM Journal on Scientific Computing, 40(5), A3344–A3370 (2018)

DOI: 10.1137/17M1132537