A quasiseparable approach to solve the definite generalized eigenvalue problem

摘要

We present a new fast algorithm for solving the generalized eigenvalue problem Tx = lambda Sx, 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 = LLT and solve the equivalent symmetric standard eigenvalue problem L-1TL-T (L-T x) = lambda(L-T x). We prove that the matrix L-1TL-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 O(n) parameters defining L-1TL-T and review eigensolvers for quasi-separable matrices. Our approach shows that by fully exploiting the structure, the eigenvalues of Tx = lambda Sx can be computed in O(n(2)) operations, as opposed to the 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.