Title: Computing the smallest singular value of tridiagonal matrices via semiseparable matrices
Authors: Vandebril, Raf
Van Barel, Marc
Mastronardi, Nicola #
Issue Date: 2006
Conference: 12th International Congress on Computational and Applied Mathematics location:Leuven, Belgium date:July 10-14, 2006
Abstract: 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.
Publication status: published
KU Leuven publication type: IMa
Appears in Collections:NUMA, Numerical Analysis and Applied Mathematics Section
Electrical Engineering - miscellaneous
# (joint) last author

Files in This Item:
File Status SizeFormat
smeig.pdf Submitted 499KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.