TW 595

Andrey Chesnokov, Marc Van Barel, Nicola Mastronardi, and Raf Vandebril
Homotopy algorithm for the symmetric diagonal-plus-semiseparable eigenvalue problem

Abstract

A dense symmetric matrix can be reduced into a similar diagonal-plus-semiseparable one by means of orthogonal similarity transformations. This makes such a diagonal-plus-semiseparable representation a good alternative to the tridiagonal one when solving dense linear algebra problems. For symmetric tridiagonal matrices there have been developed different homotopy eigensolvers.

We present a homotopy method combined with a divide-and-conquer approach to find all the eigenvalues and eigenvectors of a diagonal-plus-semiseparable matrix. The basic mathematical theory behind this algorithm is reviewed and is followed by a discussion of the numerical considerations of the actual implementation. First, we split the original matrix into two smaller matrices of the same structure, and later we join the eigendecompositions of these smaller matrices. On this way a complete eigenvalue problem for a diagonal plus rank-one matrix is solved by a homotopy method. Deflation techniques are implemented, leading to a fast convergence of the homotopy method.

The validity of the approach is illustrated by numerical experiments.

report.pdf (342K) / mailto: M. Van Barel