The Orthogonal qd-Algorithm
U. von Matt · SIAM Journal on Scientific Computing · 1997
The orthogonal qd-algorithm is presented to compute the singular value decomposition of a bidiagonal matrix. This algorithm represents a modification of Rutishauser's qd-algorithm, and it is capable of determining all the singular values and their corresponding singular vectors to high relative accuracy. A generalization of the Givens transformation, which has applications besides the orthogonal qd-algorithm, is also introduced. The shift strategy of the orthogonal qd-algorithm is based on Laguerre's method, which is used to compute a lower bound on the smallest singular value of the bidiagonal matrix. Special attention is devoted to the numerically stable evaluation of this shift.