Участник:Малков Кирилл/Алгоритм бидиагонализации матрицы методом отражений: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 5: Строка 5:
 
где <math>P</math> и <math>Q</math> - произведения конечного числа матриц отражения(или вращения).
 
где <math>P</math> и <math>Q</math> - произведения конечного числа матриц отражения(или вращения).
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
Пусть дана матрица A размера <math>n \times n</math>. Вычисляется двухдиагональная матрица D размера <math>n \times n</math>, такая что <math>A = P \times D \times Q</math> для некоторых матриц P и Q, являющихся произведением некоторого числа матриц отражения.Сначала мы умножаем A слева на матрицу отражения, аннулирующую все поддиагональные элементы вервого столбца. Затем умножаем результат справа на матрицу отражения, аннулирующую элементы первой строки в позициях с 3-й по n-ю. Далее умножением слева аннулируем все поддиагональные элементы второго столбца, затем умножением справа аннулируем получаем нули во второй строке в позициях с 4-й по n-ю и т.д. После каждого умножения на матрицу отражения все ранее полученные нули остаются.
+
Пусть дана матрица A размера <math>n \times n</math>. Вычисляется двухдиагональная матрица D размера <math>n \times n</math>, такая что <math>A = P D Q</math> для некоторых матриц P и Q, являющихся произведением некоторого числа матриц отражения.Сначала мы умножаем A слева на матрицу отражения, аннулирующую все поддиагональные элементы первого столбца. Затем умножаем результат справа на матрицу отражения, аннулирующую элементы первой строки в позициях с 3-й по n-ю. Далее умножением слева аннулируем все поддиагональные элементы второго столбца, затем умножением справа аннулируем получаем нули во второй строке в позициях с 4-й по n-ю и т.д. После каждого умножения на матрицу отражения все ранее полученные нули остаются.
 
Формулы метода:
 
Формулы метода:
 
Пусть <math>A = [a_1, a_2, ..., a_n]</math>
 
Пусть <math>A = [a_1, a_2, ..., a_n]</math>
Строка 37: Строка 37:
 
Получим, что параллельная сложность алгоритма есть <math>O(n^2)<\math>
 
Получим, что параллельная сложность алгоритма есть <math>O(n^2)<\math>
 
=== Входные и выходные данные алгоритма ===  
 
=== Входные и выходные данные алгоритма ===  
На вход подается матрица A и ее размер n. Выходные данные -- матрицы P, Q, D, такие что <math>A = P * D * Q <\math>
+
На вход подается матрица A и ее размер n. Выходные данные -- матрицы P, Q, D, такие что <math>A = P D Q <\math>
 
=== Свойства алгоритма ===
 
=== Свойства алгоритма ===
 
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов является линейным.
 
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов является линейным.
 
Вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных, линейна.
 
Вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных, линейна.
 +
== Программная реализация алгоритма ==
 +
=== Особенности реализации последовательного алгоритма ===
 +
=== Локальность данных и вычислений ===
 +
=== Возможные способы и особенности параллельной реализации алгоритма ===
 +
=== Масштабируемость алгоритма и его реализации ===
 +
=== Динамические характеристики и эффективность реализации алгоритма ===
 +
=== Выводы для классов архитектур ===
 +
=== Существующие реализации архитектур ===
  
 
== Литература ==  
 
== Литература ==  
 
Е. Е. Тыртышников, "Методы численного анализа".
 
Е. Е. Тыртышников, "Методы численного анализа".

Версия 02:57, 7 декабря 2021

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

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

Матрица [math]B = [b_{ij}][/math] называется (верхней) двухдиагональной, или бидиагональной, если [math]b_{ij} = 0[/math], [math]i \gt j[/math] или [math]i + 1 \lt j[/math]. Алгоритм бидиагонализации матрицы методом отражений приводит произвольную [math]n \times n[/math] матрицу A к бидиагональному виду [math]B = PAQ[/math], где [math]P[/math] и [math]Q[/math] - произведения конечного числа матриц отражения(или вращения).

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

