Итерация алгоритма dqds: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
(Новая страница: «{{algorithm | name = Итерация алгоитма dqds | serial_complexity = <math>5n-4</math> | pf_height = <math>4n-3</math> | pf_w…») |
|||
| Строка 1: | Строка 1: | ||
| + | |||
{{algorithm | {{algorithm | ||
| − | | name = | + | | name = Алгоритм dqds нахождения<br /> сингулярных чисел двухдиагональной матрицы |
| serial_complexity = <math>5n-4</math> | | serial_complexity = <math>5n-4</math> | ||
| pf_height = <math>4n-3</math> | | pf_height = <math>4n-3</math> | ||
| Строка 7: | Строка 8: | ||
| output_data = <math>2n</math> | | output_data = <math>2n</math> | ||
}} | }} | ||
| + | |||
Основные авторы описания: [[Участник:Chernyavskiy|А.Ю.Чернявский]] | Основные авторы описания: [[Участник:Chernyavskiy|А.Ю.Чернявский]] | ||
| Строка 13: | Строка 15: | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| − | '''Итерация | + | '''Итерация алгоритма dqds''' является одним шагом [[Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы|итерационного алгоритма для нахождения сингулярных чисел |
| + | |||
| + | двухдиагональной матрицы]]. | ||
| + | |||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
| Строка 20: | Строка 25: | ||
:<math> | :<math> | ||
| − | \widehat{q}_j = q_j + e_j - \widehat{e}_{j-1} - \delta \quad j \in [1,n-1]\\ | + | \widehat{q}_j = q_j + e_j - \widehat{e}_{j-1} - \delta, \quad j \in [1,n-1]\\ |
| − | \widehat{e}_j = e_j \cdot q_{j+1} / \widehat{q}_j \quad j \in [1,n-1]\\ | + | \widehat{e}_j = e_j \cdot q_{j+1} / \widehat{q}_j, \quad j \in [1,n-1]\\ |
\widehat{q}_n = q_n - \widehat{e}_{n-1} - \delta. | \widehat{q}_n = q_n - \widehat{e}_{n-1} - \delta. | ||
</math> | </math> | ||
| − | Здесь <math>q_j, \; j \in [1,n]</math> и <math>e_j, \; j \in [1,n-1]</math> - квадраты элемнтов главной и верхней побочной диагональ соответственно. Крышка означает выходные переменные, а <math>\delta</math> - сдвиг (параметр алгоритма). | + | Здесь <math>q_j, \; j \in [1,n]</math> и <math>e_j, \; j \in [1,n-1]</math> - квадраты элемнтов главной и верхней побочной диагональ соответственно. Крышка означает выходные переменные, а |
| + | |||
| + | <math>\delta</math> - сдвиг (параметр алгоритма). | ||
Такая математическая запись наиболее компактна и соответсвует так называемой qds-итерации. | Такая математическая запись наиболее компактна и соответсвует так называемой qds-итерации. | ||
| − | Представим также математическую запись, приближенную к dqds-итерации (с математической точки зрения qds и dqds-итерации эквивалентны) с введенными вспомогательными переменными <math>t_j</math> и <math>d_j:</math> | + | Представим также математическую запись, приближенную к dqds-итерации (с математической точки зрения qds и dqds-итерации эквивалентны) с введенными вспомогательными переменными |
| + | |||
| + | <math>t_j</math> и <math>d_j:</math> | ||
:<math> | :<math> | ||
| Строка 40: | Строка 49: | ||
Отметим, что при <math>\delta=0</math> две итерации dqds эквиваленты одной QR-итерации. | Отметим, что при <math>\delta=0</math> две итерации dqds эквиваленты одной QR-итерации. | ||
| + | |||
| + | === Вычислительное ядро алгоритма === | ||
| + | |||
| + | Вычислительным ядром алгоритма является производимое n-1 раз вычисление, содержащие по одной операции сложения, вычитания и деления, а также две операции умножения. | ||
| + | |||
| + | === Макроструктура алгоритма === | ||
| + | |||
| + | Алгоритм состоит из отдельного вычисления первого элемента главной диагонали и последующим (n-1)-кратным выполнением повторяющейся последовательности из 5 операций (+,/,*,*,-). | ||
| + | |||
| + | === Схема реализации последовательного алгоритма === | ||
| + | |||
| + | Отметим, что выходные данные сразу могут быть записаны во взодные (это учтено в схеме), также для хранения вспомогательных <math>t_j</math> и <math>d_j</math> достаточно двух | ||
| + | |||
| + | перезаписываемых переменных. | ||
| + | |||
| + | # Вычисляется начальное значение <math>d = q_1-\delta</math> | ||
| + | |||
| + | # Производится цикл по i от 1 до n-1, состоящий из: | ||
| + | |||
| + | ## | ||
| + | ## | ||
| + | ## | ||
| + | ## | ||
| + | ## | ||
| + | |||
| + | # Вычисляется <math>q_n = d.</math> | ||
Версия 14:07, 23 августа 2015
| Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]5n-4[/math] |
| Объём входных данных | [math]2n[/math] |
| Объём выходных данных | [math]2n[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]4n-3[/math] |
| Ширина ярусно-параллельной формы | [math]2[/math] |
Основные авторы описания: А.Ю.Чернявский
Содержание
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Итерация алгоритма dqds является одним шагом итерационного алгоритма для нахождения сингулярных чисел двухдиагональной матрицы.
1.2 Математическое описание алгоритма
Формулы алгоритма следующие:
- [math] \widehat{q}_j = q_j + e_j - \widehat{e}_{j-1} - \delta, \quad j \in [1,n-1]\\ \widehat{e}_j = e_j \cdot q_{j+1} / \widehat{q}_j, \quad j \in [1,n-1]\\ \widehat{q}_n = q_n - \widehat{e}_{n-1} - \delta. [/math]
Здесь [math]q_j, \; j \in [1,n][/math] и [math]e_j, \; j \in [1,n-1][/math] - квадраты элемнтов главной и верхней побочной диагональ соответственно. Крышка означает выходные переменные, а
[math]\delta[/math] - сдвиг (параметр алгоритма). Такая математическая запись наиболее компактна и соответсвует так называемой qds-итерации.
Представим также математическую запись, приближенную к dqds-итерации (с математической точки зрения qds и dqds-итерации эквивалентны) с введенными вспомогательными переменными
[math]t_j[/math] и [math]d_j:[/math]
- [math] d_1 = q_1 - \delta, \; q_n = d_n \\ для \; j\in [1,n-1]: \\ \widehat{q}_j = d_j + e_j\\ t_j = q_{j+1}/\widehat{q}_j\\ \widehat{e}_j=e_j \cdot t_j \\ d_{j+1} = d \cdot t - \delta \\ [/math]
Отметим, что при [math]\delta=0[/math] две итерации dqds эквиваленты одной QR-итерации.
1.3 Вычислительное ядро алгоритма
Вычислительным ядром алгоритма является производимое n-1 раз вычисление, содержащие по одной операции сложения, вычитания и деления, а также две операции умножения.
1.4 Макроструктура алгоритма
Алгоритм состоит из отдельного вычисления первого элемента главной диагонали и последующим (n-1)-кратным выполнением повторяющейся последовательности из 5 операций (+,/,*,*,-).
1.5 Схема реализации последовательного алгоритма
Отметим, что выходные данные сразу могут быть записаны во взодные (это учтено в схеме), также для хранения вспомогательных [math]t_j[/math] и [math]d_j[/math] достаточно двух
перезаписываемых переменных.
- Вычисляется начальное значение [math]d = q_1-\delta[/math]
- Производится цикл по i от 1 до n-1, состоящий из:
- Вычисляется [math]q_n = d.[/math]
