A Quasi-Separable Approach to Solve the Symmetric Definite Tridiagonal Generalized Eigenvalue Problem
Raf Vandebril, Gene Howard Golub, Marc Van Barel · SIAM Journal on Matrix Analysis and Applications · 2009
We present a new fast algorithm for solving the generalized eigenvalue problem $T\mathbf{x}=\lambda S\mathbf{x}$, in which both T and S are real symmetric tridiagonal matrices and S is positive definite. A method for solving this problem is to compute a Cholesky factorization $S=LL^T$ and solve the equivalent symmetric standard eigenvalue problem $L^{-1}TL^{-T}(L^T\mathbf{x})=\lambda(L^T\mathbf{x})$. We prove that the matrix $L^{-1}TL^{-T}$ is quasi-separable; that is, all submatrices taken out of its strictly lower triangular part have rank at most 1. We show how to efficiently compute the $\mathcal{O}(n)$ parameters defining $L^{-1}TL^{-T}$ and review eigensolvers for quasi-separable matrices. Our approach shows that by fully exploiting the structure, the eigenvalues of $T\mathbf{x}=\lambda S\mathbf{x}$ can be computed in $\mathcal{O}(n^2)$ operations, as opposed to the $\mathcal{O}(n^3)$ operations for standard methods such as the so-called Cholesky-$QR$ method. It will be shown that the computation of the representation of this quasi-separable matrix is only linear in time, and numerical experiments will illustrate the effectiveness of the presented approach.