A Cholesky LR algorithm for the positive definite symmetric diagonal-plus-semiseparable eigenproblem

We present a Cholesky LR algorithm with Laguerre’s shift for computing the eigenvalues of a positive definite symmetric diagonal-plus-semiseparable matrix. By exploiting the semiseparable structure, each step of the method can be performed in linear time.