A generalization of the divide and conquer algorithm for the symmetric tridiagonal eigenproblem
This work provides a faster algorithm for computing eigenvalues of symmetric tridiagonal matrices with rank-two modifications, which is an incremental improvement over existing methods.
The authors generalize Cuppen's divide-and-conquer algorithm for symmetric tridiagonal eigenproblems to handle rank-two modifications, introducing a new deflation technique and secular equation. Numerical results show their algorithm computes eigenvalues twice as fast as Cuppen's original method.
In this paper, we present a generalized Cuppen's divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem. We extend the Cuppen's work to the rank two modifications of the form $A =T +β_1\bw_1\bw_1^T + β_2\bw_2\bw_2^T$, where $T$ is a block tridiagonal matrix having three blocks. We introduce a new deflation technique and obtain a secular equation, for which the distribution of eigenvalues is nontrivial. We present a way to count the number of eigenvalues in each subinterval. It turns out that each subinterval contains either none, one or two eigenvalues. Furthermore, computing eigenvectors preserving the orthogonality are also suggested. Some numerical results, showing our algorithm can calculate the eigenvalue twice as fast as the Cuppen's divide-and-conquer algorithm, are included.