Accurate Singular Values and Differential QD Algorithms

Abstract

We have discovered a new implementation of the qd algorithm that has a far wider domain of stability than Rutishauser's version. Our algorithm was developed from an examination of the LR-Cholesky transformation and can be adapted to parallel computation in stark contrast to traditional qd. Our algorithm also yields useful a posteriori upper and lower bounds on the smallest singular value of a bidiagonal matrix. The zero-shift bidiagonal QR of Demmel and Kahan computes the smallest singular values to maximal relative accuracy and the others to maximal absolute accuracy with little or no degradation in efficiency when compared with the LINPACK code. Our algorithm obtains maximal relative accuracy for all the singular values and runs at least four times faster than the LINPACK code. qd, LR algorithm, Cholesky decomposition, singular values, SVD, bidiagonal matrices.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1992
Accession Number
ADA256582

Entities

People

  • Beresford N. Parlett
  • K. V. Fernando

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • Air Platforms
  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Applied Mathematics
  • Arithmetic
  • Arithmetic Units
  • Complex Variables
  • Computations
  • Eigenvalues
  • Equations
  • Error Analysis
  • Errors
  • Floating Point Operations
  • Mathematics
  • Notation
  • Rational Functions
  • Square Roots
  • Theorems

Readers

  • Computational Modeling and Simulation
  • Linear Algebra