Difference between revisions of "The dqds algorithm for calculating singular values of bidiagonal matrices"
Jump to navigation
Jump to search
[quality revision] | [quality revision] |
m (ASA moved page The dqds algorithm for calculating the singular values of a bidiagonal matrix to The dqds algorithm for calculating singular values of bidiagonal matrices) |
|||
(7 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
=== General description of the algorithm === | === General description of the algorithm === | ||
− | + | The '''dqds''' algorithm (''differential quotient-difference algorithm with shifts'')<ref name="vla">Demmel. D. Applied numerical linear algebra. 1997.</ref><ref name="hola">Hogben L. (ed.). Handbook of linear algebra. – CRC Press, 2006.</ref> calculates to high accuracy the singular values of bi-diagonal matrices. The [[The_dqds_algorithm_iteration|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 [[The_dqds_algorithm_iteration|dqds-iteration]]. Details concerning the non-iterative part, its variants, and the analysis of convergence can be found in the related literature | |
− | |||
<ref>Fernando K. V., Parlett B. N. Accurate singular values and differential qd algorithms //Numerische Mathematik. – 1994. – Т. 67. – №. 2. – С. 191-229.</ref> | <ref>Fernando K. V., Parlett B. N. Accurate singular values and differential qd algorithms //Numerische Mathematik. – 1994. – Т. 67. – №. 2. – С. 191-229.</ref> | ||
<ref>Parlett B. N., Marques O. A. An implementation of the dqds algorithm (positive case) //Linear Algebra and its Applications. – 2000. – Т. 309. – №. 1. – С. 217-259.</ref> | <ref>Parlett B. N., Marques O. A. An implementation of the dqds algorithm (positive case) //Linear Algebra and its Applications. – 2000. – Т. 309. – №. 1. – С. 217-259.</ref> | ||
<ref>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.</ref>. | <ref>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.</ref>. | ||
− | |||
=== Existing implementations of the algorithm === | === Existing implementations of the algorithm === | ||
− | + | In [http://netlib.org/lapack/ LAPACK], the algorithm is realized by the function XLASQ1. | |
== References == | == References == | ||
Line 15: | Line 13: | ||
− | [[Category: | + | [[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
- ↑ Demmel. D. Applied numerical linear algebra. 1997.
- ↑ Hogben L. (ed.). Handbook of linear algebra. – CRC Press, 2006.
- ↑ Fernando K. V., Parlett B. N. Accurate singular values and differential qd algorithms //Numerische Mathematik. – 1994. – Т. 67. – №. 2. – С. 191-229.
- ↑ Parlett B. N., Marques O. A. An implementation of the dqds algorithm (positive case) //Linear Algebra and its Applications. – 2000. – Т. 309. – №. 1. – С. 217-259.
- ↑ 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.