Treffer: The Orthogonal QD-Algorithm

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 to high relative precision. A generalization of the Givens transformation is also introduced, which has applications besides the orthogonal qd-algorithm. The shift strategy of the orthogonal qd-algorithm is based on Laguerre's method, which is used to compute a lower bound for the smallest singular value of the bidiagonal matrix. Special attention is devoted to the numerically stable evaluation of this shift. Key words. Generalized Givens transformation, implicit Cholesky decomposition, Laguerre's method, orthogonal qd-algorithm, singular value decomposition. AMS subject classifications. 65F20. This report is available by anonymous ftp from cs.umd.edu in the directory /pub/papers/TRs. y Institute for Advanced Computer Studies, University of Mar.