Bidiagonal singular value decomposition and Hamiltonian mechanics

Percy Deift, James Demmel, Luen Chau Li, Carlos Tomei

Research output: Contribution to journalArticle

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 J. 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.

Original languageEnglish (US)
Pages (from-to)1463-1516
Number of pages54
JournalSIAM Journal on Numerical Analysis
Volume28
Issue number5
DOIs
StatePublished - 1991

ASJC Scopus subject areas

  • Numerical Analysis
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Bidiagonal singular value decomposition and Hamiltonian mechanics'. Together they form a unique fingerprint.

  • Cite this