  The approximation of $e^{tA}B$ where $A$ is a large sparse matrix and $B$ a
rectangular matrix is the 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$\acute{\rm
e}$odory-Fej$\acute{\rm e}$r approximation, whose core reduces to solve shifted
linear systems with multiple right-hand sides. The restarted and shifted block
FOM algorithm is a commonly used technique for this problem. However,
determining good preconditioners for shifted systems that preserve the original
structure is a difficult task. In this paper, we propose a new preconditioner
for the restarted and shifted block FOM algorithm. The key is that the absolute
values of the poles of the Carath$\acute{\rm e}$odory-Fej$\acute{\rm e}$r
approximation are medium sized and can be much smaller than the norm of the
matrix in question. The advantages of the proposed strategy are that we can
precondition all the shifted linear systems simultaneously, and preserve the
original structure of the shifted linear systems after restarting. Theoretical
results are provided to show the rationality of our preconditioning strategy.
Applications of the new approach to Toeplitz matrix exponential problem are
also discussed. Numerical experiments illustrate the superiority of the new
algorithm over many state-of-the-art algorithms for matrix exponential.
