Algorithm 894: On a block Schur--Parlett algorithm for ϕ-functions based on the sep-inverse estimate

ABSTRACT

FORTRAN 95 software is provided for computing the matrix values of ϕ-functions required in exponential integrators. The subroutines in the library accept as their argument a full, diagonal, or upper quasitriangular matrix with real or complex entries in one of four precisions. Two different algorithms are implemented, one is the scaling and squaring method, and the other is a modified block Schur--Parlett algorithm. In the latter algorithm, a recursive three-by-three blocking is applied to the argument based on an estimate of the sep-inverse function. The estimation of the sep-inverse function is carried out by Hager--Higham estimator implemented as the subroutine xLACON in LAPACK. Our modifications to the block Schur--Parlett algorithm are described together with the results of numerical experiments.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 2: Bai, Z. and Demmel, J. W. 1993. On swapping diagonal blocks in real Schur form. Lin. Alg. Appl. 186, 73--95.
• 3: R. H. Bartels , G. W. Stewart, Solution of the matrix equation AX + XB = C [F4], Communications of the ACM, v.15 n.9, p.820-826, Sept. 1972 [doi>10.1145/361573.361582]
• 4: Håvard Berland , Bård Skaflestad , Will M. Wright, EXPINT---A MATLAB package for exponential integrators, ACM Transactions on Mathematical Software (TOMS), v.33 n.1, p.4-es, March 2007 [doi>10.1145/1206040.1206044]
• 5: An updated set of basic linear algebra subprograms (BLAS), ACM Transactions on Mathematical Software (TOMS), v.28 n.2, p.135-151, June 2002 [doi>10.1145/567806.567807]
• 6: Philip I. Davies , Nicholas J. Higham, A Schur-Parlett Algorithm for Computing Matrix Functions, SIAM Journal on Matrix Analysis and Applications, v.25 n.2, p.464-485, 2003 [doi>10.1137/S0895479802410815]
• 7: Frank, W. L. 1958. Computing eigenvalues of complex matrices by determinant evaluation and by methods of Danilewski and Wielandt. J. Soc. Indust. Appl. Math. 6, 4, 378--392.
• 8: Nicholas J. Higham, FORTRAN codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation, ACM Transactions on Mathematical Software (TOMS), v.14 n.4, p.381-396, Dec. 1988 [doi>10.1145/50063.214386]
• 9: Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2002
• 10: Nicholas J. Higham, The Scaling and Squaring Method for the Matrix Exponential Revisited, SIAM Journal on Matrix Analysis and Applications, v.26 n.4, p.1179-1193, 2005 [doi>10.1137/04061101X]
• 11: Nicholas J. Higham , Françoise Tisseur, A Block Algorithm for Matrix 1-Norm Estimation, with an Application to 1-Norm Pseudospectra, SIAM Journal on Matrix Analysis and Applications, v.21 n.4, p.1185-1201, March – May 2000 [doi>10.1137/S0895479899356080]
• 12: Intel corporation. 2008. Intel Fortran compiler. http://developer.intel.com/software/products/.
• 13: Isak Jonsson , Bo Kågström, Recursive blocked algorithms for solving triangular systems—Part I: one-sided and coupled Sylvester-type matrix equations, ACM Transactions on Mathematical Software (TOMS), v.28 n.4, p.392-415, December 2002 [doi>10.1145/592843.592845]
• 14: Bo Kågström , Peter Poromaa, Distributed and shared memory block algorithms for the triangular Sylvester equation with sep-1 estimators, SIAM Journal on Matrix Analysis and Applications, v.13 n.1, p.90-101, Jan. 1992 [doi>10.1137/0613009]
• 15: Kågström, B. and Westin, L. 1989. Generalized Schur methods with condition estimators for solving the generalized Sylvester equation. IEEE Trans. Autom. Cont. 34, 745--751.
• 16: Aly-Khan Kassam , Lloyd N. Trefethen, Fourth-Order Time-Stepping for Stiff PDEs, SIAM Journal on Scientific Computing, v.26 n.4, p.1214-1233, 2005 [doi>10.1137/S1064827502410633]
• 17: S. Koikari, An error analysis of the modified scaling and squaring method, Computers & Mathematics with Applications, v.53 n.8, p.1293-1305, April, 2007 [doi>10.1016/j.camwa.2006.04.032]
• 18: Minchev, B. and Wright, W. M. 2005. A review of exponential integrators for first order semi-linear problem. Tech. rep. No. 2/2005. The Norwegian University of Science and Technology. Trondhein, Norway.
• 19: Moler, C. B. and Van Loan, C. F. 2003. Nineteen dubious ways to compute the exponential of a matrix, twenty five years later. SIAM Rev. 45, 1, 3--49.
• 20: Parlett, B. N. 1976. A recurrence among the elements of functions of triangular matrices. Lin. Alg. Appl. 14, 117--121.
• 21: Roger B. Sidje, Expokit: a software package for computing matrix exponentials, ACM Transactions on Mathematical Software (TOMS), v.24 n.1, p.130-156, March 1998 [doi>10.1145/285861.285868]
• 22: Sun Microsystems. 2008. Sun Fortran 95 compiler. http://developers.sun.com/sunstudio/.
• 23: Tommila, M. 2005. apfloat, a C++ high performance arbitrary precision arithmetic package, Version 2.41. http://www.apfloat.org/.
• 24: Torczon, V. 1991. On the convergence of the multidirectional search algorithm. SIAM J. Optimiz. 1, 1, 123--145.
• 25: Vaught, A. 2006. G95 Manual. http://www.g95.org/.
• 26: 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
      G.1.3 Numerical Linear Algebra

General Terms:
Algorithms

Keywords:
ϕ-functions, block Schur--Parlett algorithm, exponential integrators, matrix functions