Участник:Sagak/Алгоритм Ланцоша в арифметике с плавающей точкой
Содержание
1 Алгоритм Ланцоша
Алгоритм Ланцоша – итерационный метод , созданный Корнелиусом Ланцошем, для нахождения собственных значений и собственных веторов симметричной матрицы. Суть алгоритма в том, что он сводит частичную проблему собственных значений симметричной вещественной матрицы к полной проблеме собственных значений для симметричной трехдиагональной матрицы меньшей размерности. Алгоритм применяется к матрицам большой размерности, к которым не применимы никакие прямые методы. Есть три вида алгоритма: Алгоритм Ланцоша с точной арифметикой, Алгоритм Ланцоша в арифметике с плавающей точкой и Алгоритм Ланцоша с выборочной ортогонализацией. Алгоритм Ланцоша в арифметике с плавающей точкой учитывает округления, возникающие при вычислениях.
Симметричность матрицы позволяет хранить и вычислять только чуть больше половины её элементов, что почти вдвое экономит как необходимые для вычислений объёмы памяти, так и количество операций.Также алгоритм позволяет использовать так называемый режим накопления, обусловленный тем, что значительную часть вычислений составляют вычисления скалярных произведений.
2 Математическое описание алгоритма
Исходные данные: положительно определённая симметрическая матрица [math]A[/math], вектор [math]b[/math],количество итераций [math]k[/math].
Вычисляемые данные: трехдиагональная матрица [math]T_k[/math](элементы [math]t_{ij}[/math]) размерности [math]k[/math].
Формула метода:
- [math] \begin{align} q_1&=b/||b||,\beta_0=0,q_o=0. \\ z&=Aq_j, \\ \alpha_j&=q_j^Tz, \\ z& =z-\sum\nolimits_{i=1}^{j-1}(z^Tq_i)q_i, \\ \end{align} [/math]
[math] \begin{align} \\ z&=z-\sum\nolimits_{i=1}^{j-1}(z^Tq_i)q_i, \\ z&=z-\alpha_jq_j-\beta_{j-1}q_{j-1}, \\ \beta&=||z||,\\ q_{j+1}&=z/\beta_j, \quad j \in [1, k]. \end{align} [/math]
Полная переортогонализация соответствует повторному проведению операции [math]z =z-\sum\nolimits_{i=1}^{j-1}(z^Tq_i)q_i,[/math], для того чтобы почти гарантировать, что z будет ортогонален векторам [math]q_1...q_{j-1}[/math].
3 Вычислительное ядро алгоритма
Вычислительное ядро последовательной версии алгоритма Ланцоша можно составить из [math]k[/math] умножений
[math]Aq_j[/math]
векторов на исходную матрицу
и [math]k^2+2k[/math] скалярных произведений вида
[math]z^Tq_i, q_j^Tz[/math].
4 Схема реализации последовательного алгоритма
Последовательность исполнения метода следующая:
[math] \begin{align} \\ 1 .& q_1=b/||b||,\\ 2 .& \beta_0=0,\\ 3 .&q_o=0. \\ \end{align} [/math]
Далее для всех [math]j[/math] от [math]1[/math] до [math]k[/math] по нарастанию выполняются
[math] \begin{align} 4&.z=Aq_j, \\ 5&.\alpha_j=q_j^Tz, \\ 6&.z =z-\sum\nolimits_{i=1}^{j-1}(z^Tq_i)q_i, \\ 7&.z=z-\sum\nolimits_{i=1}^{j-1}(z^Tq_i)q_i, \\ 8&.z=z-\alpha_jq_j-\beta_{j-1}q_{j-1}, \\ 9&.\beta=||z||,\\ 1&0.q_{j+1}=z/\beta_j.\\ \end{align} [/math]
При этом если [math]\beta=0[/math], то алгоритм завершается.
5 Последовательная сложность алгоритма
Для выполнения алгоритма Ланцоша в последовательном варианте требуется:
[math]n^2[/math] вычислений квадратного корня,
[math]n^2[/math] сложений (вычитаний),
[math]n^2[/math] умножений
Умножения и сложения (вычитания) составляют основную часть алгоритма.
6 Информационный граф
Опишем граф алгоритма в виде рисунка.
- Вершина черного цвета соответствует операции [math]Aq_j,[/math].
- Вершина красного цвета соответствует операции скалярного произведения [math]q_j^Tz[/math].
- Вершина сиреневого цвета соответствует операции [math]z-\sum\nolimits_{i=1}^{j-1}(z^Tq_i)q_i[/math].
- Вершина желтого цвета соответствует операции [math]z-\alpha_jq_j-\beta_{j-1}q_{j-1}[/math].
- Вершина синего цвета соответствует операции [math]||z||[/math].
- Вершина зеленого цвета соответствует операции [math]z/\beta_j[/math].
Здесь показаны первые три итерации алгоритма,при больших итерациях граф строится аналогичным образом.
Отметим, что можно подробнее расписать первые четыре операции, в первая из них является стандартной операцией умножения вектора на матрицу,вторая-скалярное произведение, третье-сумма скалярных произведений. Именно эти операции содержат ресурс параллелизма.
