A new algorithm for the computation of the smallest eigenvalue of a symmetric matrix and its eigenspace

B. Jansen, C. Roos, T. Terlaky

The problem of finding the smallest eigenvalue and the corresponding eigenspace of a symmetric matrix is stated as a semidefinite optimization problem. A straightforward application of nowadays more or less standard routines for the solution of semidefinite problems yields a new algorithm for the smallest eigenvalue problem; the approach not only yields the smallest eigenvalue, but also a symmetric positive semidefinite (SPSD) matrix whose column space is equal to the eigenspace for the smallest eigenvalue. It is shown that the predictor-corrector method yields a polynomial time algorithm which, with a suitable choice of the step size, asymptotically is quadratically convergent.

Report 95-70, Faculty of Technical Mathematics and Computer Science, Delft University of Technology, Delft, 1995.

Contact: t.terlaky@twi.tudelft.nl