reviewernum: 9689
revieweremail: znojil@ujf.cas.cz
zblno: DE015196101
author: Chandrasekaran, S.
shorttitle: Symmetric definite generalized eigenvalue algorithm
source: SIAM J. Matrix Anal. Appl. 21, No. 4, 1202-1228 (2000)
rpclass: 65F15
rsclass: 65K05; 15A18; 15A22; 15A23
keywords: generalized eigenvalues, eigenvectors,error analysis, deflation, perturbation bounds, pencils, stable algorithm
revtext: Generalized eigenvalue problem Ax = $\lambda$ Bx is considered with symmetric A and B and positive definite B. The author proposes a new algorithm. It is designed to combine the merits of the strict simultaneous diagonalization of both A and B (often violated when using the simple-minded factorization of B in finite precision) and of keeping all the eigenvalues real (violated, e.g., by QZ algorithm). Its essence lies in a factorization which admits a deflation of the eigenvectors, roughly speaking, in a decreasing order of their eigenvalues. This guarantees the stability for, admittedly, singular A. Proofs are provided via an extensive analysis of error propagation, incorporating an interesting perturbation bound. The formalism is presented in infinite precision, with subsequent demonstration of the ``survival" of the scheme when the (numerically) vanishing eigenvalues have to be deflated as strict zeros. It is conjectured that the number of operations (recomputations) grows logarithmically with the precision. Efficiency and robustness are demonstrated via numerical tests.