TL;DR
This paper introduces a new algorithm, "Getvec," that computes eigenvectors of symmetric tridiagonal matrices with high relative accuracy and numerical orthogonality. This is achieved by leveraging a bidiagonal factorization and a novel "twisted" factorization, leading to significant speedups over existing methods, especially for matrices with clustered eigenvalues.
What Problem Does This Paper Address?
Computing eigenvectors of symmetric matrices is a fundamental problem in numerical linear algebra. While existing methods like the QR algorithm can produce numerically orthogonal eigenvectors, they can be slow, especially for large matrices with clustered eigenvalues. Inverse iteration, on the other hand, is faster per eigenvector but can struggle with orthogonality when eigenvalues are close. The authors aim to bridge this gap by developing an algorithm that computes eigenvectors with both high relative accuracy and numerical orthogonality, ideally in O(n^2) time for all eigenvectors of an n x n matrix. This is particularly relevant for modern parallel computing where efficient eigenvector computation is crucial.
Methods
The core of the paper revolves around a new algorithm called Algorithm Getvec. It operates on a bidiagonal factorization (LDL^t) of a translated tridiagonal matrix, which is shown to be more robust than the standard tridiagonal representation for eigenvalue problems. The key steps involve:
- Differential qd transforms: These are novel, numerically stable algorithms (dstqds and dqds) used to compute "twisted" factorizations of the matrix (T - λI). These transforms are crucial for revealing the singularity of the matrix when λ is an approximate eigenvalue.
- Twisted factorization: Instead of a standard LDL^t factorization, Getvec uses a "twisted" factorization (NrDrNt) that is specifically designed to expose the eigenvector associated with an approximate eigenvalue. The choice of the "twist" index 'r' is critical and is determined by minimizing a specific value (γk) related to the singularity.
- Solving a linear system: The approximate eigenvector is then obtained by solving a linear system involving the twisted factors.
The authors emphasize the importance of "relative accuracy" and "relative gaps" between eigenvalues, arguing that these concepts are key to achieving accurate eigenvectors, especially when eigenvalues are close.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and numerical examples using constructed matrices and standard test cases.
Key Insights and Ideas
- Bidiagonal factorization is key: Representing a tridiagonal matrix as LDL^t is more robust for eigenvalue computations than using diagonal and off-diagonal elements directly, especially when dealing with potential numerical instability.
- "Twisted" factorization reveals eigenvectors: The novel twisted factorization (NrDrNt) is specifically designed to isolate and compute eigenvectors, particularly when eigenvalues are close.
- Relative gaps matter more than absolute gaps: For eigenvector accuracy, the relative separation between eigenvalues is more critical than their absolute separation.
- Differential qd transforms are essential for accuracy: These new transforms are shown to have attractive properties in the presence of roundoff errors, which are crucial for proving the algorithm's correctness.
- Accuracy implies orthogonality: The paper demonstrates that achieving high relative accuracy in eigenvector computation naturally leads to numerical orthogonality, eliminating the need for explicit reorthogonalization steps in many cases.
Key Results
- Algorithm Getvec: This new algorithm computes a single eigenvector of a symmetric tridiagonal matrix in O(n) time.
- High relative accuracy: For well-conditioned eigenpairs (where the relative gap between the eigenvalue and its neighbors exceeds a threshold), Getvec computes an eigenvector accurate to working precision.
- Numerical orthogonality: The computed eigenvectors are shown to be numerically orthogonal, a significant advantage over some existing methods.
- Speedups: The paper presents timing comparisons (Table 1) showing that Algorithm Getvec can be orders of magnitude faster than LAPACK and EISPACK routines for certain types of matrices, particularly those with clustered eigenvalues. For example, for a 2000x2000 matrix, Getvec takes 4.5 seconds compared to 343.9 seconds for LAPACK's DSTEBZ + DSTEIN.
- Theoretical guarantees: The paper provides rigorous theoretical bounds on the accuracy of the computed eigenvectors, relating them to the relative gaps and condition numbers.
Limitations and Future Work
- Limited to symmetric tridiagonal matrices: The current algorithm is specialized for symmetric tridiagonal matrices. Extending it to more general symmetric matrices would be a natural next step.
- "Well-behaved" eigenpairs: The algorithm's guarantee of high relative accuracy is for "well-behaved" eigenpairs, defined by a sufficiently large relative gap. Handling very tight clusters of eigenvalues still requires more sophisticated techniques (e.g., Algorithm MRRR mentioned in the paper).
- Further study of the middle term in bounds: The authors note that the middle term in their accuracy bound warrants further study, although they argue that it is often detectable in practice.
- Singular vector computation: The paper briefly discusses an extension to compute singular vectors of bidiagonal matrices, suggesting this as a future application.
- Parallelization: While the O(n) cost per eigenvector is beneficial for parallelization, the paper doesn't delve deeply into the parallel implementation details.
Summary updated