The dqds algorithm for calculating singular values of bidiagonal matrices

From Algowiki
Jump to: navigation, search

1 General description of the algorithm

The dqds algorithm (differential quotient-difference algorithm with shifts)[1][2] calculates to high accuracy the singular values of bi-diagonal matrices. The dqds iteration is the computational kernel of this algorithm. Outside of the iterations, shifts [math]\delta[/math] are chosen, convergence is looked after, and various optimization tricks are applied. Note that the non-iterative part of the algorithm is not important with respect to the structure of calculations because the main computational costs fall on dqds-iteration. Details concerning the non-iterative part, its variants, and the analysis of convergence can be found in the related literature [3] [4] [5].

2 Existing implementations of the algorithm

In LAPACK, the algorithm is realized by the function XLASQ1.

3 References

  1. Demmel. D. Applied numerical linear algebra. 1997.
  2. Hogben L. (ed.). Handbook of linear algebra. – CRC Press, 2006.
  3. Fernando K. V., Parlett B. N. Accurate singular values and differential qd algorithms //Numerische Mathematik. – 1994. – Т. 67. – №. 2. – С. 191-229.
  4. Parlett B. N., Marques O. A. An implementation of the dqds algorithm (positive case) //Linear Algebra and its Applications. – 2000. – Т. 309. – №. 1. – С. 217-259.
  5. Aishima K. et al. On convergence of the DQDS algorithm for singular value computation //SIAM Journal on Matrix Analysis and Applications. – 2008. – Т. 30. – №. 2. – С. 522-537.