Orthogonal Eigenvectors and Relative Gaps
The authors present and analyze a new method, Algorithm Getvec, for computing eigenvectors of symmetric tridiagonal matrices factored as \(LDL^T\), with \(D\) diagonal and \(L\) unit bidiagonal. If an eigenpair is well behaved in a certain sense with respect to the factorization, the algorithm is shown to compute an approximate eigenvector which is accurate to working precision. As a consequence, all the eigenvectors computed by the algorithm come out numerically orthogonal to each other without making use of any reorthogonalization process. The properties that must be satisfied in order for Algorithm Getvec to compute an accurate approximation to eigenvector \(v\) (corresponding to eigenvalue \(\lambda\) of \(LDL^T\)) are that (i) both \(\lambda\) and \(v\) must be determined to high relative accuracy by the parameters in \(L\) and \(D\) and (ii) the relative gap between \(\lambda\) and its nearest neighbor \(\mu\) in the spectrum should exceed tol; \(| \lambda - \mu | > tol | \lambda | \). The key is first applying a \(qd\)-type algorithm to the factored matrix \(LDL^T\) and then a fine-tuned version of inverse iteration especially adapted to this situation. Since the computational cost is \(O(n)\) per eigenvector for an \(n \times n\) matrix, the proposed algorithm is the central step of a more ambitious algorithm which, at best (that is, when all eigenvectors are well-conditioned), would compute all eigenvectors of an \(n \times n\) symmetric tridiagonal at \(O(n^2)\) cost, a great improvement over existing algorithms. The authors compare Algorithm Getvec with others algorithms for different examples at the end of the paper.
- Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices
- scientific article; zbMATH DE number 3930234
- For tridiagonals \(T\) replace \(T\) with \(LDL\)
- scientific article; zbMATH DE number 879770
- An Orthogonal High Relative Accuracy Algorithm for the Symmetric Eigenproblem
- Fernando's solution to Wilkinson's problem: An application of double factorization
- Accurate ordering of eigenvectors and singular vectors without eigenvalues and singular values.
- Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices
- For tridiagonals \(T\) replace \(T\) with \(LDL\)
- A periodic qd-type reduction for computing eigenvalues of structured matrix products to high relative accuracy
- Computing singular value decompositions of parameterized matrices with total nonpositivity to high relative accuracy
- The orthogonal Rayleigh quotient iteration (ORQI) method
- An \({\mathcal O}(n^{2})\) algorithm for the bidiagonal SVD
- Relatively robust representations of symmetric tridiagonals
- Numerical methods for accurate computation of the eigenvalues of Hermitian matrices and the singular values of general matrices
- A real triple dqds algorithm for the nonsymmetric tridiagonal eigenvalue problem
- Accurate eigenvalues of some generalized sign regular matrices via relatively robust representations
- A shift strategy for superquadratic convergence in the dqds algorithm for singular values
- Twisted factorization of a banded matrix
- Evaluation of small elements of the eigenvectors of certain symmetric tridiagonal matrices with high relative accuracy
- A fast symmetric SVD algorithm for square Hankel matrices
- Simulation of laser propagation in a plasma with a frequency wave equation
- On sensitivity of Gauss-Christoffel quadrature
- Computing Fundamental Matrix Decompositions Accurately via the Matrix Sign Function in Two Iterations: The Power of Zolotarev's Functions
- A twisted factorization method for complex symmetric tridiagonal eigenvalue decomposition
- Structured Eigenvalue Problems
- Computing eigenvectors of block tridiagonal matrices based on twisted block factorizations
- The singular value decomposition: anatomy of optimizing an algorithm for extreme scale
- scientific article; zbMATH DE number 879770 (Why is no real title available?)
- A note on generating finer‐grain parallelism in a representation tree
- Subsampling algorithms for semidefinite programming
- Restructuring the tridiagonal and bidiagonal QR algorithms for performance
- Fast linear inversion for highly overdetermined inverse scattering problems
- The Godunov-inverse iteration: A fast and accurate solution to the symmetric tridiagonal eigenvalue problem
- Vectorization of a Thread-Parallel Jacobi Singular Value Decomposition Method
- On a special basis of approximate eigenvectors with local supports for an isolated narrow cluster of eigenvalues of a symmetric tridiagonal matrix
- A note on the dqds algorithm with Rutishauser's shift for singular values
- Computing eigenvalues of quasi-rational Said-Ball-Vandermonde matrices
- Estimation of spectral gaps for sparse symmetric matrices
- DBDSVDMR3: An MRRR-Based Bidiagonal SVD Solver Built from DSTEGR
- On computing the eigenvectors of a class of structured matrices
- Rigorous proof of cubic convergence for the dqds algorithm for singular values
- Superquadratic convergence of DLASQ for computing matrix singular values
This page was built for publication: Orthogonal Eigenvectors and Relative Gaps
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4650963)