Computing the smallest singular value of tridiagonal matrices via semiseparable matrices
Raf Vandebril, Marc Van Barel, Nicola Mastronardi · Lirias · 2006
In this talk we present a new fast method for computing the smallest absolute eigenvalue, i.e. the smallest singular value, of symmetric tridiagonal matrices. Firstly the tridiagonal matrix T is inverted, leading to a semiseparable matrix S. Different techniques for inverting the matrix T are provided, based on the LU-decomposition, the QR-decomposition, and direct inversion. Secondly the knowledge of the $Q$ factor of the QR-method applied on the matrix $S$ is used for performing an orthogonal similarity transformation on the matrix T. The shift in the QR-factorization of the matrix S is chosen in such a way that the QR-method will converge to the largest eigenvalue of the matrix S. This orthogonal transformation matrix Q (consisting of Givens transformations) is then applied on the tridiagonal matrix T, leading to a forced convergence of T to an approximation of smallest eigenvalue. Moreover, theoretically, this special orthogonal transformation Q, will not disturb the structure of the tridiagonal matrix T. Several approaches are tested. One approach consists of continuing the performance of the QR-method on the matrix $S$ and hence also on the matrix T. A second approach consists of reinverting the tridiagonal matrix after each QR-step. A third approach uses the first approximation, for starting the QR-method on the tridiagonal matrix itself. Numerical experiments are provided, investigating the stability of the inversion methods, comparing the accuracy of the smallest eigenvalue with both the inverse of the largest eigenvalue of S and the computed smallest eigenvalue via this technique. If time permits we will also illustrate the applicability of his technique to semiseparable (plus diagonal) matrices.