LAPACK-style algorithms and software for solving the generalized Sylvester equation and estimating the separation between regular matrix pairs

ABSTRACT

Robust and fast software to solve the generalized Sylvester equation (AR - LB = C, DR - LE = F) for unknowns R and L is presented. This special linear system of equations, and its transpose, arises in computing error bounds for computed eigenvalues and eigenspaces of the generalized eigenvalue problem S-&lgr;T, in computing deflating subspaces of the same problem, and in computing certain decompositions of transfer matrices arising in control theory. Our contributions are twofold. First, we reorganize the standard algorithm for this problem to use Level 3 BLAS operations, like matrix multiplication, in its inner loop. This speeds up the algorithm by a factor of 9 on an IBM RS6000. Second, we develop and compare several condition estimation algorithms, which inexpensively but accurately estimate the sensitivity of the solution of this linear system.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 2: Z. Bai , James Demmel , A. McKenney, On computing condition numbers for the nonsymmetric eigenproblem, ACM Transactions on Mathematical Software (TOMS), v.19 n.2, p.202-223, June 1993 [doi>10.1145/152613.152617]
• 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: CHu, IC-W. E. 1987. The solution of the matrix equations AXB- CXD ~ E and (YA- DZ, YC - BZ) = (E, F). Lin. Alg. Appl. 93, 93-105.
• 5: CLINE, A., MOLER, C., STEWART, G. W., AND WILKINSON, J. 1979. An estimate of the condition number of a matrix. SIAM J. Numer. Anal. 16, 368-375.
• 6: DEMMEL, J. AND K~OSTROM, B. 1987. Computing stable eigendecompositions of matrix pencils. Lin. Alg. Appl. 88/89 (Apr.), 139-186.
• 7: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 8: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 9: Judith D. Gardiner , Matthew R. Wette , Alan J. Laub , James J. Amato , Cleve B. Moler, Algorithm 705; a FORTRAN-77 software package for solving the Sylvester matrix equation AXBT + CXDT = E, ACM Transactions on Mathematical Software (TOMS), v.18 n.2, p.232-238, June 1992 [doi>10.1145/146847.146930]
• 10: Judith D. Gardiner , Alan J. Laub , James J. Amato , Cleve B. Moler, Solution of the Sylvester matrix equation AXBT + CXDT = E, ACM Transactions on Mathematical Software (TOMS), v.18 n.2, p.223-231, June 1992 [doi>10.1145/146847.146929]
• 11: GOLUB, G., NASH, S., AND VAN LOAN, C. 1979. A Hessenberg-Schur method for the matrix problem AX + XB = C. IEEE Trans. Automat. Contr. AC-24, 909-913.
• 12: Nick Gould, On growth in Gaussian elimination with complete pivoting, SIAM Journal on Matrix Analysis and Applications, v.12 n.2, p.354-361, April 1991 [doi>10.1137/0612025]
• 13: HAOER, W.W. 1984. Condition estimators. SlAM J. Sci. Stat. Comput. 5, 311-316.
• 14: Nicholas J. Higham, ALGORITHM 674: 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.15 n.2, p.168, June 1989 [doi>10.1145/63522.214391]
• 15: HIGI/kM, N.J. 1993. Perturbation theory and backward error analysis for AX - XB = C. BIT 33, 1, 124-136.
• 16: KXCSTROM, B. 1993. A direct method for reordering eigenvalues in the generalized real Schur form of a regular matrix pair (A, B). In Linear Algebra for Large Scale and Real-Time Applications, M. S. Moonen, G. H. Golub, and B. L. R. De Moor, Eds. Kluwer Academic, Amsterdam, 195-218.
• 17: Bo Kagstrom, A Perturbation Analysis of the Generalized Sylvester Equation $(AR - LB, DR - LE) = (C, F)$, SIAM Journal on Matrix Analysis and Applications, v.15 n.4, p.1045-1060, Oct. 1994 [doi>10.1137/S0895479893246212]
• 18: 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]
• 19: Bo Kagstrom , Peter Poromaa, LAPACK Working Note 75: LAPACK-Style Algorithms and Software for Solving the Generalized Sylvester Equation and Estimating the Separation Between Regular Matrix Pairs, University of Tennessee, Knoxville, TN, 1994
• 20: Bo Kagstrom , Peter Poromaa, LAPACK Working Note 87: Computing Eigenspaces with Specified Eigenvalues of a Regular Matrix Pair and Condition Estimation: Theory, Algorithms and Software, University of Tennessee, Knoxville, TN, 1994
• 21: K~GSTROM, B. AND VAN DOOREN, P. 1992. A generalized state-space approach for the additive decomposition of a transfer matrix. Int. J. Nurner. Lin. Alg. Appl. 1, 2, 165-181.
• 22: K~GSTROM, B. AND WESTIN, L. 1989. Generalized Schur methods with condition estimators for solving the generalized Sylvester equation. IEEE Trans. Automat. Contr. 34, 4, 745-751.
• 23: MOLER, C. AND STEWART, G. 1973. An algorithm for the generalized matrix eigenvalue problem. SIAM J. Numer. Anal. 10, 241-256.
• 24: POROM~, P. 1995. On efficient and robust estimators for the separation between two regular matrix pairs with applications in condition estimation. Rep. UMINF-95.05, Dept. of Computing Science, Ume~ Univ., Ume~, Sweden.
• 25: STEWART, G.W. 1973. Error and perturbation bounds for subspaces associated with certain eigenvalue problems. SIAM Rev. 15, 4 (Oct.), 727-764.
• 26: STEWART, G. W. AND SUN, J.-G. 1990. Matrix Perturbation Theory. Academic Press, New York. VARAH, J. 1979. On the separation of two matrices. SIAM J. Numer. Anal. 16, 216-222.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods); Matrix inversion; Conditioning
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency; Reliability and robustness

General Terms:
Algorithms

Keywords:
LAPACK, block algorithms, condition numbers, dif-estimators, error bounds, generalized Sylvester equation