On Computing Accurate Singular Values and Eigenvalues of Acyclic Matrices
Technical rept. 1 Oct 1991-31 Mar 1992
NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF MATHEMATICS
Pagination or Media Count:
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.
- Numerical Mathematics