An Efficient and Stable Algorithm for the Symmetric-Definite Generalized Eigenvalue Problem

DOI10.1137/S0895479897316308MaRDI QIDQ4509611zbMATH OpenFDO

Authors S. Chandrasekaran

Publication date 19 October 2000

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895479897316308

zbMATH Keywords

deflationeigenvectorserror analysisgeneralized eigenvalue problempencilsperturbation boundsstabilitystable algorithm

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15)

Review text

A 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 the 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.

Recommendations

• An Algorithm for $Ax = \lambda Bx$ with Symmetric and Positive-Definite A and B
• An Orthogonal High Relative Accuracy Algorithm for the Symmetric Eigenproblem
• An algorithm for the symmetric generalized eigenvalue problem
• Publication:4723165
• scientific article; zbMATH DE number 3969998

Cited in

(20)

• On a deflation method for the symmetric generalized eigenvalue problem
• HMDR and FMDR algorithms for the generalized eigenvalue problem
• An algorithm for symmetric generalized inverse eigenvalue problems
• On the complex Falk-Langemeyer method
• Newton's method in floating point arithmetic and iterative refinement of generalized eigenvalue problems
• Analysis of the Cholesky method with iterative refinement for solving the symmetric definite generalized eigenproblem
• High relative accuracy algorithms for the symmetric eigenproblem
• A Padé-based factorization-free algorithm for identifying the eigenvalues missed by a generalized symmetric eigensolver
• scientific article; zbMATH DE number 4143343 (Why is no real title available?)
• An Algorithm for $Ax = \lambda Bx$ with Symmetric and Positive-Definite A and B
• Globally and Rapidly Convergent Algorithms for Symmetric Eigenproblems
• Stable and efficient algorithm for selected eigenvalues and eigenvectors of the general symmetric eigenproblem
• scientific article; zbMATH DE number 3997025 (Why is no real title available?)
• Accurate computation of generalized eigenvalues of regular SR-BP pairs
• A Quasi-Separable Approach to Solve the Symmetric Definite Tridiagonal Generalized Eigenvalue Problem
• Using the discriminant in a numerically stable symmetric 3 × 3 direct eigenvalue solver
• Automatic code selection for the dense symmetric generalized eigenvalue problem using ATMathCoreLib
• Symmetric-diagonal reductions as preprocessing for symmetric positive definite generalized eigenvalue solvers
• Spectral transformation for the dense symmetric semidefinite generalized eigenvalue problem
• Basis selection in LOBPCG

This page was built for publication: An Efficient and Stable Algorithm for the Symmetric-Definite Generalized Eigenvalue Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4509611)