Computing the singular value decomposition with high relative accuracy (Q1964330)

Although classical methods can compute singular values of matrices with very small absolute errors, the estimates they give for very small singular values often contain no correct significant figures, even when these small singular values are well determined by the physical problem being modeled. Many recent papers have identified special classes of matrices for which the singular value decomposition may be computed with high relative accuracy, but the perturbation theory and algorithms for the different cases have been very different. This paper gives a common perturbation theory and a common strategy which makes possible the computation of the singular value decomposition with high relative accuracy not only for many classes of matrices previously dealt with but also for many new cases as well. The first step is to compute a ``rank revealing'' decomposition \(XDY^T\) of the given matrix, where \(D\) is diagonal and \(X\) and \(Y\) have at least as many rows as columns and are well-conditioned in a certain sense. Often the \(LDU\) decomposition is a suitable choice. Several algorithms for computing the singular value decomposition from \(XDY^T\) are compared and a complete analysis is given for the main recommended method. The paper includes a discussion of several open problems, and 80 references to the related literature.