Evaluating products of matrix pencils and collapsing matrix products

This paper describes three numerical methods to collapse a formal product o f p pairs of matrices P = Pi (p=1)(k=0) E-k(-1).4(k) down to the product of a single pair (E) over cap (-1) (A) over cap. In the setting of linear rel ations. the product formally extends to the case in which some of the E-k's are singular and it is impossible to explicitly form P as a single matrix. The methods differ in flop count, work space, and inherent parallelism. Th ey have in common that they are immune to overflows and use no matrix inver sions. A rounding error analysis shows that the special case of collapsing two pairs is numerically backward stable. Copyright (C) 2001 John Wiley & S ons, Ltd.