Difference between revisions of "The dqds algorithm for calculating singular values of bidiagonal matrices"
Jump to navigation
Jump to search
| [unchecked 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) |
|||
| (4 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"> | + | 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> | ||
| Line 6: | Line 6: | ||
=== 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 13: | 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 \delta 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.
