Expokit: a software package for computing matrix exponentials

ABSTRACT

Expokit provides a set of routines aimed at computing matrix exponentials. More precisely, it computes either a small matrix exponential in full, the action of a large sparse matrix exponential on an operand vector, or the solution of a system of linear OBEs with constant inhomogeneity. The backbone of the sparse routines consists of matrix-free Krylov subspace projection methods (Arnoldi and Lanczos processes), and that is why the toolkit is capable of coping with sparse matrices of large dimension. The software handles real and complex matrices and provides specific routines for symmetric and Hermitian matrices. The computation of matrix exponentials is a numerical issue of critical importance in the area of Markov chains and furthermore, the computed solution is subject to probabilistic constraints. In addition to addressing general matrix exponentials, a distinct attention is assigned to the computation of transient states of Markov chains.

REFERENCES

• 1: BARRET, R., BERRY, M., CHAN, T. F., DEMMEL, J., DONATO, J., DONGARRA, J., EIJKHOUT, V., POZO, R., ROMINE, C., AND VAN DER VORST, H. 1994. Templates for the Solutions of Linear Systems: Building Blocks for Iterative Methods. Society for Industrial and Applied Mathematics, Philadelphia, PA.
• 2: BERMAN, A. AND PLEMMONS, R.J. 1979. Nonnegative Matrices in the Mathematical Sciences. Academic Press, Inc., New York, NY.
• 3: CARPENTER, A. J., RUTTAN, A., AND VARGA, R.S. 1984. Extended numerical computations on the 1/9 conjecture in rational approximation theory. In Rational Approximation and Interpolation. Springer Lecture Notes in Mathematics, vol. 1105. Springer-Verlag, Berlin, Germany, 383-411.
• 4: G. Ciardo , R. A. Marie , B. Sericola , K. S. Trivedi, Performability Analysis Using Semi-Markov Reward Processes, IEEE Transactions on Computers, v.39 n.10, p.1251-1264, October 1990 [doi>10.1109/12.59855]
• 5: CLAROTTI, C.A. 1984. The Markov approach to calculating system reliability: Computational problems. In International School of Physics "Enrico Fermi" Varenna, Italy (Amsterdam, The Netherlands), A. Serra and R. E. Barlow, Eds. North-Holland Physics Publishing, Amsterdam, The Netherlands, 54-66.
• 6: CODY, W. J., MEINARDUS, a., AND VARGA, R.S. 1969. Chebyshev rational approximation to exp(-x) in {0,+~) and applications to heat conduction problems. J. Approx. Theory 2, 50-65.
• 7: DRUSKIN, V. AND KNIZHNERMAN, L. 1995. Krylov subspace approximations ofeigenpairs and matrix functions in exact and computer arithmetic. Num. Lin. Alg. Appl. 2, 205-217.
• 8: I. S. Duff , Roger G. Grimes , John G. Lewis, Sparse matrix test problems, ACM Transactions on Mathematical Software (TOMS), v.15 n.1, p.1-14, March 1989 [doi>10.1145/62038.62043]
• 9: FASSINO, C. 1993. Computation of matrix functions. Ph.D. thesis. Universita di Pisa, Udine, Italy.
• 10: E. Gallopoulos , Y. Saad, Efficient solution of parabolic equations by Krylov approximation methods, SIAM Journal on Scientific and Statistical Computing, v.13 n.5, p.1236-1264, Sept. 1992 [doi>10.1137/0913071]
• 11: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 12: Kjell Gustafsson, Control theoretic techniques for stepsize selection in explicit Runge-Kutta methods, ACM Transactions on Mathematical Software (TOMS), v.17 n.4, p.533-554, Dec. 1991 [doi>10.1145/210232.210242]
• 13: Marlis Hochbruck , Christian Lubich, On Krylov Subspace Approximations to the Matrix Exponential Operator, SIAM Journal on Numerical Analysis, v.34 n.5, p.1911-1925, Oct. 1997 [doi>10.1137/S0036142995280572]
• 14: Marlis Hochbruck , Christian Lubich , Hubert Selhofer, Exponential Integrators for Large Systems of Differential Equations, SIAM Journal on Scientific Computing, v.19 n.5, p.1552-1574, Sept. 1998 [doi>10.1137/S1064827595295337]
• 15: ISERLES, A. AND NDRSETT, S.P. 1991. Order Stars. Chapman & Hall, Ltd., London, UK.
• 16: LAWSON, J. D. 1967. Generalized Runge-Kutta processes for stable systems with large Lipschitz constants. SIAM J. Numer. Anal. 4, 372-380.
• 17: LEYK, T. AND ROBERTS, S.G. 1995. Numerical solving of a free boundary phase field model using Krylov subspace method. In Proceedings of the Computational Techniques and Applications Conference (Melbourne, Australia). World Scientific Publishing Co., Inc., River Edge, NJ.
• 18: MEERBERGEN, K. AND SADKANE, M. 1996. Using Krylov approximations to the matrix exponentional operator in Davidson's method. Tech. Rep. TW 238, Dept. of Computer Science. Katholieke Universiteit Leuven, Leuven, Belgium.
• 19: MOLER, C. B. AND VAN LOAN, C.F. 1978. Nineteen dubious ways to compute the exponentional of a matrix. SIAM Rev. 20, 4, 801-836.
• 20: NEUTS, M. F. 1981. Matrix Geometric Solutions in Stochastic Models: An Algorithmic Approach. Johns Hopkins University Press, Baltimore, MD.
• 21: PARLETT, B.N. 1976. A recurrence among the elements of functions of triangular matrices. Lin. Alg. Appl. 14, 117-121.
• 22: PARLETT, B. N. AND NG, K. C. 1985. Development of an accurate algorithm for exp(BT). Tech. Rep. PAM-294, Center for Pure and Applied Mathematics, University of California at Berkeley, Berkeley, CA.
• 23: PHILIPPE, B. AND SIDJE, R. B. 1995. Transient solutions of Markov processes by Krylov subspaces. In Proceedings of the 2nd International Workshop on the Numerical Solution of Markov Chains (Raleigh, NC), W. J. Stewart, Ed. Kluwer Academic, Amsterdam, The Netherlands.
• 24: Y. Saad, Analysis of some Krylov subspace approximations to the matrix exponential operator, SIAM Journal on Numerical Analysis, v.29 n.1, p.209-228, Feb. 1992 [doi>10.1137/0729014]
• 25: SAAD, Y. 1992b. Numerical Methods for Large Eigenvalue Problems. Manchester University Press, New York, NY.
• 26: SAAD, Y. 1994. Sparskit: A basic tool kit for sparse matrix computation, version 2. Tech. Rep., Computer Science Dept., University of Minnesota, Minneapolis, MN.
• 27: SENETA, E. 1981. Non-negative Matrices and Markov Chains. 2nd ed. Springer-Verlag, New York, NY.
• 28: SIDJE, R.B. 1994. Parallel algorithms for large sparse matrix exponentials: Application to numerical transient analysis of Markov processes. Ph.D. thesis. University of Rennes 1, Rennes, France.
• 29: SIDJE, R. B. 1997. Alternatives for parallel Krylov basis computation. Num. Lin. Alg. Appl. 4, 4, 305-331.
• 30: Roger B. Sidje , William J. Stewart, A numerical study of large sparse matrix exponentials arising in Markov chains, Computational Statistics & Data Analysis, v.29 n.3, p.345-368, Jan. 28, 1999 [doi>10.1016/S0167-9473(98)00062-0]
• 31: D. E. Stewart , T. S. Leyk, Error estimates for Krylov subspace approximations of matrix exponentials, Journal of Computational and Applied Mathematics, v.72 n.2, p.359-369, Aug. 13, 1996 [doi>10.1016/0377-0427(96)00006-4]
• 32: STEWART, W.J. 1994. Introduction to the Numerical Solution of Markov Processes. Princeton University Press, Princeton, NJ.
• 33: VAN LOAN, C.F. 1977. The sensitivity of the matrix exponential. SIAM J. Numer. Anal. 14, 6, 971-981.
• 34: Richard S. Varga, Scientific Computations on Mathematical Problems and Conjectures, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1990
• 35: WARD, R. C. 1977. Numerical computation of the matrix exponential with accuracy estimate. SIAM J. Numer. Anal. 14, 4, 600-610.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Initial value problems

General Terms:
Algorithms

Keywords:
Krylov methods, Markov chains, matrix exponential