A QUASI-SEPARABLE APPROACH TO SOLVE THE SYMMETRIC DEFINITE TRIDIAGONAL GENERALIZED EIGENVALUE PROBLEM

摘要

We present a new fast algorithm for solving the generalized eigenvalue problemTx =λ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 = LL~Tand solvethe equivalent symmetric standard eigenvalue problem L~(-1)TL~(-T)(L~Tx) =(Tx).We prove thatthe matrix L~(-1)TL~(-T)is quasi-separable; that is, all submatrices taken out of its strictly lowertriangular part have rank at most 1. We show how to efficiently compute the O(n) parametersdefining L~(-1)TL~(-T)and review eigensolvers for quasi-separable matrices. Our approach shows thatby fully exploiting the structure, the eigenvalues of Tx = λ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 onlylinear in time, and numerical experiments will illustrate the effectiveness of the presented approach.