A shifted block FOM algorithm with deflated restarting for matrix exponential computations

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 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 GMRES algorithm is also analyzed. Numerical experiments demonstrate the superiority of the proposed algorithm over many state-of-the-art algorithms for the matrix exponential.