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

From Algowiki
Jump to navigation Jump to search
[quality revision][quality revision]
(Created page with "=== General description of the algorithm === Алгоритм '''dqds''' (''differential quotient-difference algorithm with shifts'')<ref name="vla">Деммель Д. Выч...")
 
 
(8 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
=== General description of the algorithm ===
 
=== General description of the algorithm ===
−
Алгоритм '''dqds''' (''differential quotient-difference algorithm with shifts'')<ref name="vla">Деммель Д. Вычислительная линейная алгебра. – М : Мир, 2001.</ref><ref name="hola">Hogben L. (ed.). Handbook of linear algebra. – CRC Press, 2006.</ref> позволяет с высокой точностью вычислять сингулярные числа двухдиагональных матриц.  
+
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
−
Вычислительным ядром алгоритма является [[Итерация алгоритма dqds|dqds-итерация]], вне итераций происходит подбор сдвига <math>\delta</math>, отслеживание сходимости, а также применение различных оптимизационных "хитростей". Отметим, что внеитерационная часть алгоритма не существенна с точки зрения структуры вычислений, т.к. основыне вычислительные затраты ложаться на [[Итерация алгоритма dqds|dqds-итерацию]]. Подробности и варианты внеитерационной части, а также анализ сходимости можно найти в соответствующей литературе
 
 
<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 ===
−
В [http://netlib.org/lapack/ LAPACK] реализовано функцией XLASQ1.
+
In [http://netlib.org/lapack/ LAPACK], the algorithm is realized by the function XLASQ1.
  
 
== References ==
 
== References ==
Line 15: 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"