Difference between revisions of "The dqds algorithm for calculating singular values of bidiagonal matrices"

From Algowiki
Jump to navigation Jump to search
 
(One intermediate revision by the same user not shown)
Line 13: Line 13:
  
  
−
[[Category:Started articles]]
+
[[Category:Finished articles]]
  
 
[[Ru:Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы]]
 
[[Ru:Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы]]

Latest revision as of 15:18, 14 March 2018

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.
Retrieved from "https://algowiki-project.org/algowiki/en/index.php?title=The_dqds_algorithm_for_calculating_singular_values_of_bidiagonal_matrices&oldid=1649"