The generalized Schur decomposition of an arbitrary pencil A–&lgr;B—robust software with error bounds and applications. Part I: theory and algorithms

ABSTRACT

Robust software with error bounds for computing the generalized Schur decomposition of an arbitrary matrix pencil A – &lgr;B (regular or singular) is presented. The decomposition is a generalization of the Schur canonical form of A – &lgr;I to matrix pencils and reveals the Kronecker structure of a singular pencil. Since computing the Kronecker structure of a singular pencil is a potentially ill-posed problem, it is important to be able to compute rigorous and reliable error bounds for the computed features. The error bounds rely on perturbation theory for reducing subspaces and generalized eigenvalues of singular matrix pencils. The first part of this two-part paper presents the theory and algorithms for the decomposition and its error bounds, while the second part describes the computed generalized Schur decomposition and the software, and presents applications and an example of its use.

REFERENCES

• 1: BEELEN, T., AND VAN DOOREN, P. An improved algorithm for the computation of Kronecker's canomcal form of a singular pencil. Lin. Alg Appl. 105 (1988), 9-65.
• 2: BEELEN, T., VAN DOOREN, P., AND VERHAEGEN, M. A class of staircase algorithms for generalized state space systems. In Proceedings of the American Control Conference (Seattle, Wash., 1986), 425-426.
• 3: Daniel Lucius Boley, Computing the controllability - observability decomposition of a linear time-invariant dynamic system, a numerical approach, 1981
• 4: BOLE~, D., AND GOLUB, G. The Lanczos-Arnoldi algorithm and controllability. Syst. Control Lett. 4 (1984), 317 324.
• 5: CHAN, T. Rank revealing QR factorizations. Lin. Alg. Appl. 88/89 (1987), 67-82.
• 6: CHu, K.E. Exclusion theorems and the perturbation analysis of the generalized eigenproblem. Mathematics Dept. Numerical Analysis Rep. NA/11/85, Univ. of Reading, Reading, England, 1985.
• 7: DEMMEL, J., AND KA~GSTROM, B. Stable eigendecompositions of matrix pencils A - AB. Rep. UMINF-118.84, Inst. of Information Processing, Univ. of Ume~, S-901 87 Ume~, Sweden, 1984.
• 8: DEMMEL, J., AND KA~STROM, B. Stably computing the Kronecker structure and reducing subspaces of singular pencils A AB for uncertain data. In Large Scale Etgenvalue Problems, J. Cullum and R. A. Willoughby, Eds., North-Holland, Amsterdam, 1986, 283-323. Mathematics Studies Series Vol. 127.
• 9: DEMMEL, J., ANn KA~$TROM, B. Computing stable eigendecompositions of matrix pencils. Lin. Alg. Appl. 88/89 (Apr. 1987), 139-186.
• 10: James Demmel , Bo Kågström, Accurate solutions of ill-posed problems in control theory, SIAM Journal on Matrix Analysis and Applications, v.9 n.1, p.126-145, Jan. 1988 [doi>10.1137/0609010]
• 11: James Demmel , Bo Kågström, The generalized Schur decomposition of an arbitrary pencil A–&lgr;B—robust software with error bounds and applications. Part II: software and applications, ACM Transactions on Mathematical Software (TOMS), v.19 n.2, p.175-201, June 1993 [doi>10.1145/152613.152616]
• 12: Jack J Dongarra , Eric Grosse, Distribution of mathematical software via electronic mail, Communications of the ACM, v.30 n.5, p.403-407, May 1987 [doi>10.1145/22899.22904]
• 13: GANTMACHER, F. The Theory of Matrices, Vol. H (transl.). Chelsea, New York, 1959.
• 14: GARBOW, B. S., BOYLE, J. M., DONGARRA, J. J., AND MOLER, C. B. Matrix Etgensystem Routines EISPACK Guide Extension. Lecture Notes zn Computer Science, Vol. 51 Springer- Verlag, Berlin, 1977.
• 15: GOLUB, G., AND WILKINSON, J.H. Ill-conditioned eigensystems and the computation of the Jordan canonical form. SIAM Rev. 18, 4 (1976), 578 619.
• 16: HAMMARLINO, S., KENWARD, P., SYMM, H., AND WILYdNSON, J.H. Subroutine UKGE3R/D in the LASLIB library. Manuscript, 1981.
• 17: KA~sTI~OM, B. On computing the Kronecker canonical form of regular A - ^B pencils. In Matrix Pencils, Lecture Notes in Mathematics, Vol. 973, B. K~gstrdm and A. Ruhe, Eds., Springer-Verlag, Berlin, 1983, 30-57.
• 18: KA~STR(SM, B. The generalized singular value decomposition and the general A - AB problem. BIT 24 (1984), 568 583.
• 19: Bo Kågström, RGSD an algorithm for computing the Kronecker structure and reducing subspaces of singular A-&lgr;B pencils, SIAM Journal on Scientific and Statistical Computing, v.7 n.1, p.185-211, Jan. 1986 [doi>10.1137/0907014]
• 20: Bo Kågström , Axel Ruhe, Algorithm 560: JNF, An Algorithm for Numerical Computation of the Jordan Normal Form of a Complex Matrix [F2], ACM Transactions on Mathematical Software (TOMS), v.6 n.3, p.437-443, Sept. 1980 [doi>10.1145/355900.355917]
• 21: Bo Kågström , Axel Ruhe, An Algorithm for Numerical Computation of the Jordan Normal Form of a Complex Matrix, ACM Transactions on Mathematical Software (TOMS), v.6 n.3, p.398-419, Sept. 1980 [doi>10.1145/355900.355912]
• 22: KRONECKER, L. Algebraische Reduction der Schaaren Bilinearer Formen. S. B. Akad., 1890, 763-776.
• 23: KUBLANOVSKAYA, V. On a method of solving the complete eigenvalue problem of a degenerate matrix. USSR Comput. Math. Math. Phys. 6 (1968), i 14.
• 24: KUBLXr4OV~~&, V. An approach to solving the spectral problem of A AB. In Matrzx Pencils, Lecture Notes in Mathematics, Vol. 973, B. K~gstr6in and A. Ruhe, Eds., Springer- Verlag, Berlin, 1983, 17-29.
• 25: KUmJANOVSt~~A, V. AB-algorithm and its modifications for the spectral problem of linear pencils of matrices. Numer. Math. 43 (1984), 329-342.
• 26: KUBLANOVSKAYA, V, AND CHAZANOV, V g. Spectral problems for matrix pencils, methods and algorithms, part I (in Russian). Preprint LOMIP-2-88, USSR Academy of Sciences, Leningrad, 1988.
• 27: PAINE, C. Properties of numerical algorithms related to computing controllability IEEE Trans. Auto. Cntr. AC-26, I (1981), 130-138
• 28: PAIGE, C., AND SAUNDERS, M. Towards a generahzed singular value decomposition. SIAM J. Numer. Anal. 15 (1981), 241-256.
• 29: POKRZYWA, A. On perturbations and the equivalence orbit of a matrix pencil Lzn. Alg Appl. 82 (1986), 99 121.
• 30: SMITH, B. T., BOYLE, J. M., DONO^RRA, J. J., G^RBOW, B. S., I~BE, Y., KLEMA, V. C., AND MOLER, C B. Matrtx Eigensystem Rouhnes EISPACK Outde. Lecture Notes tn Computer Sczence, Springer-Verlag, Berlin, 1976.
• 31: STEWART, G.W. On the sensitivity of the eigenvalue problem A_r = ABx. SIAM J. Numer Anal. 9, 4 (1972), 669 686.
• 32: STEWART, G. W. Error and perturbation bounds for subspaces associated with certain eigenvalue problems. SIAM Rev. 15, 4 (Oct. 1973), 727-764
• 33: STEWART, G. W Gershgorin theory tbr the generalized eigenproblem Ax = ABx. Math. Comput 29, 130 (1975), 600 606.
• 34: SUN, J. G Orthogonal projections and the perturbation of the eigenvalues of singular pencils. J. Comput. Math. (China) i (1983), 63 74.
• 35: SUN, J G. Perturbation analysis for the generalized eigenvalue and generalized singular value problem. In Mutrzx Pencils, Lecture Notes zn Mathematzcs, Vol. 973, B. Kdgstroin and A. Ruhe, Eds., Springer-Verlag, Berlin, 1983, 221 244
• 36: SUN, J.G. Gershgorin type theorem and the perturbations of the eigenvalues of a singular pencil. Chmese J. Numer Math. Appl. 10, I (1988), 1-13.
• 37: VAN DOOREN, P. The computation of Kronecker's canonical form of a singular pencil LzT~. Alg. Appl. 27 (1979), 103 141.
• 38: VAN DOOREN, P The generalized eigenstructure problem in linear system theory. IEEE Trans. Aut. Cntr. AC-26 (1981), 111-128.
• 39: VAN DOOREN, P. Reducing subspaces: Computational aspects and apphcations in linear systems theory. In Procee&ngs of the 5th International Conference on Analysts and Optzrntzation of Systems (1982), Lecture Notes on Control and Informatzon Sczences, Vol. 44, Springer-Verlag, 1983.
• 40: VAN DOOREN, P. Reducing subspaces: Definitions, properties and algorithms. In Matrzx Pencils, Lecture Notes in Mathemattcs, Vol. 973, B. Kdgstrom and A. Ruhe, Eds.. Springer- Verlag, Berlin, 1983, 58-73.
• 41: VAN LOAN, C. Computing the CS and the generalized singular value decompositions. Numer. Math , 46, 4 (1985), 76-83.
• 42: WATERHOUSE, W. The codimension of singular matrix pairs. Ltn. Alg. Appl. 57 1984, 227 245.
• 43: WILKiNSON, J H. Linear differential equations and Kronecker's canonical form. In Recent Advances in Numerical Analysis, C de Boor and G. Golub, Eds. Academic Press, 1978, 231-265.
• 44: WILKINSON, J. H. Kronecker's canonical form and the QZ algorithm. Lm. Alg. Appl. 28 (1979), 285 303
• 45: WONHAM, M. Linear Multivartable Control Theory: A Geometrtc Approach, 2nd Ed. Springer-Verlag, New York, 1979.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Conditioning
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Reliability, Theory

Keywords:
Kronecker canonical form, Schur decomposition, controllable subspace, generalized eigenvalues, ill-posed problem, matrix pencils, reducing subspaces, uncontrollable modes