We analyze when it is possible to compute the singular values and singular
vectors of a matrix with high relative accuracy. This means that: each comp
uted singular value is guaranteed to have some correct digits, even if the
singular values have widely varying magnitudes. This is in contrast to the
absolute accuracy provided by conventional backward stable algorithms, whic
h in general only guarantee correct digits in the singular values with larg
e enough magnitudes. It is of interest to compute the tiniest singular valu
es with several correct digits, because in some cases, such as finite eleme
nt problems and quantum mechanics, it is the smallest singular values that
have physical meaning, and should be determined accurately by the data. Man
y recent papers have identified special classes of matrices where high rela
tive accuracy is possible, since it is not possible in general. The perturb
ation theory and algorithms for these matrix classes have been quite differ
ent, motivating us to seek a common perturbation theory and common algorith
m. We provide these in this paper, and show that high relative accuracy is
possible in many new cases as well. The briefest: way to describe our resul
ts is that we can compute the SVD of G to high relative accuracy provided w
e can accurately factor G = XDYT where D is diagonal and X and Y are any we
ll-conditioned matrices; furthermore, the LDU factorization frequently does
the job. We provide many examples of matrix classes permitting such an LDU
decomposition. (C) 1999 Elsevier Science Inc. All rights reserved.