January 23, 2006

Yuli Eidelman

Title: On eigenvalue problem for quasiseparable matrices

Abstract:

We discuss spectral properties of quasiseparable matrices. This class of matrices contains at least three well-known classes of structured matrices: diagonal plus semiseparable matrices, band matrices and unitary Hessenberg matrices.

The first part of the talk is focused on quasiseparable of order one matrices. We present various recursive relations for characteristic polynomials of the principal submatrices of such matrices and obtain a $ O(N^2)$ algorithm for the computation of the coefficients of their characteristic polynomials. These recursions generalize some well-known results for the polynomials orthogonal on the real line and for the Szego polynomials. We obtain conditions where an eigenvalue of the quasiseparable matrix is simple and derive the explicit formula for the corresponding eigenvector. Next we extend the method of computation of the eigenvectors to the case where the eigenvalues are not simple. The computation of every eigenvector is performed using a linear complexity algorithm.

In the second part of the talk a fast $ QR$ iteration algorithm for quasiseparable of any order Hermitian matrices with $ O(N)$ operations per step is discussed.

This is joint work with Israel Gohberg and Vadim Olshevsky.