Title: A quasiseparable approach to solve the definite generalized eigenvalue problem
Authors: Vandebril, Raf ×
Van Barel, Marc
Mastronardi, Nicola #
Issue Date: 2009
Publisher: Society for Industrial and Applied Mathematics
Series Title: SIAM Journal on Matrix Analysis and Applications vol:31 issue:1 pages:154-174
Abstract: 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.
ISSN: 0895-4798
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Numerical Analysis and Applied Mathematics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
Vandebril_VanBarel_Mastronardi_2008.pdfOA article Published 445KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science