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

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. The second part of this two-part paper describes the computed generalized Schur decomposition in more detail and the software, and presents applications and an example of its use. Background theory and algorithms for the decomposition and its error bounds are presented in Part I of this paper.

REFERENCES

• 1: BEELEN, T., VAN DOOREN, P., AND VERHAEGEN, M. A class of staircase algorithms for generalized state space systems In Proceedmg's of the Amerzcan Control Coz~ference (Seattle, Wash., 1986), 425-426.
• 2: BISCHOF, C., DEMMEL, J., DONGARRA, J., Du CROZ, J., GREENBAUM, A., HAMMARLING, S., AND SORENSEN, D. LAPACK Prowsional Contents Mathematics and Computer SeJenee Division Rep. ANL-88-38, Argonne National Laboratory, Argonne, II1., 1988
• 3: BUNCH, J., DONGARRA, J, MOLER, C., AND STEWART, G.W. LINPACK User's Guide. SIAM, Philadelphia, 1979.
• 4: DEMMEL, J. LAPACK: A portable linear algebra hbrary for supercomputers. In Proceedzngs of the 1989 IEEE Control Systems Soclety Workshop on Computer-Aided Control System Destgzz (Tampa, Fla., Dec 1989). IEEE, New York.
• 5: 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 I: theory and algorithms, ACM Transactions on Mathematical Software (TOMS), v.19 n.2, p.160-174, June 1993 [doi>10.1145/152613.152615]
• 6: 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]
• 7: DEMMEL, J., AND KA~GSTROM, B. Stably computing the Kronecker structure and reducing subspaces of singular pencils A - AB for uncertain data. In Large Scale Elgenvalue Problems. North-Holland, Amsterdam, 1986, 283-323.
• 8: James Demmel , W. Kahan, Accurate singular values of bidiagonal matrices, SIAM Journal on Scientific and Statistical Computing, v.11 n.5, p.873-912, September 1990 [doi>10.1137/0911052]
• 9: 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]
• 10: GARBOW, B. S., BOYLE, J. M., DONGARRA, J. J., AND MOLER, C. B. Matrix Eigensystem Routtnes--EISPACK Guide Extension, Lecture Notes in Computer Science, vol. 51. Springer-Verlag, Berlin, 1977.
• 11: GOLUB, G., AND WILKINSON, J.H. Ill-conditioned eigensystems and the computation of the Jordan canonical form. SIAM Rev. 18, 4 (1976), 578-619.
• 12: 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]
• 13: 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]
• 14: 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]
• 15: KA~GSTROM, B., AND WESTIN, L. GSYLV--Fortran routines for the generalized Schur method with Dif-l-estimators for solving the generalized Sylvester equation. Rep. UMINF-132.86, Inst. of Information Processing, Univ. of Ume~, S-901 87 Ume~, Sweden, 1987.
• 16: KA~GSTR()M, B., AND WESTIN, L. Generalized Schur methods with condition estimators for solving the generalized Sylvester equation. IEEE Trans. Autom. Contr. 34, 4 (1989), 745 751.
• 17: SMITH, B. T., BOYLE, J. M., DONGARRA, J. J., GARBOW, B. S., IKEBE, Y., KLEMA, V. C., AND MOLER, C.B. Matrix E~gensystem Routines--EISPACK Guide. Lecture Notes in Computer Science, vol. 6. Springer-Verlag, Berlin, 1976.
• 18: VAN DOOREN, P. Reducing subspaces: Computational aspects and applications in linear systems theory. In Proceedings of the 5th International Conference on Analysis and Optimization of Systems (1982). Lecture Notes on Control and Information Sciences, vol. 44. Springer-Verlag, New York, 1983.
• 19: P. Van Dooren, Algorithm 590: DSUBSP and EXCHQZ: FORTRAN Subroutines for Computing Deflating Subspaces with Specified Spectrum, ACM Transactions on Mathematical Software (TOMS), v.8 n.4, p.376-382, Dec. 1982 [doi>10.1145/356012.356017]
• 20: VAN DOOREN, P. The generalized eigenstructure problem in linear system theory. IEEE Trans. Aut. Contr. AC-26 (1981), 111-128.
• 21: VAN DOOREN, P. The computation of Kronecker's canonical form of a singular pencil. Lm. Alg. Appl., 27 (1979), 103-141.

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
      F.4.1 Mathematical Logic

  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