HMDR and FMDR algorithms for the generalized eigenvalue problem (Q1115100)

The authors present a new algorithm for the solution of the generalized eigenproblem \(Ax=\lambda Bx\), with \(A,B\in {\mathbb{R}}^{n\times n}\). The matrix B may be reduced to a positive semidefinite diagonal matrix D by the transformation \(\pi BQ^ T=_ R\), where \(\pi\) is a permutation matrix and Q is orthogonal; this implies that the standard form may be written in the form \(Ax=\lambda Dx.\) The MDR transformation is essentially two-dimensional and is designed to annihilate an element of A in an efficient well-conditioned manner [cf. \textit{A. Bunse-Gerstner}, ibid. 58, 43-68 (1984; Zbl 0575.65028)]. The current paper presents two variants of this method; the HMDR is based on Householder transformations and the FMDR is based on a fast MDR which is nearly as well conditioned but requires less computational work. To overcome problems arising in the presence of infinite eigenvalues a new `preprocessing' procedure is described. A comparison of the number of `flops' required by the new method as against the commonly used QZ algorithm shows a 60\% improvement over the latter. The stability of the new method, which in principle resembles the QR algorithm, is similar to that of the MDR method.