Department of Computer Science, K.U.Leuven, Leuven, Belgium
TW Reports vol:TW367
The QR algorithm is one of the classical methods to compute
the eigendecomposition of a matrix. If it is applied on a dense 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 ﬁrst reduced to tridiagonal form using orthogonal
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