Accurate Singular Value Decompositions of Structured Matrices
James Weldon Demmel · SIAM Journal on Matrix Analysis and Applications · 2000
We present new O(n 3 ) algorithms to compute very accurate singular value decompositions of Cauchy matrices, Vandermonde matrices, and related "unit-displacement-rank" matrices. These algorithms compute all the singular values with guaranteed relative accuracy, independent of their dynamic range. In contrast, previous O(n 3 ) algorithms can potentially lose all relative accuracy in the tiniest singular values.