On computing accurate singular values and eigenvalues of matrices with acyclic graphs (Q2365723)

The authors prove that the following two statements are equivalent: (1) 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. (2) Its associated bipartite graph is acyclic. Also an algorithm to compute the singular values of such a matrix to high relative accuracy is developed. The same algorithm can compute eigenvalues of symmetric matrices with acyclic graphs with tiny componentwise relative backward error.