Title: An implicit QR algorithm for semiseparable matrices, to compute the eigendecomposition of symmetric matrices
Authors: Vandebril, Raf
Van Barel, Marc
Mastronardi, Nicola
Issue Date: Aug-2003
Publisher: Department of Computer Science, K.U.Leuven, Leuven, Belgium
Series Title: TW Reports vol:TW367
Abstract: The QR algorithm is one of the classical methods to compute
the eigendecomposition of a matrix. If it is applied on a dense n
× n
matrix, this algorithm requires O(n3 ) operations per iteration step.
To reduce this complexity for a symmetric matrix to O(n), the original matrix is first reduced to tridiagonal form using orthogonal
similarity transformations.
In the report [Van Barel, Vandebril, Mastronardi 2003] a reduction from a symmetric matrix into a similar semiseparable one is
described. In this paper a QR algorithm to compute the eigenvalues of semiseparable matrices is designed where each iteration step
requires O(n) operations. Hence, combined with the reduction to
semiseparable form, the eigenvalues of symmetric matrices can be
computed via intermediate semiseparable matrices, instead of tridiagonal ones.
The eigenvectors of the intermediate semiseparable matrix will be
computed by applying inverse iteration to this matrix. This will be
achieved by using an O(n) system solver, for semiseparable matrices.
A combination of the previous steps leads to an algorithm for
computing the eigenvalue decompositions of semiseparable matrices.
Combined with the reduction of a symmetric matrix towards semiseparable form, this algorithm can also be used to calculate the eigenvalue decomposition of symmetric matrices. The presented algorithm has the same order of complexity as the tridiagonal approach, but has larger lower order terms. Numerical experiments illustrate the complexity and the numerical accuracy of the proposed
Publication status: published
KU Leuven publication type: IR
Appears in Collections:NUMA, Numerical Analysis and Applied Mathematics Section
Electrical Engineering - miscellaneous

Files in This Item:
File Status SizeFormat
TW367.pdf Submitted 289KbAdobe PDFView/Open


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