Блочная прогонка: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Frolov (обсуждение | вклад) |
Frolov (обсуждение | вклад) |
||
| Строка 89: | Строка 89: | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
Вычислительное ядро алгоритма можно представить из двух частей - прямого и обратного хода. В прямом ходе ядро составляют последовательности операций | Вычислительное ядро алгоритма можно представить из двух частей - прямого и обратного хода. В прямом ходе ядро составляют последовательности операций умножения обратной к одной матрице на другую, умножения и сложения/вычитания матриц и векторов. В обратном ходе в ядре остаются только последовательности умножения и сложения матриц и векторов. | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| Строка 140: | Строка 140: | ||
=== Описание ресурса параллелизма алгоритма === | === Описание ресурса параллелизма алгоритма === | ||
Для выполнения прогонки в трёхдиагональной СЛАУ из n уравнений с n неизвестными в параллельном варианте требуется последовательно выполнить следующие | Для выполнения прогонки в трёхдиагональной СЛАУ из n уравнений с n неизвестными в параллельном варианте требуется последовательно выполнить следующие макроярусы: | ||
* <math>n</math> ярусов | * <math>n</math> ярусов умножения матрицы, обратной к одной, на другую или на вектор (в каждом из ярусов, кроме одного, по 2 деления), | ||
* по <math>2n - 2</math> ярусов умножений и сложений/вычитаний (в n-1 ярусах - по 2 операции, в n-1 - по одной). | * по <math>2n - 2</math> ярусов умножений и сложений/вычитаний мариц и векторов (в n-1 ярусах - по 2 операции, в n-1 - по одной). | ||
При классификации по высоте ЯПФ, таким образом, прогонка относится к алгоритмам | При классификации по высоте ЯПФ, таким образом, прогонка относится к алгоритмам с макросложностью <math>O(n)</math>. При классификации по ширине ЯПФ его макросложность будет <math>2</math>. | ||
=== Входные и выходные данные алгоритма === | === Входные и выходные данные алгоритма === | ||
'''Входные данные''': трёхдиагональная матрица <math>A</math> ( | '''Входные данные''': блочно-трёхдиагональная матрица <math>A</math> (блоки <math>A_{ij}</math>), вектор <math>B</math> (блоки <math>B_{i}</math>). | ||
'''Выходные данные''': вектор <math> | '''Выходные данные''': вектор <math>X</math> (блоки <math>Х_{i}</math>). | ||
'''Объём выходных данных''': <math>n</math>. | '''Объём выходных данных''': <math>n</math> '''блоков'''. | ||
=== Свойства алгоритма === | === Свойства алгоритма === | ||
Соотношение последовательной и параллельной | Соотношение последовательной и параллельной макросложности, как хорошо видно, является ''константой'' (причём менее 2). | ||
При этом вычислительная мощность алгоритма, как отношение числа | При этом вычислительная мощность алгоритма, как отношение числа макроопераций к суммарному объему входных и выходных макроданных – тоже ''константа''. | ||
Алгоритм полностью детерминирован. | Алгоритм полностью детерминирован. | ||
Обычно прогонка используется для решения СЛАУ с диагональным преобладанием. Тогда гарантируется устойчивость алгоритма. | Обычно прогонка используется для решения СЛАУ с диагональным преобладанием. Тогда гарантируется устойчивость алгоритма. | ||
В случае, когда требуется решение нескольких СЛАУ с одной и той же матрицей, левую ветвь вычислений (см. рисунок с графом алгоритма) можно не повторять. Это связано с тем, что <math>LU</math>-разложение матрицы системы не нужно перевычислять. | В случае, когда требуется решение нескольких СЛАУ с одной и той же матрицей, левую ветвь вычислений (см. рисунок с графом алгоритма) можно не повторять. Это связано с тем, что блочное <math>LU</math>-разложение матрицы системы не нужно перевычислять. | ||
== Программная реализация алгоритма == | == Программная реализация алгоритма == | ||
Версия от 11:46, 10 августа 2015
| Прогонка для трёхдиагональной матрицы, точечный вариант | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ 8n-7 }[/math] |
| Объём входных данных | [math]\displaystyle{ 4n-2 }[/math] |
| Объём выходных данных | [math]\displaystyle{ n }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ 3n-2 }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ 2 }[/math] |
Основные авторы описания: А.В.Фролов
Свойства и структура алгоритма
Общее описание алгоритма
Блочная прогонка - один из вариантов метода исключения неизвестных в приложении к решению блочно-трёхдиагональной СЛАУ[1][2] вида [math]\displaystyle{ Ax = b }[/math], где
- [math]\displaystyle{ A = \begin{bmatrix} A_{11} & A_{12} & 0 & \cdots & \cdots & 0 \\ A_{21} & A_{22} & A_{23}& \cdots & \cdots & 0 \\ 0 & A_{32} & A_{33} & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & A_{n-1 n-2} & A_{n-1 n-1} & A_{n-1 n} \\ 0 & \cdots & \cdots & 0 & A_{n n-1} & A_{n n} \\ \end{bmatrix}, x = \begin{bmatrix} X_{1} \\ X_{2} \\ \vdots \\ X_{n} \\ \end{bmatrix}, b = \begin{bmatrix} B_{1} \\ B_{2} \\ \vdots \\ B_{n} \\ \end{bmatrix} }[/math]
Часто, однако, при изложении сути метода блочной прогонки[3] блоки правой части и матрицы системы обозначают и нумеруют по-другому, например СЛАУ может иметь вид ([math]\displaystyle{ N=n+1 }[/math])
- [math]\displaystyle{ A = \begin{bmatrix} C_{0} & -B_{0} & 0 & \cdots & \cdots & 0 \\ -A_{1} & C_{1} & -B_{1} & \cdots & \cdots & 0 \\ 0 & -A_{2} & C_{2} & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & -A_{N-1} & C_{N-1} & -B_{N-1} \\ 0 & \cdots & \cdots & 0 & -A_{N} & C_{N} \\ \end{bmatrix}\begin{bmatrix} Y_{0} \\ Y_{1} \\ \vdots \\ Y_{N} \\ \end{bmatrix} = \begin{bmatrix} F_{0} \\ F_{1} \\ \vdots \\ F_{N} \\ \end{bmatrix} }[/math]
или, если записывать отдельно по блочным уравнениям, то
- [math]\displaystyle{ C_{0} Y_{0} - B_{0} Y_{1} = F_{0},\\ -A_{i} Y_{i-1} + C_{i} Y_{i} - B_{i} Y_{i+1} = F_{i}, 1 \le i \le N-1, \\ -A_{N} Y_{N-1} + C_{N} Y_{N} = F_{N} }[/math]
Суть метода - в исключении из уравнений неизвестных, сначала - сверху вниз - под диагональю, а потом - снизу вверх - над диагональю.
Математическое описание алгоритма
В приведённых обозначениях в прогонке сначала выполняют её прямой ход - вычисляют матричные коэффициенты
- [math]\displaystyle{ \boldsymbol{\alpha}_{1} = C_{0}^{-1} B_{0},\\ \boldsymbol{\beta}_{1} = C_{0}^{-1} F_{0}, \\ \boldsymbol{\alpha}_{i+1} = (C_{i}-A_{i}\boldsymbol{\alpha}_{i})^{-1} B_{i}, \quad i = 1, 2, \cdots , N-1, \\ \boldsymbol{\beta}_{i+1} = (C_{i}-A_{i}\boldsymbol{\alpha}_{i})^{-1}(F_{i}+A_{i}\boldsymbol{\beta}_{i}), \quad i = 1, 2, \cdots , N. }[/math]
после чего вычисляют решение с помощью обратного хода
- [math]\displaystyle{ Y_{N} = \boldsymbol{\beta}_{N+1}, \\ Y_{i} = \boldsymbol{\alpha}_{i+1} Y_{i+1} + \boldsymbol{\beta}_{i+1}, \quad i = N-1, N-2, \cdots , 1, 0. }[/math]
Данные формулы эквиваленты вычислению одного из блочных [math]\displaystyle{ LU }[/math]-разложений матрицы системы с последующим решением блочно-двухдиагональных систем методом обратной подстановки.
Вычислительное ядро алгоритма
Вычислительное ядро алгоритма можно представить из двух частей - прямого и обратного хода. В прямом ходе ядро составляют последовательности операций умножения обратной к одной матрице на другую, умножения и сложения/вычитания матриц и векторов. В обратном ходе в ядре остаются только последовательности умножения и сложения матриц и векторов.
Макроструктура алгоритма
Кроме представления макроструктуры алгоритма как совокупности прямого и обратного хода, прямой ход также может быть разложен на две макроединицы - разложения матрицы и прямого хода решения двухдиагональной СЛАУ, которые выполняются "одновременно", т.е., параллельно друг другу. При этом решение двухдиагональной СЛАУ использует результаты разложения.
Схема реализации последовательного алгоритма
Последовательность исполнения метода следующая:
1. Инициализируется прямой ход прогонки:
- [math]\displaystyle{ \boldsymbol{\alpha}_{1} = C_{0}^{-1} B_{0},\\ \boldsymbol{\beta}_{1} = C_{0}^{-1} F_{0}, \\ }[/math]
2. Последовательно для всех i от 1 до N-1 выполняются формулы прямого хода:
- [math]\displaystyle{ \boldsymbol{\alpha}_{i+1} = (C_{i}-A_{i}\boldsymbol{\alpha}_{i})^{-1} B_{i}, \\ \boldsymbol{\beta}_{i+1} = (C_{i}-A_{i}\boldsymbol{\alpha}_{i})^{-1}(F_{i}+A_{i}\boldsymbol{\beta}_{i}). }[/math]
3. Инициализируется обратный ход прогонки:
- [math]\displaystyle{ Y_{N} = (C_{N}-A_{N}\boldsymbol{\alpha}_{N})^{-1}(F_{N}+A_{N}\boldsymbol{\beta}_{N}) }[/math]
4. Последовательно для всех i с убыванием от N-1 до 0 выполняются формулы обратного хода:
- [math]\displaystyle{ Y_{i} = \boldsymbol{\alpha}_{i+1} Y_{i+1} + \boldsymbol{\beta}_{i+1}. }[/math]
Последовательная сложность алгоритма
Для выполнения прогонки в трёхдиагональной СЛАУ из n уравнений с n неизвестными в последовательном (наиболее быстром) варианте требуется:
- [math]\displaystyle{ 2n-1 }[/math] делений,
- [math]\displaystyle{ 3n-3 }[/math] сложений/вычитаний,
- [math]\displaystyle{ 3n-3 }[/math] умножений.
При классификации по последовательной сложности, таким образом, прогонка относится к алгоритмам с линейной сложностью.
Информационный граф
Информационный макрограф прогонки изображён на рис.1. Как видно, в терминах макроопераций он почти последователен: при выполнении прямого хода две ветви (левая - блочное разложение матрицы, центральная - решение первой из блочно-двухдиагональных систем) могут выполняться параллельно друг другу. Правая ветвь соответствует обратному ходу. По рисунку видно, что не только математическая суть обработки элементов векторов, но даже структура макрографа алгоритма и направление потоков данных в нём вполне соответствуют названию "обратный ход".
Описание ресурса параллелизма алгоритма
Для выполнения прогонки в трёхдиагональной СЛАУ из n уравнений с n неизвестными в параллельном варианте требуется последовательно выполнить следующие макроярусы:
- [math]\displaystyle{ n }[/math] ярусов умножения матрицы, обратной к одной, на другую или на вектор (в каждом из ярусов, кроме одного, по 2 деления),
- по [math]\displaystyle{ 2n - 2 }[/math] ярусов умножений и сложений/вычитаний мариц и векторов (в n-1 ярусах - по 2 операции, в n-1 - по одной).
При классификации по высоте ЯПФ, таким образом, прогонка относится к алгоритмам с макросложностью [math]\displaystyle{ O(n) }[/math]. При классификации по ширине ЯПФ его макросложность будет [math]\displaystyle{ 2 }[/math].
Входные и выходные данные алгоритма
Входные данные: блочно-трёхдиагональная матрица [math]\displaystyle{ A }[/math] (блоки [math]\displaystyle{ A_{ij} }[/math]), вектор [math]\displaystyle{ B }[/math] (блоки [math]\displaystyle{ B_{i} }[/math]).
Выходные данные: вектор [math]\displaystyle{ X }[/math] (блоки [math]\displaystyle{ Х_{i} }[/math]).
Объём выходных данных: [math]\displaystyle{ n }[/math] блоков.
Свойства алгоритма
Соотношение последовательной и параллельной макросложности, как хорошо видно, является константой (причём менее 2).
При этом вычислительная мощность алгоритма, как отношение числа макроопераций к суммарному объему входных и выходных макроданных – тоже константа.
Алгоритм полностью детерминирован.
Обычно прогонка используется для решения СЛАУ с диагональным преобладанием. Тогда гарантируется устойчивость алгоритма. В случае, когда требуется решение нескольких СЛАУ с одной и той же матрицей, левую ветвь вычислений (см. рисунок с графом алгоритма) можно не повторять. Это связано с тем, что блочное [math]\displaystyle{ LU }[/math]-разложение матрицы системы не нужно перевычислять.
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
В зависимости от нужд вычислений, возможны как разные способы хранения матрицы СЛАУ (в виде одного массива с 3 строками или в виде 3 разных массивов), так и разные способы хранения вычисляемых коэффициентов (на месте использованных уже элементов матрицы либо отдельно).