The Bidiagonal Singular Value Decomposition and Hamiltonian Mechanics

Authors:
  • PDPercy Deift
    Percy Deift
  • JDJames Demmel
    James Demmel
  • LLLuen-Chau Li
    Luen-Chau Li
  • CTCarlos Tomei
    Carlos Tomei

Abstract
Computing the singular value decomposition of a bidiagonal matrix B is considered. This problem arises in the singular value decomposition of a general matrix, and in the eigenproblem for a symmetric positive-definite tridiagonal matrix. It is shown that if the entries of B are known with high relative accuracy, the singular values and singular vectors of B will be determined to much higher accuracy than the standard perturbation theory suggests. It is also shown that the algorithm in [Demmel and Kahan, SIAM I. Sci. Statist. Comput., 11 (1990), pp. 873–912] computes the singular vectors as well as the singular values to this accuracy. A Hamiltonian interpretation of the algorithm is also given, and differential equation methods are used to prove many of the basic facts. The Hamiltonian approach suggests a way to use flows to predict the accumulation of error in other eigenvalue algorithms as well.

This publication has 23 references indexed in Scilit: