Computing the singular value decomposition with high relative accuracy

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.