The Lanczos reduction to semiseparable matrices

Raf Vandebril

The Lanczos tridiagonalization is the classical way to compute an approximation of dominant singular subspaces. Recently, a similarity reduction of symmetric matrices in semiseparable form has been introduced [2]. The latter reduction has the same convergence properties as the Lanczos tridiagonalization for the "extremal" eigenvalues and it is based on Householder and Givens transformations.

The interesting feature of the latter algorithm is that, if gaps are present in the spectrum, after few steps the transformed matrix has almost a diagonal block structure, and the largest eigenvalues of the left­top block converge to the largest eigenvalues of the original matrix.

In this talk we consider a new reduction of a matrix in semiseparable form [1]. Similarly to the Lanczos tridiagonalization, the main computation of each step of the new algorithm is a product of the original matrix by a vector. This can be done in an efficient way exploiting the structure of the original matrix (i.e. sparsity, rank structure, low displacement rank structure, ...). Moreover, during the reduction the already partially computed semiseparable submatrix is almost block diagonal, and the largest eigenvalues of the left­top block converge to the largest eigenvalues of the original matrix.

References

  • Nicola Mastronardi, Mieke Schuermans, Marc Van Barel, Raf Vandebril, and Sabine Van Huffel. A Lanczos-like reduction of symmetric structured matrices into semiseparable ones. Calcolo, 2005. To appear.
  • Marc Van Barel, Raf Vandebril, and Nicola Mastronardi. An orthogonal similarity reduction of a matrix into semiseparable form. SIAM Journal on Matrix Analysis and Applications, 27(1):176­197, 2005.