Пусть дана матрица A размера [math]n \times n[/math]. Вычисляется двухдиагональная матрица D размера [math]n \times n[/math], такая что [math]A = P D Q[/math] для некоторых матриц P и Q, являющихся произведением некоторого числа матриц отражения.Сначала мы умножаем A слева на матрицу отражения, аннулирующую все поддиагональные элементы первого столбца. Затем умножаем результат справа на матрицу отражения, аннулирующую элементы первой строки в позициях с 3-й по n-ю. Далее умножением слева аннулируем все поддиагональные элементы второго столбца, затем умножением справа аннулируем получаем нули во второй строке в позициях с 4-й по n-ю и т.д. После каждого умножения на матрицу отражения все ранее полученные нули остаются. Формулы метода: Пусть [math]A = [a_1, a_2, ..., a_n][/math] [math]D_1 = A, P_1 = I, Q_1 = I.[/math] [math]Если i четное, то D_i = D_{i-1} * (I - 2 * u_{i-1} * u_{i-1}^*)[/math] [math]u_i = frac{[0, 0, ..., 0, d_{i+1} - ||d_{i+1}||_2, d_{i+2}, ..., d_n]}{||[0, 0, ..., 0, d_{i+1} - ||d_{i+1}||_2, d_{i+2}, ..., d_n]||_2}, Q_i = (I - 2 * u_{i} * u_{i}^*) * Q_{i-1}, P_i = P_{i-1}.[/math] [math]Если i нечетное, то D_i = (I - 2 * u_{i-1} * u_{i-1}^*) * D_{i-1},[/math] [math]u_i = frac{[0, 0, ..., 0, d_i - ||d_i||_2, d_{i+1}, ..., d_n]}{||[0, 0, ..., 0, d_i - ||d_i||_2, d_{i+1}, ..., d_n]||_2}, Q_i = Q_{i-1}, P_i = P_{i-1} * (I - 2 * u_{i} * u_{i}^*).[/math]

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

Вычислительное ядро алгоритма составляет нахождение на каждом этапе матрицы отражения(всего [math]2 * n - 2[/math].

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

Операции скалярного произведения, умножения матрицы на вектор

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

[math]D_1 = A, P_1 = I, Q_1 = I.[/math] [math]1) для четного i : D_i = D_{i-1} * (I - 2 * u_{i-1} * u_{i-1}^*), Q_i = (I - 2 * u_{i} * u_{i}^*) * Q_{i-1}, P_i = P_{i-1};[/math] [math] для нечетного i : D_i = (I - 2 * u_{i-1} * u_{i-1}^*) * D_{i-1}, Q_i = Q_{i-1}, P_i = P_{i-1} * (I - 2 * u_{i} * u_{i}^*).[/math] [math]2) для четного i : u_i = \frac{[0, 0, ..., 0, d_{i+1} - ||d_{i+1}||_2, d_{i+2}, ..., d_n]}{||[0, 0, ..., 0, d_{i+1} - ||d_{i+1}||_2, d_{i+2}, ..., d_n]||_2},[/math] [math] для нечетного i : u_i = \frac{[0, 0, ..., 0, d_i - ||d_i||_2, d_{i+1}, ..., d_n]}{||[0, 0, ..., 0, d_i - ||d_i||_2, d_{i+1}, ..., d_n]||_2}.[/math]

1.6 Последовательная сложность

Для двухдиагонализации матрицы порядка n методом отражений при последовательном варианте требуется: <math>1) 2 * n - 2 вычислений квадратного корня, 2) 4 * n - 4 делений, 3) (4 * n - 4)(1 + n + n^2) умножений, 4) (4 * n - 4)(1 + n + n^2) сложений. Сложность последовательного алгоритма есть <math>O(n^3)<\math>.

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

=== При параллельном вычислении двухдиагональной матрицы методом отражений требуется последовательно выполнить следующие ярусы: <math> -- k ярусов с вычислением 4 * (n/k) - 4 делений, -- k ярусов с вычислением (4 * (n/k) - 4)(1 + n + n^2) умножений, -- k ярусов с вычислением (4 * (n/k) - 4)(1 + n + n^2) сложений. Получим, что параллельная сложность алгоритма есть <math>O(n^2)<\math>

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

На вход подается матрица A и ее размер n. Выходные данные -- матрицы P, Q, D, такие что <math>A = P D Q <\math>

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

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

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

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

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

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

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

2.5 Динамические характеристики и эффективность реализации алгоритма

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

2.7 Существующие реализации архитектур

3 Литература

Е. Е. Тыртышников, "Методы численного анализа".