Итерация алгоритма dqds

Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ 5n-4 }[/math]
Объём входных данных	[math]\displaystyle{ 2n }[/math]
Объём выходных данных	[math]\displaystyle{ 2n }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ 4n-3 }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ 2 }[/math]

Основные авторы описания: А.Ю.Чернявский

Свойства и структура алгоритмов

Общее описание алгоритма

Итерация алгоритма dqds является одним шагом итерационного алгоритма для нахождения сингулярных чисел двухдиагональной матрицы.

Математическое описание алгоритма

Формулы алгоритма следующие:

[math]\displaystyle{ \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]\displaystyle{ q_j, \; j \in [1,n] }[/math] и [math]\displaystyle{ e_j, \; j \in [1,n-1] }[/math] - квадраты элемнтов главной и верхней побочной диагональ соответственно. Крышка означает выходные переменные, а

[math]\displaystyle{ \delta }[/math] - сдвиг (параметр алгоритма). Такая математическая запись наиболее компактна и соответсвует так называемой qds-итерации.

Представим также математическую запись, приближенную к dqds-итерации (с математической точки зрения qds и dqds-итерации эквивалентны) с введенными вспомогательными переменными

[math]\displaystyle{ t_j }[/math] и [math]\displaystyle{ d_j: }[/math]

[math]\displaystyle{ 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]\displaystyle{ \delta=0 }[/math] две итерации dqds эквиваленты одной QR-итерации.

Вычислительное ядро алгоритма

Вычислительным ядром алгоритма является производимое n-1 раз вычисление, содержащие по одной операции сложения, вычитания и деления, а также две операции умножения.

Макроструктура алгоритма

Алгоритм состоит из отдельного вычисления первого элемента главной диагонали и последующим (n-1)-кратным выполнением повторяющейся последовательности из 5 операций (+,/,*,*,-).

Схема реализации последовательного алгоритма

Отметим, что выходные данные сразу могут быть записаны на место входных (это учтено в схеме), также для хранения вспомогательных переменных [math]\displaystyle{ t_j }[/math] и [math]\displaystyle{ d_j }[/math] достаточно двух перезаписываемых переменных.

1. Вычисляется начальное значение вспомогательной переменной [math]\displaystyle{ d = q_1-\delta. }[/math]

2. Производится цикл по j от 1 до n-1, состоящий из:

2.1 Вычисляется значение [math]\displaystyle{ q_j = d + e_j; }[/math]

2.2 Вычисляется значение вспомогательной переменной [math]\displaystyle{ t = q_{j+1}/q_j; }[/math]

2.3 Вычисляется значение [math]\displaystyle{ e_j = e_j \cdot t; }[/math]

2.4 Вычисляется значение вспомогательной переменной [math]\displaystyle{ d = d \cdot t - \delta. }[/math]

3. Вычисляется [math]\displaystyle{ q_n = d. }[/math]

Последовательная сложность алгоритма

Для выполнения одной итерации dqds необходимо выполнить:

• [math]\displaystyle{ n-1 }[/math] делений,
• [math]\displaystyle{ 2n-2 }[/math] умножений,
• [math]\displaystyle{ 2n-1 }[/math] сложений/вычитаний.

Таким образом одна dqds-итерация имеет с линейную сложность.