Accurate SVDs of Structured Matrices
James Weldon Demmel · 1998
We present new O(n 3 ) algorithms to compute very accurate SVDs 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. LAPACK Working Note 130 University of Tennessee Computer Science Report ut-cs-97-375 1 Introduction The singular value decomposition (SVD) of a real matrix G is the factorization G = U \\SigmaV T where U and V are orthogonal matrices and \\Sigma is nonnegative and diagonal. If G is m-by-n, with m n (otherwise transpose G), then U is m-by-n, \\Sigma = diag(oe 1 ; :::; oe n ) with oe 1 \\Delta \\Delta \\Delta oe n 0, and V is n-by-n. We call the columns u i of U = [u 1 ; :::; u n ] the left singular vectors, the columns v i of V = [v 1 ; :::; v n ] the right singular vectors, and the oe i the sing...