Solution of the Sylvester matrix equation AXBT + CXDT = E

ABSTRACT

A software package has been developed to solve efficiently the Sylvester-type matrix equation AXBT + CXDT = E. A transformation method is used which employs the QZ algorithm to structure the equation in such a way that it can be solved columnwise by a back substitution technique. The algorithm is an extension of the Bartels-Stewart method and the Hessenberg-Schur method. The numerical performance of the algorithms and software is demonstrated by application to near-singular systems.

REFERENCES

• 1: ARNOLD, W F., AND LAUB, A. J Generalized eigenproblem algorithms and software for algebraic Riccati equations. Proc. IEEE 72, 12 (Dec. 1984), 1746-1754
• 2: 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]
• 3: BYERS, R. A LINPACK-style condition estimator for the equation AX - XBr - C. IEEE Trans. Aut. Contr. AC~29, 10 (Oct. 1984), 926-928.
• 4: CHU, K.-W. E. The solution of the matrix equation AXB - CXD = E and (YA - DZ, YC - BZ) = (E, F). Lin. Alg. Appl. 93 (Aug. 1987), 93-105.
• 5: CLINE, A. K., MOLER, C. B., STEWART, G. W., ANn WmKINSO~, J.H. An estimate for the condition number of a matrix SIAM J. Numer. Anal. 16, 2 (Apr. 1979), 368-375.
• 6: 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]
• 7: GOLUB, G. H., NAss, S., AND VAN LOAN, C.F. A Hessenberg-Schur method for the problem AX + XB = C. IEEE Trans. Aut. Control. AC-24, 6 (Dec. 1979), 909-913.
• 8: GOLUB, G. H., AND VAN LOAN, C.F. Matrix Computations. Johns Hopkins Univ. Press, Baltimore, Second Edition, 1989.
• 9: Gary Hewer , Charles Kenney, The sensitivity of the stable Lyapunov equation, SIAM Journal on Control and Optimization, v.26 n.2, p.321-344, March 1988 [doi>10.1137/0326018]
• 10: 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]
• 11: HmHAM, N. J., AND HmHAM, D. J. Large growth factors in Gaussian elimination with pivoting. SIAM J. Matrix Anal. Appl. 10, 2 (Apr. 1989), 155-164.
• 12: K~GSTRSM, B., AND WESTIN, L. Generalized Schur methods with condition estimators for solving the generalized Sylvester equation. IEEE Trans. Aut. Control. AC-34, 7 (July 1989), 745-751.
• 13: LANCASTER, P. Theory of Matrices. Academic Press, New York, 1969.
• 14: MOLER, C. B., AND STEWART, G. W. An algorithm for generalized matrix eigenvalue problems. SIAM J. Numer. Anal. 10, 2 (Apr. 1973), 241-256.
• 15: SYLVEST~R, J J. Sur la solution du cas le plus g~n6ral des ~quations lin~aires en quantit~s binaires, c~est&-dire en quaternions ou en matrices du second ordres. Sur la r~solution g~n~rale de F6quation lin~aire en matrices d'un ordre quelconque. Sur F~quation lin~aire trin6me en matrices d~un ordre quelconque. Comptes Rendus Acad. $ci. 99 (1884), 117-118, 409-412, 432-436, 527-529.
• 16: Lloyd N. Trefethen , Robert S. Schreiber, Average-case stability of Gaussian elimination, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.335-360, Jul. 1990 [doi>10.1137/0611023]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

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: Conditioning
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency; Algorithm design and analysis; Reliability and robustness

General Terms:
Algorithms, Performance