On Computing Accurate Singular Values and Eigenvalues of Acyclic Matrices

Abstract

It is known that small relative perturbations in the entries of a bidiagonal matrix only cause small relative perturbations in its singular values, independent of the values of the matrix entries. In this paper we show that a matrix has this property if and only if its associated bipartite graph is acyclic. We also show how to compute the singular values of such a matrix to high relative accuracy. The same algorithm can compute eigenvalues of symmetric acyclic matrices with tiny component-wise relative backward error. This class includes tridragonal matfices, arrow matrices, and exponentially many others.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 07, 1992
Accession Number
ADA255892

Entities

People

  • James W. Demmel
  • William Gragg

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • California
  • Classification
  • Computer Science
  • Eigenvalues
  • Elimination
  • Equations
  • Error Analysis
  • Errors
  • Graph Theory
  • Mathematics
  • Minnesota
  • Perturbation Theory
  • Perturbations
  • Security
  • Theorems

Fields of Study

  • Mathematics

Readers

  • Linear Algebra