On computing the eigenvectors of a class of structured matrices

Nicola Mastronardi

A real symmetric matrix of order n has a full set of orthogonal eigenvectors. The approach often used to solve the eigenproblem reduces the dense symmetric matrix first into a symmetric structured one, i.e., a tridiagonal matrix or a semiseparable matrix. This step is accomplished in O(n3) operations. Once the latter symmetric structured matrix is available, the eigenvalues of the latter matrix are computed in an iterative fashion by means of the QR method in O(n2) operations.

In principle, the whole set of eigenvectors of the symmetric structured matrix can be computed by means of inverse iteration in O(n2) operations.

The problem in this approach is that the computed eigenvectors may not be numerically orthogonal if clusters are present in the spectrum. To enforce orthogonality the Gram-Schmidt procedure is used, requiring O(n3) operations in the worst case.

In this talk we consider a new fast and stable method (O(n2) operations) to compute all the eigenvectors of tridiagonal and semiseparable matrices which does not suffer from the presence of clusters in the spectrum. Also the problem of computing the eigenvectors of unsymmetric matrices is handled.