Итерация алгоритма 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 является одним шагом итерационного алгоритма для нахождения сингулярных чисел двухдиагональной матрицы. Основные вычисления алгоритма dqds приходятся именно на внутреннюю итерацию. Внешняя часть алгоритма отвечает за контроль сходимости и выбор сдвигов [math]\displaystyle{ \delta, }[/math] что основано на довольно сложной теории и имеет различные реализации, но в то же время не влияет на вычислительные аспекты. В связи с этим dqds-итерация и dqds-алгоритм рассматриваются отдельно.

Для понимания dqds-итерации полезно рассмотреть кратко её вывод, относительно точно отражающий и историю возникновения алгоритма (подробности можно найти в .

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

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

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

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

Информационный граф

Рисунок 1. Граф алгоритма для n=4 без отображения входных и выходных данных.

Ресурс параллелизма алгоритма

Как видно из информационного графа алгоритма, на каждом шаге основного цикла возможно лишь параллельное выполнение операции умножения (2.2) и умножения+сложения (2.4). Это позволяет сократить число ярусов на одной итерации цикла c 5 до 4, а общее число ярусов алгоритма с 5n-4 до 4n-3. Ярусы с операциями умножения состоят из двух операций, остальные же из одной.

Входные и выходные данные алгоритма

Входные данные: Квадраты элементов основной и верхней побочной диагонали двухдиагональной матрицы (вектора [math]\displaystyle{ q }[/math] длины n и [math]\displaystyle{ e }[/math] длины n-1), а также параметр сдвига [math]\displaystyle{ \delta }[/math].

Объём входных данных: [math]\displaystyle{ 2n }[/math].

Выходные данные: Квадраты элементов основной и верхней побочной диагонали выходной двухдиагональной матрицы.

Объём выходных данных: [math]\displaystyle{ 2n-1 }[/math].

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

Соотношение последовательной и параллельной сложности при наличии возможности параллельного выполнения операций умножения составляет [math]\displaystyle{ \frac{5n-4}{4n-3} }[/math], т.е. алгоритм плохо распараллеливается.

Вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных - константа.

Описываемый алгоритм является полностью детерминированным.

Программная реализация алгоритмов

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

Алгоритм на языке Matlab может быть записать так:

d = q(1)-delta;
for j = 1:n-1
    q(j)=d+e(j);
    t=q(j+1)/q(j);
    e(j) = e(j)*t;
    d = d*t-delta;
end
q(n) = d;

Локальность данных и вычислений

Легко видеть, что локальность данных высока. Её легко повысить, размещая рядом соответствующие элементы массивов e и q, однако, это не оказывает существенного влияния на производительность в силу константного количества операций относительно объема обрабатываемых данных.

Возможные способы и особенности параллельной реализации алгоритма

Итерация dqds практически полностью последовательна. Единственная возможность - одновременное выполнение операции умножения (2.3) и опрерации (2.4) умножения и сложения, что дает небольшой выигрыш в производительности.

Масштабируемость алгоритма и его реализации

Алгоритм не является масштабируемым, максимального эффекта ускорения можно добиться на двух независимых процессорах.

Выводы для классов архитектур

Эффективное выполнение алгоритма возможно только на вычислительных устройствах с одним или двумя ядрами.

Существующие реализации алгоритма

Перечень реализаций приведен на странице алгоритма dqds.