THE GENERALIZED SCHUR DECOMPOSITION OF AN ARBITRARY PENCIL-A - LAMBDA-B - ROBUST SOFTWARE WITH ERROR-BOUNDS AND APPLICATIONS .1. THEORY AND ALGORITHMS

Robust software with error bounds for computing the generalized Schur decomposition of an arbitrary matrix pencil A - lambdaB (regular or singular) is presented. The decomposition is a generalization of the Schur canonical form of A - lambdaI 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.