ON COMPUTING ACCURATE SINGULAR-VALUES AND EIGENVALUES OF MATRICES WITH ACYCLIC GRAPHS

It is known that small relative perturbations in the entries of a bidi agonal 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 matrices with acyclic graphs with tiny componentwise relative backward error. This class includes tridi agonal matrices, arrow matrices, and exponentially many others.