An O(n2) algorithm for the bidiagonal SVD

AbstractThe relatively robust representations (RRR) algorithm computes the eigendecomposition of a symmetric tridiagonal matrix T with an O(n2) complexity. This article discusses how this method can be extended to the bidiagonal SVD B=UΣVT. It turns out that using the RRR algorithm as a black box to compute BTB=VΣ2VT and BBT=UΣ2UT separately may give poor results for ∥BV−UΣ∥. The use of the standard Jordan–Wielandt representation can fail as well if clusters of tiny singular values are present. A solution is to work on BTB and to keep factorizations of BBT implicitly. We introduce a set of coupling transformations which allow us to replace the representation u=1σBv by a more stable representation u=Xv, where X is a diagonal matrix. Numerical results of our implementation are compared with the LAPACK routines DSTEGR, DBDSQR and DBDSDC