Алговики - Вклад [ru]

Метод релаксации матрицы

2025-12-09T04:04:52Z

Овсиенко Олеся:

{{algorithm
| name = Метод релаксации матрицы
| serial_complexity = <math>O(it\_max \cdot N^2)</math>
| pf_height = <math>O(it\_max)</math>
| pf_width = <math>O(N^2)</math>
| input_data = <math>N^2</math> (матрица значений)
| output_data = <math>N^2</math> (матрица значений)
}}

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

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

Метод релаксации является одним из простейших итерационных методов решения уравнений в частных производных. В данной реализации он применяется для численного решения уравнения Лапласа на прямоугольной области с граничными условиями Дирихле. Алгоритм основан на дискретизации уравнения с использованием конечно-разностной схемы и последующем итеративном обновлении значений в узлах сетки до достижения заданной точности.

Метод широко используется в вычислительной физике для решения стационарных задач, таких как распределение потенциала, тепловое равновесие и др. Благодаря простоте реализации и естественному параллелизму (каждая точка сетки обновляется независимо на каждой итерации) алгоритм хорошо подходит для распараллеливания на многопроцессорных системах.

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

Исходная задача: решение уравнения Лапласа
<math>
\frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} = 0
</math>
в прямоугольной области <math>[0,1]\times[0,1]</math> с нулевыми граничными условиями.

Дискретизация на равномерной сетке <math>N \times N</math> с шагом <math>h = 1/(N-1)</math> приводит к системе линейных уравнений, которая решается методом релаксации:

Для каждого внутреннего узла <math>(i,j)</math> на итерации <math>k</math>:
<math>
u_{i,j}^{(k)} = \frac{u_{i-1,j}^{(k-1)} + u_{i+1,j}^{(k-1)} + u_{i,j-1}^{(k-1)} + u_{i,j+1}^{(k-1)}}{4}
</math>

Критерий остановки:
<math>
\max_{i,j} |u_{i,j}^{(k)} - u_{i,j}^{(k-1)}| < \varepsilon_{\text{max}}
</math>

Начальное приближение для внутренних точек:
<math>
u_{i,j}^{(0)} = 1 + i + j
</math>

Контрольная сумма для верификации:
<math>
S = \frac{1}{N^2} \sum_{i=0}^{N-1} \sum_{j=0}^{N-1} u_{i,j} \cdot (i+1) \cdot (j+1)
</math>

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

Вычислительное ядро алгоритма состоит из операций обновления значений во внутренних узлах сетки:
<math>
\text{new_val} = \frac{\text{left} + \text{right} + \text{top} + \text{bottom}}{4}
</math>

Для каждой внутренней точки на каждой итерации выполняется:
* 4 чтения значений соседей
* 3 операции сложения
* 1 операция деления
* 1 запись нового значения
* 1 операция вычисления погрешности (разности между старым и новым значением)

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

Алгоритм имеет итерационную структуру:

# Инициализация матрицы (граничные условия + начальное приближение)
# Для каждой итерации:
## Вычисление новых значений для всех внутренних точек (релаксация)
## Обновление матрицы
## Вычисление максимальной погрешности
## Проверка условия сходимости
# Вычисление контрольной суммы

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

* Инициализация матрицы A граничными условиями и начальными значениями, инициализация матрицы B нулями.
* Цикл по итерациям:
```c
for (it = 1; it <= itmax; it++) {
eps = 0.0;
relax(); // Вычисление B[i][j] как среднее соседей из A
resid(); // Обновление A[i][j] = B[i][j], вычисление погрешности
if (eps < maxeps) break;
}
```
* Вычисление и вывод контрольной суммы

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

Для сетки размером <math>N \times N</math>:
* Каждая итерация требует <math>O(N^2)</math> операций
* Количество итераций зависит от сходимости, ограничено `itmax`
* Общая сложность: <math>O(it\_max \cdot N^2)</math>

Конкретно для каждой внутренней точки на каждой итерации:
* 4 операции чтения
* 3 сложения
* 1 деление
* 1 запись
* 1 вычитание и взятие модуля для погрешности

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

Информационный граф алгоритма состоит из четырёх групп вершин, расположенных в целочисленных узлах областей различной размерности.

[[file:information_graph.png|thumb|center|1150px|Информационный граф метода релаксации для <math>N</math> = 4 , <math>max\_it</math> = 2]]

1) Первая группа вершин (входные данные и инициализация) :

Расположена в двумерной области с координатами <math>(i, j)</math>.
Диапазоны изменения координат: <math>i ∈ [0, N−1] , j ∈ [0, N−1]</math>.

Операция:
* если <math>i = 0</math> или <math>i = N−1</math> или <math>j = 0</math> или <math>j = N−1</math> → <math>A[i][j] = 0</math> (граничные условия),
* иначе <math>A[i][j] = 1 + i + j</math> (начальное приближение внутри области).

Результат: элементы массива <math>A[i][j]</math> на итерации 0.
Все вершины этой группы являются источниками (входными данными алгоритма).
На рисунке соответствуют синим прямоугольникам слева с надписью <math>A[i][j]^{(0)}</math>.

2) Вторая группа вершин (релаксация — вычисление нового слоя) :

Расположена в трёхмерной области с координатами <math>(i, j, k)</math>.

Диапазоны изменения координат:
<math>i ∈ [1, N−2] , j ∈ [1, N−2] , k ∈ [1, it\_max]</math>, где <math>k</math> — номер выполненной итерации.

Соответствующая операция:
<math>B[i][j] = (A[i−1][j] + A[i+1][j] + A[i][j−1] + A[i][j+1]) / 4.0</math>
(усреднение по четырём соседям — шаблон «крест»).

Аргументы операции:
четыре значения <math>A[⋅][⋅]</math> с предыдущего слоя (итерации <math>k−1</math>).

Результат срабатывания: элемент нового слоя <math>B[i][j]^{(k)}</math>.
На рисунке — зелёные блоки с надписью <math>B[i][j]^{(k)}</math>.

3) Третья группа вершин (вычисление невязки и обновление <math>A</math>) :

Расположена в той же трёхмерной области с координатами <math>(i, j, k)</math>.
Операция выполняется сразу после второй группы на той же итерации <math>k</math> :

# <math>e = |A[i][j]^{(k-1)} − B[i][j]^{(k)}|</math>
# <math>A[i][j]^{(k)} = B[i][j]^{(k)}</math>
# <math>eps^{(k)} = max(eps^{(k)}, e)</math>

Аргументы: значения <math>A[i][j]^{(k-1)}</math> из первой группы вершин и <math>B[i][j]^{(k)}</math> из второй группы вершин.

Результат:
* обновлённое значение <math>A[i][j]^{(k)}</math>, которое будет использовано на следующей итерации,
* вклад в глобальную норму невязки <math>eps^{(k)}</math>.

На рисунке — жёлтые блоки с надписями вида <math>A[i][j]^{(k)} = B[i][j]^{(k)}</math>.

4) Четвёртая группа вершин (условия завершения) :

Состоит из двух типов вершин скалярной размерности (координата <math>k</math>):

* Вершины сравнения <math>eps^{(k)} < max\_eps</math> :
** Координата <math>k ∈ [1, it\_max]</math>.
** Аргумент — накопленное на итерации <math>k</math> значение <math>eps^{(k)}</math>.
** На рисунке — фиолетовые овалы с надписью <math>eps^{(k)} < max\_eps</math>.

* Вершина проверки числа итераций <math>iteration = it\_max</math> : На рисунке — красный прямоугольник справа.

Обе вершины являются стоками-условиями (управляющие вершины).
При выполнении любого из условий (YES) происходит выход из цикла (break).
При невыполнении обоих условий (NO) алгоритм переходит к следующей итерации <math>k+1</math>.

Таким образом, граф имеет ярко выраженную волновую структуру по итерациям <math>k</math>, с полным барьером синхронизации в конце каждой итерации (все элементы нового слоя должны быть вычислены перед подсчётом невязки и переходом к следующей итерации).

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

Алгоритм обладает высоким потенциалом параллелизма:
* На каждой итерации все внутренние точки могут обновляться независимо
* Высота ЯПФ: <math>O(it\_max)</math> (последовательные итерации)
* Ширина ЯПФ: <math>O(N^2)</math> (все точки могут обрабатываться параллельно на одной итерации)

В MPI-реализации:
* Сетка разбивается на горизонтальные полосы
* Каждый процесс обрабатывает свою полосу
* Необходим обмен граничными строками между соседними процессами
* Используются неблокирующие операции MPI для перекрытия вычислений и коммуникаций

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

Входные данные:
* Размер сетки <math>N</math> (целое число)
* Матрица значений <math>A</math> размером <math>N \times N</math> (вещественные числа)
* Параметры: maxeps (точность), itmax (максимальное число итераций)

Выходные данные:
* Матрица <math>A</math> с решением (вещественные числа)
* Контрольная сумма <math>S</math> (вещественное число)
* Число выполненных итераций (целое)
* Время выполнения (в параллельной версии)

Объём данных: <math>O(N^2)</math>

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

# Детерминированность: При фиксированных входных данных и последовательном выполнении результат детерминирован.
# Сходимость: Метод сходится медленно (линейно), количество итераций пропорционально <math>N^2</math> для достижения заданной точности.
# Устойчивость: Алгоритм устойчив к ошибкам округления.
# Масштабируемость: Хорошо масштабируется на параллельных системах благодаря локальности данных.
# Вычислительная мощность: Отношение числа операций к объёму данных составляет <math>O(it\_max)</math>.

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

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

В последовательной реализации:
# Используются две матрицы <math>A</math> и <math>B</math> для хранения значений на текущей и предыдущей итерациях.
# Граничные условия заданы нулевыми.
# Начальное приближение: <math>A[i][j] = 1.0 + i + j</math> для внутренних точек.
# Реализован режим вычисления максимальной погрешности для контроля сходимости.
# Контрольная сумма вычисляется по формуле, включающей веса <math>(i+1)(j+1)</math>.

Ключевые особенности:

```c
// Вычисление нового значения
B[i][j] = (A[i-1][j] + A[i+1][j] + A[i][j-1] + A[i][j+1]) / 4.0;
// Обновление и вычисление погрешности
e = fabs(A[i][j] - B[i][j]);
A[i][j] = B[i][j];
eps = Max(eps, e);
```

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

MPI-реализация включает следующие особенности:

* Разбиение данных: Сетка разбивается на горизонтальные полосы, каждая обрабатывается отдельным процессом.
* Распределение нагрузки: При неравномерном разбиении (когда <math>N</math> не кратно числу процессов) первые процессы получают на одну строку больше.
* Обмен граничными данными: Используются неблокирующие операции <math>MPI\_Isend / MPI\_Irecv</math> для перекрытия вычислений и коммуникаций.
* Вычисление погрешности: Локальные погрешности собираются с помощью <math>MPI\_Allreduce</math> для нахождения глобального максимума.
* Вычисление контрольной суммы: Частичные суммы вычисляются на каждом процессе и собираются с помощью <math>MPI\_Reduce</math>.

```c
// Обмен граничными строками
if (rank > 0) {
MPI_Irecv(localA[0], N, MPI_FLOAT, rank-1, 0, MPI_COMM_WORLD, &req[req_count++]);
MPI_Isend(localA[1], N, MPI_FLOAT, rank-1, 0, MPI_COMM_WORLD, &req[req_count++]);
}
if (rank < size-1) {
MPI_Irecv(localA[local_rows+1], N, MPI_FLOAT, rank+1, 0, MPI_COMM_WORLD, &req[req_count++]);
MPI_Isend(localA[local_rows], N, MPI_FLOAT, rank+1, 0, MPI_COMM_WORLD, &req[req_count++]);
}
```

* Оптимизация: Пропуск вычислений для граничных строк на первом и последнем процессах.
* Измерение времени: Использование <math>MPI\_Wtime</math> для точного измерения времени выполнения.

=== Результаты прогонов===

Для получения результатов была проведена серия экспериментов с различными:
# Размерами сетки ( <math>N</math> = 512, 1024, 2048, 4096 )
# Количеством процессов ( 1, 2, 3, ... , 28 )
# Параметрами точности ( <math>max\_eps</math> = 0.1e-7 )

[[file:correct_result.png|thumb|center|700px|Зависимость времени выполнения от размера матрицы и числа процессов]]

Результаты экспериментов подтверждают корректность и эффективность MPI-реализации :
* Время выполнения растёт пропорционально квадрату размера сетки, демонстрируя сложность <math>O(N²)</math>.
* Алгоритм хорошо масштабируется: для <math>N</math> = 4096 использование 28 процессов ускоряет вычисления в 20 раз по сравнению с последовательной версией.
* Значения контрольной суммы сохраняются при любом количестве процессов, что подтверждает корректность обмена данными.
* Наилучшая эффективность достигается при балансе между объёмом вычислений на процесс и затратами на коммуникации.

== Литература ==

# Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. — М.: Наука, 1978.
# Самарский А. А., Гулин А. В. Численные методы. - M.: Наука, 1989.
# Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical Recipes: The Art of Scientific Computing. — 3rd ed. — Cambridge University Press, 2007.
# Gropp W., Lusk E., Skjellum A. Using MPI: Portable Parallel Programming with the Message-Passing Interface. — 3rd ed. — MIT Press, 2014.
# Документация по MPI: https://www.mpi-forum.org/docs/

Метод релаксации матрицы

2025-12-09T04:03:51Z

Овсиенко Олеся:

{{algorithm
| name = Метод релаксации для уравнения Лапласа
| serial_complexity = <math>O(it\_max \cdot N^2)</math>
| pf_height = <math>O(it\_max)</math>
| pf_width = <math>O(N^2)</math>
| input_data = <math>N^2</math> (матрица значений)
| output_data = <math>N^2</math> (матрица значений)
}}

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

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

Метод релаксации является одним из простейших итерационных методов решения уравнений в частных производных. В данной реализации он применяется для численного решения уравнения Лапласа на прямоугольной области с граничными условиями Дирихле. Алгоритм основан на дискретизации уравнения с использованием конечно-разностной схемы и последующем итеративном обновлении значений в узлах сетки до достижения заданной точности.

Метод широко используется в вычислительной физике для решения стационарных задач, таких как распределение потенциала, тепловое равновесие и др. Благодаря простоте реализации и естественному параллелизму (каждая точка сетки обновляется независимо на каждой итерации) алгоритм хорошо подходит для распараллеливания на многопроцессорных системах.

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

Исходная задача: решение уравнения Лапласа
<math>
\frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} = 0
</math>
в прямоугольной области <math>[0,1]\times[0,1]</math> с нулевыми граничными условиями.

Дискретизация на равномерной сетке <math>N \times N</math> с шагом <math>h = 1/(N-1)</math> приводит к системе линейных уравнений, которая решается методом релаксации:

Для каждого внутреннего узла <math>(i,j)</math> на итерации <math>k</math>:
<math>
u_{i,j}^{(k)} = \frac{u_{i-1,j}^{(k-1)} + u_{i+1,j}^{(k-1)} + u_{i,j-1}^{(k-1)} + u_{i,j+1}^{(k-1)}}{4}
</math>

Критерий остановки:
<math>
\max_{i,j} |u_{i,j}^{(k)} - u_{i,j}^{(k-1)}| < \varepsilon_{\text{max}}
</math>

Начальное приближение для внутренних точек:
<math>
u_{i,j}^{(0)} = 1 + i + j
</math>

Контрольная сумма для верификации:
<math>
S = \frac{1}{N^2} \sum_{i=0}^{N-1} \sum_{j=0}^{N-1} u_{i,j} \cdot (i+1) \cdot (j+1)
</math>

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

Вычислительное ядро алгоритма состоит из операций обновления значений во внутренних узлах сетки:
<math>
\text{new_val} = \frac{\text{left} + \text{right} + \text{top} + \text{bottom}}{4}
</math>

Для каждой внутренней точки на каждой итерации выполняется:
* 4 чтения значений соседей
* 3 операции сложения
* 1 операция деления
* 1 запись нового значения
* 1 операция вычисления погрешности (разности между старым и новым значением)

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

Алгоритм имеет итерационную структуру:

# Инициализация матрицы (граничные условия + начальное приближение)
# Для каждой итерации:
## Вычисление новых значений для всех внутренних точек (релаксация)
## Обновление матрицы
## Вычисление максимальной погрешности
## Проверка условия сходимости
# Вычисление контрольной суммы

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

* Инициализация матрицы A граничными условиями и начальными значениями, инициализация матрицы B нулями.
* Цикл по итерациям:
```c
for (it = 1; it <= itmax; it++) {
eps = 0.0;
relax(); // Вычисление B[i][j] как среднее соседей из A
resid(); // Обновление A[i][j] = B[i][j], вычисление погрешности
if (eps < maxeps) break;
}
```
* Вычисление и вывод контрольной суммы

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

Для сетки размером <math>N \times N</math>:
* Каждая итерация требует <math>O(N^2)</math> операций
* Количество итераций зависит от сходимости, ограничено `itmax`
* Общая сложность: <math>O(it\_max \cdot N^2)</math>

Конкретно для каждой внутренней точки на каждой итерации:
* 4 операции чтения
* 3 сложения
* 1 деление
* 1 запись
* 1 вычитание и взятие модуля для погрешности

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

Информационный граф алгоритма состоит из четырёх групп вершин, расположенных в целочисленных узлах областей различной размерности.

[[file:information_graph.png|thumb|center|1150px|Информационный граф метода релаксации для <math>N</math> = 4 , <math>max\_it</math> = 2]]

1) Первая группа вершин (входные данные и инициализация) :

Расположена в двумерной области с координатами <math>(i, j)</math>.
Диапазоны изменения координат: <math>i ∈ [0, N−1] , j ∈ [0, N−1]</math>.

Операция:
* если <math>i = 0</math> или <math>i = N−1</math> или <math>j = 0</math> или <math>j = N−1</math> → <math>A[i][j] = 0</math> (граничные условия),
* иначе <math>A[i][j] = 1 + i + j</math> (начальное приближение внутри области).

Результат: элементы массива <math>A[i][j]</math> на итерации 0.
Все вершины этой группы являются источниками (входными данными алгоритма).
На рисунке соответствуют синим прямоугольникам слева с надписью <math>A[i][j]^{(0)}</math>.

2) Вторая группа вершин (релаксация — вычисление нового слоя) :

Расположена в трёхмерной области с координатами <math>(i, j, k)</math>.

Диапазоны изменения координат:
<math>i ∈ [1, N−2] , j ∈ [1, N−2] , k ∈ [1, it\_max]</math>, где <math>k</math> — номер выполненной итерации.

Соответствующая операция:
<math>B[i][j] = (A[i−1][j] + A[i+1][j] + A[i][j−1] + A[i][j+1]) / 4.0</math>
(усреднение по четырём соседям — шаблон «крест»).

Аргументы операции:
четыре значения <math>A[⋅][⋅]</math> с предыдущего слоя (итерации <math>k−1</math>).

Результат срабатывания: элемент нового слоя <math>B[i][j]^{(k)}</math>.
На рисунке — зелёные блоки с надписью <math>B[i][j]^{(k)}</math>.

3) Третья группа вершин (вычисление невязки и обновление <math>A</math>) :

Расположена в той же трёхмерной области с координатами <math>(i, j, k)</math>.
Операция выполняется сразу после второй группы на той же итерации <math>k</math> :

# <math>e = |A[i][j]^{(k-1)} − B[i][j]^{(k)}|</math>
# <math>A[i][j]^{(k)} = B[i][j]^{(k)}</math>
# <math>eps^{(k)} = max(eps^{(k)}, e)</math>

Аргументы: значения <math>A[i][j]^{(k-1)}</math> из первой группы вершин и <math>B[i][j]^{(k)}</math> из второй группы вершин.

Результат:
* обновлённое значение <math>A[i][j]^{(k)}</math>, которое будет использовано на следующей итерации,
* вклад в глобальную норму невязки <math>eps^{(k)}</math>.

На рисунке — жёлтые блоки с надписями вида <math>A[i][j]^{(k)} = B[i][j]^{(k)}</math>.

4) Четвёртая группа вершин (условия завершения) :

Состоит из двух типов вершин скалярной размерности (координата <math>k</math>):

* Вершины сравнения <math>eps^{(k)} < max\_eps</math> :
** Координата <math>k ∈ [1, it\_max]</math>.
** Аргумент — накопленное на итерации <math>k</math> значение <math>eps^{(k)}</math>.
** На рисунке — фиолетовые овалы с надписью <math>eps^{(k)} < max\_eps</math>.

* Вершина проверки числа итераций <math>iteration = it\_max</math> : На рисунке — красный прямоугольник справа.

Обе вершины являются стоками-условиями (управляющие вершины).
При выполнении любого из условий (YES) происходит выход из цикла (break).
При невыполнении обоих условий (NO) алгоритм переходит к следующей итерации <math>k+1</math>.

Таким образом, граф имеет ярко выраженную волновую структуру по итерациям <math>k</math>, с полным барьером синхронизации в конце каждой итерации (все элементы нового слоя должны быть вычислены перед подсчётом невязки и переходом к следующей итерации).

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

Алгоритм обладает высоким потенциалом параллелизма:
* На каждой итерации все внутренние точки могут обновляться независимо
* Высота ЯПФ: <math>O(it\_max)</math> (последовательные итерации)
* Ширина ЯПФ: <math>O(N^2)</math> (все точки могут обрабатываться параллельно на одной итерации)

В MPI-реализации:
* Сетка разбивается на горизонтальные полосы
* Каждый процесс обрабатывает свою полосу
* Необходим обмен граничными строками между соседними процессами
* Используются неблокирующие операции MPI для перекрытия вычислений и коммуникаций

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

Входные данные:
* Размер сетки <math>N</math> (целое число)
* Матрица значений <math>A</math> размером <math>N \times N</math> (вещественные числа)
* Параметры: maxeps (точность), itmax (максимальное число итераций)

Выходные данные:
* Матрица <math>A</math> с решением (вещественные числа)
* Контрольная сумма <math>S</math> (вещественное число)
* Число выполненных итераций (целое)
* Время выполнения (в параллельной версии)

Объём данных: <math>O(N^2)</math>

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

# Детерминированность: При фиксированных входных данных и последовательном выполнении результат детерминирован.
# Сходимость: Метод сходится медленно (линейно), количество итераций пропорционально <math>N^2</math> для достижения заданной точности.
# Устойчивость: Алгоритм устойчив к ошибкам округления.
# Масштабируемость: Хорошо масштабируется на параллельных системах благодаря локальности данных.
# Вычислительная мощность: Отношение числа операций к объёму данных составляет <math>O(it\_max)</math>.

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

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

В последовательной реализации:
# Используются две матрицы <math>A</math> и <math>B</math> для хранения значений на текущей и предыдущей итерациях.
# Граничные условия заданы нулевыми.
# Начальное приближение: <math>A[i][j] = 1.0 + i + j</math> для внутренних точек.
# Реализован режим вычисления максимальной погрешности для контроля сходимости.
# Контрольная сумма вычисляется по формуле, включающей веса <math>(i+1)(j+1)</math>.

Ключевые особенности:

```c
// Вычисление нового значения
B[i][j] = (A[i-1][j] + A[i+1][j] + A[i][j-1] + A[i][j+1]) / 4.0;
// Обновление и вычисление погрешности
e = fabs(A[i][j] - B[i][j]);
A[i][j] = B[i][j];
eps = Max(eps, e);
```

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

MPI-реализация включает следующие особенности:

* Разбиение данных: Сетка разбивается на горизонтальные полосы, каждая обрабатывается отдельным процессом.
* Распределение нагрузки: При неравномерном разбиении (когда <math>N</math> не кратно числу процессов) первые процессы получают на одну строку больше.
* Обмен граничными данными: Используются неблокирующие операции <math>MPI\_Isend / MPI\_Irecv</math> для перекрытия вычислений и коммуникаций.
* Вычисление погрешности: Локальные погрешности собираются с помощью <math>MPI\_Allreduce</math> для нахождения глобального максимума.
* Вычисление контрольной суммы: Частичные суммы вычисляются на каждом процессе и собираются с помощью <math>MPI\_Reduce</math>.

```c
// Обмен граничными строками
if (rank > 0) {
MPI_Irecv(localA[0], N, MPI_FLOAT, rank-1, 0, MPI_COMM_WORLD, &req[req_count++]);
MPI_Isend(localA[1], N, MPI_FLOAT, rank-1, 0, MPI_COMM_WORLD, &req[req_count++]);
}
if (rank < size-1) {
MPI_Irecv(localA[local_rows+1], N, MPI_FLOAT, rank+1, 0, MPI_COMM_WORLD, &req[req_count++]);
MPI_Isend(localA[local_rows], N, MPI_FLOAT, rank+1, 0, MPI_COMM_WORLD, &req[req_count++]);
}
```

* Оптимизация: Пропуск вычислений для граничных строк на первом и последнем процессах.
* Измерение времени: Использование <math>MPI\_Wtime</math> для точного измерения времени выполнения.

=== Результаты прогонов===

Для получения результатов была проведена серия экспериментов с различными:
# Размерами сетки ( <math>N</math> = 512, 1024, 2048, 4096 )
# Количеством процессов ( 1, 2, 3, ... , 28 )
# Параметрами точности ( <math>max\_eps</math> = 0.1e-7 )

[[file:correct_result.png|thumb|center|700px|Зависимость времени выполнения от размера матрицы и числа процессов]]

Результаты экспериментов подтверждают корректность и эффективность MPI-реализации :
* Время выполнения растёт пропорционально квадрату размера сетки, демонстрируя сложность <math>O(N²)</math>.
* Алгоритм хорошо масштабируется: для <math>N</math> = 4096 использование 28 процессов ускоряет вычисления в 20 раз по сравнению с последовательной версией.
* Значения контрольной суммы сохраняются при любом количестве процессов, что подтверждает корректность обмена данными.
* Наилучшая эффективность достигается при балансе между объёмом вычислений на процесс и затратами на коммуникации.

== Литература ==

# Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. — М.: Наука, 1978.
# Самарский А. А., Гулин А. В. Численные методы. - M.: Наука, 1989.
# Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical Recipes: The Art of Scientific Computing. — 3rd ed. — Cambridge University Press, 2007.
# Gropp W., Lusk E., Skjellum A. Using MPI: Portable Parallel Programming with the Message-Passing Interface. — 3rd ed. — MIT Press, 2014.
# Документация по MPI: https://www.mpi-forum.org/docs/

Метод релаксации матрицы

2025-12-09T03:46:32Z

Овсиенко Олеся:

{{algorithm
| name = Метод релаксации для уравнения Лапласа
| serial_complexity = <math>O(it\_max \cdot N^2)</math>
| pf_height = <math>O(it\_max)</math>
| pf_width = <math>O(N^2)</math>
| input_data = <math>N^2</math> (матрица значений)
| output_data = <math>N^2</math> (матрица значений)
}}

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

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

Метод релаксации является одним из простейших итерационных методов решения уравнений в частных производных. В данной реализации он применяется для численного решения уравнения Лапласа на прямоугольной области с граничными условиями Дирихле. Алгоритм основан на дискретизации уравнения с использованием конечно-разностной схемы и последующем итеративном обновлении значений в узлах сетки до достижения заданной точности.

Метод широко используется в вычислительной физике для решения стационарных задач, таких как распределение потенциала, тепловое равновесие и др. Благодаря простоте реализации и естественному параллелизму (каждая точка сетки обновляется независимо на каждой итерации) алгоритм хорошо подходит для распараллеливания на многопроцессорных системах.

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

Исходная задача: решение уравнения Лапласа
<math>
\frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} = 0
</math>
в прямоугольной области <math>[0,1]\times[0,1]</math> с нулевыми граничными условиями.

Дискретизация на равномерной сетке <math>N \times N</math> с шагом <math>h = 1/(N-1)</math> приводит к системе линейных уравнений, которая решается методом релаксации:

Для каждого внутреннего узла <math>(i,j)</math> на итерации <math>k</math>:
<math>
u_{i,j}^{(k)} = \frac{u_{i-1,j}^{(k-1)} + u_{i+1,j}^{(k-1)} + u_{i,j-1}^{(k-1)} + u_{i,j+1}^{(k-1)}}{4}
</math>

Критерий остановки:
<math>
\max_{i,j} |u_{i,j}^{(k)} - u_{i,j}^{(k-1)}| < \varepsilon_{\text{max}}
</math>

Начальное приближение для внутренних точек:
<math>
u_{i,j}^{(0)} = 1 + i + j
</math>

Контрольная сумма для верификации:
<math>
S = \frac{1}{N^2} \sum_{i=0}^{N-1} \sum_{j=0}^{N-1} u_{i,j} \cdot (i+1) \cdot (j+1)
</math>

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

Вычислительное ядро алгоритма состоит из операций обновления значений во внутренних узлах сетки:
<math>
\text{new_val} = \frac{\text{left} + \text{right} + \text{top} + \text{bottom}}{4}
</math>

Для каждой внутренней точки на каждой итерации выполняется:
* 4 чтения значений соседей
* 3 операции сложения
* 1 операция деления
* 1 запись нового значения
* 1 операция вычисления погрешности (разности между старым и новым значением)

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

Алгоритм имеет итерационную структуру:

# Инициализация матрицы (граничные условия + начальное приближение)
# Для каждой итерации:
## Вычисление новых значений для всех внутренних точек (релаксация)
## Обновление матрицы
## Вычисление максимальной погрешности
## Проверка условия сходимости
# Вычисление контрольной суммы

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

* Инициализация матрицы A граничными условиями и начальными значениями, инициализация матрицы B нулями.
* Цикл по итерациям:
```c
for (it = 1; it <= itmax; it++) {
eps = 0.0;
relax(); // Вычисление B[i][j] как среднее соседей из A
resid(); // Обновление A[i][j] = B[i][j], вычисление погрешности
if (eps < maxeps) break;
}
```
* Вычисление и вывод контрольной суммы

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

Для сетки размером <math>N \times N</math>:
* Каждая итерация требует <math>O(N^2)</math> операций
* Количество итераций зависит от сходимости, ограничено `itmax`
* Общая сложность: <math>O(it\_max \cdot N^2)</math>

Конкретно для каждой внутренней точки на каждой итерации:
* 4 операции чтения
* 3 сложения
* 1 деление
* 1 запись
* 1 вычитание и взятие модуля для погрешности

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

Информационный граф алгоритма состоит из четырёх групп вершин, расположенных в целочисленных узлах областей различной размерности.

[[file:information_graph.png|thumb|center|1150px|Информационный граф метода релаксации для <math>N</math> = 4 , <math>max\_it</math> = 2]]

1) Первая группа вершин (входные данные и инициализация) :

Расположена в двумерной области с координатами <math>(i, j)</math>.
Диапазоны изменения координат: <math>i ∈ [0, N−1] , j ∈ [0, N−1]</math>.

Операция:
* если <math>i = 0</math> или <math>i = N−1</math> или <math>j = 0</math> или <math>j = N−1</math> → <math>A[i][j] = 0</math> (граничные условия),
* иначе <math>A[i][j] = 1 + i + j</math> (начальное приближение внутри области).

Результат: элементы массива <math>A[i][j]</math> на итерации 0.
Все вершины этой группы являются источниками (входными данными алгоритма).
На рисунке соответствуют синим прямоугольникам слева с надписью <math>A[i][j]⁽⁰⁾</math>.

2) Вторая группа вершин (релаксация — вычисление нового слоя) :

Расположена в трёхмерной области с координатами <math>(i, j, k)</math>.

Диапазоны изменения координат:
<math>i ∈ [1, N−2] , j ∈ [1, N−2] , k ∈ [1, it\_max]</math>, где <math>k</math> — номер выполненной итерации.

Соответствующая операция:
<math>B[i][j] = (A[i−1][j] + A[i+1][j] + A[i][j−1] + A[i][j+1]) / 4.0</math>
(усреднение по четырём соседям — шаблон «крест»).

Аргументы операции:
четыре значения <math>A[⋅][⋅]</math> с предыдущего слоя (итерации <math>k−1</math>).

Результат срабатывания: элемент нового слоя <math>B[i][j]⁽ᵏ⁾</math>.
На рисунке — зелёные блоки с надписью <math>B[i][j]⁽ᵏ⁾</math>.

3) Третья группа вершин (вычисление невязки и обновление <math>A</math>) :

Расположена в той же трёхмерной области с координатами <math>(i, j, k)</math>.
Операция выполняется сразу после второй группы на той же итерации <math>k</math> :

# <math>e = |A[i][j]⁽ᵏ⁻¹⁾ − B[i][j]⁽ᵏ⁾|</math>
# <math>A[i][j]⁽ᵏ⁾ = B[i][j]⁽ᵏ⁾</math>
# <math>eps⁽ᵏ⁾ = max(eps⁽ᵏ⁾, e)</math>

Аргументы: значения <math>A[i][j]⁽ᵏ⁻¹⁾</math> из первой группы вершин и <math>B[i][j]⁽ᵏ⁾</math> из второй группы вершин.

Результат:
* обновлённое значение <math>A[i][j]⁽ᵏ⁾</math>, которое будет использовано на следующей итерации,
* вклад в глобальную норму невязки <math>eps⁽ᵏ⁾</math>.

На рисунке — жёлтые блоки с надписями вида <math>A[i][j]⁽ᵏ⁾ = B[i][j]⁽ᵏ⁾</math>.

4) Четвёртая группа вершин (условия завершения) :

Состоит из двух типов вершин скалярной размерности (координата <math>k</math>):

* Вершины сравнения <math>eps⁽ᵏ⁾ < max\_eps</math> :
** Координата <math>k ∈ [1, it\_max]</math>.
** Аргумент — накопленное на итерации <math>k</math> значение <math>eps⁽ᵏ⁾</math>.
** На рисунке — фиолетовые овалы с надписью <math>eps⁽ᵏ⁾ < max\_eps</math>.

* Вершина проверки числа итераций <math>iteration = it\_max</math> : На рисунке — красный прямоугольник справа.

Обе вершины являются стоками-условиями (управляющие вершины).
При выполнении любого из условий (YES) происходит выход из цикла (break).
При невыполнении обоих условий (NO) алгоритм переходит к следующей итерации <math>k+1</math>.

Таким образом, граф имеет ярко выраженную волновую структуру по итерациям <math>k</math>, с полным барьером синхронизации в конце каждой итерации (все элементы нового слоя должны быть вычислены перед подсчётом невязки и переходом к следующей итерации).

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

Алгоритм обладает высоким потенциалом параллелизма:
* На каждой итерации все внутренние точки могут обновляться независимо
* Высота ЯПФ: <math>O(it\_max)</math> (последовательные итерации)
* Ширина ЯПФ: <math>O(N^2)</math> (все точки могут обрабатываться параллельно на одной итерации)

В MPI-реализации:
* Сетка разбивается на горизонтальные полосы
* Каждый процесс обрабатывает свою полосу
* Необходим обмен граничными строками между соседними процессами
* Используются неблокирующие операции MPI для перекрытия вычислений и коммуникаций

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

Входные данные:
* Размер сетки <math>N</math> (целое число)
* Матрица значений <math>A</math> размером <math>N \times N</math> (вещественные числа)
* Параметры: maxeps (точность), itmax (максимальное число итераций)

Выходные данные:
* Матрица <math>A</math> с решением (вещественные числа)
* Контрольная сумма <math>S</math> (вещественное число)
* Число выполненных итераций (целое)
* Время выполнения (в параллельной версии)

Объём данных: <math>O(N^2)</math>

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

# Детерминированность: При фиксированных входных данных и последовательном выполнении результат детерминирован.
# Сходимость: Метод сходится медленно (линейно), количество итераций пропорционально <math>N^2</math> для достижения заданной точности.
# Устойчивость: Алгоритм устойчив к ошибкам округления.
# Масштабируемость: Хорошо масштабируется на параллельных системах благодаря локальности данных.
# Вычислительная мощность: Отношение числа операций к объёму данных составляет <math>O(it\_max)</math>.

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

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

В последовательной реализации:
# Используются две матрицы <math>A</math> и <math>B</math> для хранения значений на текущей и предыдущей итерациях.
# Граничные условия заданы нулевыми.
# Начальное приближение: <math>A[i][j] = 1.0 + i + j</math> для внутренних точек.
# Реализован режим вычисления максимальной погрешности для контроля сходимости.
# Контрольная сумма вычисляется по формуле, включающей веса <math>(i+1)(j+1)</math>.

Ключевые особенности:

```c
// Вычисление нового значения
B[i][j] = (A[i-1][j] + A[i+1][j] + A[i][j-1] + A[i][j+1]) / 4.0;
// Обновление и вычисление погрешности
e = fabs(A[i][j] - B[i][j]);
A[i][j] = B[i][j];
eps = Max(eps, e);
```

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

MPI-реализация включает следующие особенности:

* Разбиение данных: Сетка разбивается на горизонтальные полосы, каждая обрабатывается отдельным процессом.
* Распределение нагрузки: При неравномерном разбиении (когда <math>N</math> не кратно числу процессов) первые процессы получают на одну строку больше.
* Обмен граничными данными: Используются неблокирующие операции <math>MPI\_Isend / MPI\_Irecv</math> для перекрытия вычислений и коммуникаций.
* Вычисление погрешности: Локальные погрешности собираются с помощью <math>MPI\_Allreduce</math> для нахождения глобального максимума.
* Вычисление контрольной суммы: Частичные суммы вычисляются на каждом процессе и собираются с помощью <math>MPI\_Reduce</math>.

```c
// Обмен граничными строками
if (rank > 0) {
MPI_Irecv(localA[0], N, MPI_FLOAT, rank-1, 0, MPI_COMM_WORLD, &req[req_count++]);
MPI_Isend(localA[1], N, MPI_FLOAT, rank-1, 0, MPI_COMM_WORLD, &req[req_count++]);
}
if (rank < size-1) {
MPI_Irecv(localA[local_rows+1], N, MPI_FLOAT, rank+1, 0, MPI_COMM_WORLD, &req[req_count++]);
MPI_Isend(localA[local_rows], N, MPI_FLOAT, rank+1, 0, MPI_COMM_WORLD, &req[req_count++]);
}
```

* Оптимизация: Пропуск вычислений для граничных строк на первом и последнем процессах.
* Измерение времени: Использование <math>MPI\_Wtime</math> для точного измерения времени выполнения.

=== Результаты прогонов===

Для получения результатов была проведена серия экспериментов с различными:
# Размерами сетки ( <math>N</math> = 512, 1024, 2048, 4096 )
# Количеством процессов ( 1, 2, 3, ... , 28 )
# Параметрами точности ( <math>max\_eps</math> = 0.1e-7 )

[[file:correct_result.png|thumb|center|700px|Зависимость времени выполнения от размера матрицы и числа процессов]]

Результаты экспериментов подтверждают корректность и эффективность MPI-реализации :
* Время выполнения растёт пропорционально квадрату размера сетки, демонстрируя сложность <math>O(N²)</math>.
* Алгоритм хорошо масштабируется: для <math>N</math> = 4096 использование 28 процессов ускоряет вычисления в 20 раз по сравнению с последовательной версией.
* Значения контрольной суммы сохраняются при любом количестве процессов, что подтверждает корректность обмена данными.
* Наилучшая эффективность достигается при балансе между объёмом вычислений на процесс и затратами на коммуникации.

== Литература ==

# Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. — М.: Наука, 1978.
# Самарский А. А., Гулин А. В. Численные методы. - M.: Наука, 1989.
# Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical Recipes: The Art of Scientific Computing. — 3rd ed. — Cambridge University Press, 2007.
# Gropp W., Lusk E., Skjellum A. Using MPI: Portable Parallel Programming with the Message-Passing Interface. — 3rd ed. — MIT Press, 2014.
# Документация по MPI: https://www.mpi-forum.org/docs/

Метод релаксации матрицы

2025-12-09T03:42:53Z

Овсиенко Олеся:

{{algorithm
| name = Метод релаксации для уравнения Лапласа
| serial_complexity = <math>O(it\_max \cdot N^2)</math>
| pf_height = <math>O(it\_max)</math>
| pf_width = <math>O(N^2)</math>
| input_data = <math>N^2</math> (матрица значений)
| output_data = <math>N^2</math> (матрица значений)
}}

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

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

Метод релаксации является одним из простейших итерационных методов решения уравнений в частных производных. В данной реализации он применяется для численного решения уравнения Лапласа на прямоугольной области с граничными условиями Дирихле. Алгоритм основан на дискретизации уравнения с использованием конечно-разностной схемы и последующем итеративном обновлении значений в узлах сетки до достижения заданной точности.

Метод широко используется в вычислительной физике для решения стационарных задач, таких как распределение потенциала, тепловое равновесие и др. Благодаря простоте реализации и естественному параллелизму (каждая точка сетки обновляется независимо на каждой итерации) алгоритм хорошо подходит для распараллеливания на многопроцессорных системах.

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

Исходная задача: решение уравнения Лапласа
<math>
\frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} = 0
</math>
в прямоугольной области <math>[0,1]\times[0,1]</math> с нулевыми граничными условиями.

Дискретизация на равномерной сетке <math>N \times N</math> с шагом <math>h = 1/(N-1)</math> приводит к системе линейных уравнений, которая решается методом релаксации:

Для каждого внутреннего узла <math>(i,j)</math> на итерации <math>k</math>:
<math>
u_{i,j}^{(k)} = \frac{u_{i-1,j}^{(k-1)} + u_{i+1,j}^{(k-1)} + u_{i,j-1}^{(k-1)} + u_{i,j+1}^{(k-1)}}{4}
</math>

Критерий остановки:
<math>
\max_{i,j} |u_{i,j}^{(k)} - u_{i,j}^{(k-1)}| < \varepsilon_{\text{max}}
</math>

Начальное приближение для внутренних точек:
<math>
u_{i,j}^{(0)} = 1 + i + j
</math>

Контрольная сумма для верификации:
<math>
S = \frac{1}{N^2} \sum_{i=0}^{N-1} \sum_{j=0}^{N-1} u_{i,j} \cdot (i+1) \cdot (j+1)
</math>

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

Вычислительное ядро алгоритма состоит из операций обновления значений во внутренних узлах сетки:
<math>
\text{new_val} = \frac{\text{left} + \text{right} + \text{top} + \text{bottom}}{4}
</math>

Для каждой внутренней точки на каждой итерации выполняется:
* 4 чтения значений соседей
* 3 операции сложения
* 1 операция деления
* 1 запись нового значения
* 1 операция вычисления погрешности (разности между старым и новым значением)

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

Алгоритм имеет итерационную структуру:

# Инициализация матрицы (граничные условия + начальное приближение)
# Для каждой итерации:
## Вычисление новых значений для всех внутренних точек (релаксация)
## Обновление матрицы
## Вычисление максимальной погрешности
## Проверка условия сходимости
# Вычисление контрольной суммы

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

* Инициализация матрицы A граничными условиями и начальными значениями, инициализация матрицы B нулями.
* Цикл по итерациям:
```c
for (it = 1; it <= itmax; it++) {
eps = 0.0;
relax(); // Вычисление B[i][j] как среднее соседей из A
resid(); // Обновление A[i][j] = B[i][j], вычисление погрешности
if (eps < maxeps) break;
}
```
* Вычисление и вывод контрольной суммы

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

Для сетки размером <math>N \times N</math>:
* Каждая итерация требует <math>O(N^2)</math> операций
* Количество итераций зависит от сходимости, ограничено `itmax`
* Общая сложность: <math>O(it\_max \cdot N^2)</math>

Конкретно для каждой внутренней точки на каждой итерации:
* 4 операции чтения
* 3 сложения
* 1 деление
* 1 запись
* 1 вычитание и взятие модуля для погрешности

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

Информационный граф алгоритма состоит из четырёх групп вершин, расположенных в целочисленных узлах областей различной размерности.

[[file:information_graph.png|thumb|center|1150px|Информационный граф метода релаксации для <math>N</math> = 4 , <math>max\_it</math> = 2]]

1) Первая группа вершин (входные данные и инициализация) :

Расположена в двумерной области с координатами <math>(i, j)</math>.
Диапазоны изменения координат: <math>i ∈ [0, N−1] , j ∈ [0, N−1]</math>.

Операция:
* если <math>i = 0</math> или <math>i = N−1</math> или <math>j = 0</math> или <math>j = N−1</math> → <math>A[i][j] = 0</math> (граничные условия),
* иначе <math>A[i][j] = 1 + i + j</math> (начальное приближение внутри области).

Результат: элементы массива <math>A[i][j]</math> на итерации 0.
Все вершины этой группы являются источниками (входными данными алгоритма).
На рисунке соответствуют синим прямоугольникам слева с надписью <math>A[i][j]⁽⁰⁾</math>.

2) Вторая группа вершин (релаксация — вычисление нового слоя) :

Расположена в трёхмерной области с координатами <math>(i, j, k)</math>.

Диапазоны изменения координат:
<math>i ∈ [1, N−2] , j ∈ [1, N−2] , k ∈ [1, it\_max]</math>, где <math>k</math> — номер выполненной итерации.

Соответствующая операция:
<math>B[i][j] = (A[i−1][j] + A[i+1][j] + A[i][j−1] + A[i][j+1]) / 4.0</math>
(усреднение по четырём соседям — шаблон «крест»).

Аргументы операции:
четыре значения <math>A[⋅][⋅]</math> с предыдущего слоя (итерации <math>k−1</math>).

Результат срабатывания: элемент нового слоя <math>B[i][j]⁽ᵏ⁾</math>.
На рисунке — зелёные блоки с надписью <math>B[i][j]⁽ᵏ⁾</math>.

3) Третья группа вершин (вычисление невязки и обновление <math>A</math>) :

Расположена в той же трёхмерной области с координатами <math>(i, j, k)</math>.
Операция выполняется сразу после второй группы на той же итерации <math>k</math> :

# <math>e = |A[i][j]⁽ᵏ⁻¹⁾ − B[i][j]⁽ᵏ⁾|</math>
# <math>A[i][j]⁽ᵏ⁾ = B[i][j]⁽ᵏ⁾</math>
# <math>eps⁽ᵏ⁾ = max(eps⁽ᵏ⁾, e)</math>

Аргументы: значения <math>A[i][j]⁽ᵏ⁻¹⁾</math> из первой группы вершин и <math>B[i][j]⁽ᵏ⁾</math> из второй группы вершин.

Результат:
* обновлённое значение <math>A[i][j]⁽ᵏ⁾</math>, которое будет использовано на следующей итерации,
* вклад в глобальную норму невязки <math>eps⁽ᵏ⁾</math>.

На рисунке — жёлтые блоки с надписями вида <math>A[i][j]⁽ᵏ⁾ = B[i][j]⁽ᵏ⁾</math>.

4) Четвёртая группа вершин (условия завершения) :

Состоит из двух типов вершин скалярной размерности (координата <math>k</math>):

* Вершины сравнения <math>eps⁽ᵏ⁾ < max\_eps</math> :
** Координата <math>k ∈ [1, it\_max]</math>.
** Аргумент — накопленное на итерации <math>k</math> значение <math>eps⁽ᵏ⁾</math>.
** На рисунке — фиолетовые овалы с надписью <math>eps⁽ᵏ⁾ < max\_eps</math>.

* Вершина проверки числа итераций <math>iteration = it\_max</math> : На рисунке — красный прямоугольник справа.

Обе вершины являются стоками-условиями (управляющие вершины).
При выполнении любого из условий (YES) происходит выход из цикла (break).
При невыполнении обоих условий (NO) алгоритм переходит к следующей итерации <math>k+1</math>.

Таким образом, граф имеет ярко выраженную волновую структуру по итерациям <math>k</math>, с полным барьером синхронизации в конце каждой итерации (все элементы нового слоя должны быть вычислены перед подсчётом невязки и переходом к следующей итерации).

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

Алгоритм обладает высоким потенциалом параллелизма:
* На каждой итерации все внутренние точки могут обновляться независимо
* Высота ЯПФ: <math>O(it\_max)</math> (последовательные итерации)
* Ширина ЯПФ: <math>O(N^2)</math> (все точки могут обрабатываться параллельно на одной итерации)

В MPI-реализации:
* Сетка разбивается на горизонтальные полосы
* Каждый процесс обрабатывает свою полосу
* Необходим обмен граничными строками между соседними процессами
* Используются неблокирующие операции MPI для перекрытия вычислений и коммуникаций

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

Входные данные:
* Размер сетки <math>N</math> (целое число)
* Матрица значений <math>A</math> размером <math>N \times N</math> (вещественные числа)
* Параметры: maxeps (точность), itmax (максимальное число итераций)

Выходные данные:
* Матрица <math>A</math> с решением (вещественные числа)
* Контрольная сумма <math>S</math> (вещественное число)
* Число выполненных итераций (целое)
* Время выполнения (в параллельной версии)

Объём данных: <math>O(N^2)</math>

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

# Детерминированность: При фиксированных входных данных и последовательном выполнении результат детерминирован.
# Сходимость: Метод сходится медленно (линейно), количество итераций пропорционально <math>N^2</math> для достижения заданной точности.
# Устойчивость: Алгоритм устойчив к ошибкам округления.
# Масштабируемость: Хорошо масштабируется на параллельных системах благодаря локальности данных.
# Вычислительная мощность: Отношение числа операций к объёму данных составляет <math>O(it\_max)</math>.

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

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

В последовательной реализации:
# Используются две матрицы <math>A</math> и <math>B</math> для хранения значений на текущей и предыдущей итерациях.
# Граничные условия заданы нулевыми.
# Начальное приближение: <math>A[i][j] = 1.0 + i + j</math> для внутренних точек.
# Реализован режим вычисления максимальной погрешности для контроля сходимости.
# Контрольная сумма вычисляется по формуле, включающей веса <math>(i+1)(j+1)</math>.

Ключевые особенности:

```c
// Вычисление нового значения
B[i][j] = (A[i-1][j] + A[i+1][j] + A[i][j-1] + A[i][j+1]) / 4.0;
// Обновление и вычисление погрешности
e = fabs(A[i][j] - B[i][j]);
A[i][j] = B[i][j];
eps = Max(eps, e);
```

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

MPI-реализация включает следующие особенности:

* Разбиение данных: Сетка разбивается на горизонтальные полосы, каждая обрабатывается отдельным процессом.
* Распределение нагрузки: При неравномерном разбиении (когда <math>N</math> не кратно числу процессов) первые процессы получают на одну строку больше.
* Обмен граничными данными: Используются неблокирующие операции <math>MPI\_Isend / MPI\_Irecv</math> для перекрытия вычислений и коммуникаций.
* Вычисление погрешности: Локальные погрешности собираются с помощью <math>MPI\_Allreduce</math> для нахождения глобального максимума.
* Вычисление контрольной суммы: Частичные суммы вычисляются на каждом процессе и собираются с помощью <math>MPI\_Reduce</math>.

```c
// Обмен граничными строками
if (rank > 0) {
MPI_Irecv(localA[0], N, MPI_FLOAT, rank-1, 0, MPI_COMM_WORLD, &req[req_count++]);
MPI_Isend(localA[1], N, MPI_FLOAT, rank-1, 0, MPI_COMM_WORLD, &req[req_count++]);
}
if (rank < size-1) {
MPI_Irecv(localA[local_rows+1], N, MPI_FLOAT, rank+1, 0, MPI_COMM_WORLD, &req[req_count++]);
MPI_Isend(localA[local_rows], N, MPI_FLOAT, rank+1, 0, MPI_COMM_WORLD, &req[req_count++]);
}
```

* Оптимизация: Пропуск вычислений для граничных строк на первом и последнем процессах.
* Измерение времени: Использование <math>MPI\_Wtime</math> для точного измерения времени выполнения.

=== Результаты прогонов===

Для получения результатов была проведена серия экспериментов с различными:
# Размерами сетки ( <math>N</math> = 512, 1024, 2048, 4096 )
# Количеством процессов ( 1, 2, 3, ... , 28 )
# Параметрами точности ( <math>max\_eps</math> = 0.1e-7 )

[[file:correct_result.png|thumb|center|700px|Зависимость времени выполнения от размера матрицы и числа процессов]]

Результаты экспериментов подтверждают корректность и эффективность MPI-реализации :
* Время выполнения растёт пропорционально квадрату размера сетки, демонстрируя сложность <math>O(N²)</math>.
* Алгоритм хорошо масштабируется: для <math>N</math> = 4096 использование 28 процессов ускоряет вычисления в 20 раз по сравнению с последовательной версией.
* Значения контрольной суммы сохраняются при любом количестве процессов, что подтверждает корректность обмена данными.
* Наилучшая эффективность достигается при балансе между объёмом вычислений на процесс и затратами на коммуникации.

== Литература ==

# Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. — М.: Наука, 1978.
# Самарский А. А., Гулин А. В. Численные методы. - M.: Наука, 1989.
# Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical Recipes: The Art of Scientific Computing. — 3rd ed. — Cambridge University Press, 2007.
# Gropp W., Lusk E., Skjellum A. Using MPI: Portable Parallel Programming with the Message-Passing Interface. — 3rd ed. — MIT Press, 2014.
# Документация по MPI: https://www.mpi-forum.org/docs/

Файл:Correct result.png

2025-12-09T02:53:36Z

Овсиенко Олеся:

Файл:Result of method.png

2025-12-09T02:29:43Z

Овсиенко Олеся:

Метод релаксации матрицы

2025-12-09T02:19:23Z

Овсиенко Олеся: /* Информационный граф алгоритма */

{{algorithm
| name = Метод релаксации для уравнения Лапласа
| serial_complexity = <math>O(it\_max \cdot N^2)</math>
| pf_height = <math>O(it\_max)</math>
| pf_width = <math>O(N^2)</math>
| input_data = <math>N^2</math> (матрица значений)
| output_data = <math>N^2</math> (матрица значений)
}}

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

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

Метод релаксации является одним из простейших итерационных методов решения уравнений в частных производных. В данной реализации он применяется для численного решения уравнения Лапласа на прямоугольной области с граничными условиями Дирихле. Алгоритм основан на дискретизации уравнения с использованием конечно-разностной схемы и последующем итеративном обновлении значений в узлах сетки до достижения заданной точности.

Метод широко используется в вычислительной физике для решения стационарных задач, таких как распределение потенциала, тепловое равновесие и др. Благодаря простоте реализации и естественному параллелизму (каждая точка сетки обновляется независимо на каждой итерации) алгоритм хорошо подходит для распараллеливания на многопроцессорных системах.

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

Исходная задача: решение уравнения Лапласа
<math>
\frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} = 0
</math>
в прямоугольной области <math>[0,1]\times[0,1]</math> с нулевыми граничными условиями.

Дискретизация на равномерной сетке <math>N \times N</math> с шагом <math>h = 1/(N-1)</math> приводит к системе линейных уравнений, которая решается методом Якоби:

Для каждого внутреннего узла <math>(i,j)</math> на итерации <math>k</math>:
<math>
u_{i,j}^{(k)} = \frac{u_{i-1,j}^{(k-1)} + u_{i+1,j}^{(k-1)} + u_{i,j-1}^{(k-1)} + u_{i,j+1}^{(k-1)}}{4}
</math>

Критерий остановки:
<math>
\max_{i,j} |u_{i,j}^{(k)} - u_{i,j}^{(k-1)}| < \varepsilon_{\text{max}}
</math>

Начальное приближение для внутренних точек:
<math>
u_{i,j}^{(0)} = 1 + i + j
</math>

Контрольная сумма для верификации:
<math>
S = \frac{1}{N^2} \sum_{i=0}^{N-1} \sum_{j=0}^{N-1} u_{i,j} \cdot (i+1) \cdot (j+1)
</math>

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

Вычислительное ядро алгоритма состоит из операций обновления значений во внутренних узлах сетки:
<math>
\text{new_val} = \frac{\text{left} + \text{right} + \text{top} + \text{bottom}}{4}
</math>

Для каждой внутренней точки на каждой итерации выполняется:
* 4 чтения значений соседей
* 3 операции сложения
* 1 операция деления
* 1 запись нового значения
* 1 операция вычисления погрешности (разности между старым и новым значением)

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

Алгоритм имеет итерационную структуру:

# Инициализация матрицы (граничные условия + начальное приближение)
# Для каждой итерации:
## Вычисление новых значений для всех внутренних точек (релаксация)
## Обновление матрицы
## Вычисление максимальной погрешности
## Проверка условия сходимости
# Вычисление контрольной суммы

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

* Инициализация матрицы A граничными условиями и начальными значениями, инициализация матрицы B нулями.
* Цикл по итерациям:
```c
for (it = 1; it <= itmax; it++) {
eps = 0.0;
relax(); // Вычисление B[i][j] как среднее соседей из A
resid(); // Обновление A[i][j] = B[i][j], вычисление погрешности
if (eps < maxeps) break;
}
```
* Вычисление и вывод контрольной суммы

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

Для сетки размером <math>N \times N</math>:
* Каждая итерация требует <math>O(N^2)</math> операций
* Количество итераций зависит от сходимости, ограничено `itmax`
* Общая сложность: <math>O(it\_max \cdot N^2)</math>

Конкретно для каждой внутренней точки на каждой итерации:
* 4 операции чтения
* 3 сложения
* 1 деление
* 1 запись
* 1 вычитание и взятие модуля для погрешности

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

Информационный граф алгоритма состоит из четырёх групп вершин, расположенных в целочисленных узлах областей различной размерности.

[[file:information_graph.png|thumb|center|1150px|Информационный граф метода релаксации для <math>N</math> = 4 , <math>max\_it</math> = 2]]

1) Первая группа вершин (входные данные и инициализация) :

Расположена в двумерной области с координатами <math>(i, j)</math>.
Диапазоны изменения координат: <math>i ∈ [0, N−1] , j ∈ [0, N−1]</math>.

Операция:
* если <math>i = 0</math> или <math>i = N−1</math> или <math>j = 0</math> или <math>j = N−1</math> → <math>A[i][j] = 0</math> (граничные условия),
* иначе <math>A[i][j] = 1 + i + j</math> (начальное приближение внутри области).

Результат: элементы массива <math>A[i][j]</math> на итерации 0.
Все вершины этой группы являются источниками (входными данными алгоритма).
На рисунке соответствуют синим прямоугольникам слева с надписью <math>A[i][j]⁽⁰⁾</math>.

2) Вторая группа вершин (релаксация — вычисление нового слоя) :

Расположена в трёхмерной области с координатами <math>(i, j, k)</math>.

Диапазоны изменения координат:
<math>i ∈ [1, N−2] , j ∈ [1, N−2] , k ∈ [1, it\_max]</math>, где <math>k</math> — номер выполненной итерации.

Соответствующая операция:
<math>B[i][j] = (A[i−1][j] + A[i+1][j] + A[i][j−1] + A[i][j+1]) / 4.0</math>
(усреднение по четырём соседям — шаблон «крест»).

Аргументы операции:
четыре значения <math>A[⋅][⋅]</math> с предыдущего слоя (итерации <math>k−1</math>).

Результат срабатывания: элемент нового слоя <math>B[i][j]⁽ᵏ⁾</math>.
На рисунке — зелёные блоки с надписью <math>B[i][j]⁽ᵏ⁾</math>.

3) Третья группа вершин (вычисление невязки и обновление <math>A</math>) :

Расположена в той же трёхмерной области с координатами <math>(i, j, k)</math>.
Операция выполняется сразу после второй группы на той же итерации <math>k</math> :

# <math>e = |A[i][j]⁽ᵏ⁻¹⁾ − B[i][j]⁽ᵏ⁾|</math>
# <math>A[i][j]⁽ᵏ⁾ = B[i][j]⁽ᵏ⁾</math>
# <math>eps⁽ᵏ⁾ = max(eps⁽ᵏ⁾, e)</math>

Аргументы: значения <math>A[i][j]⁽ᵏ⁻¹⁾</math> из первой группы вершин и <math>B[i][j]⁽ᵏ⁾</math> из второй группы вершин.

Результат:
* обновлённое значение <math>A[i][j]⁽ᵏ⁾</math>, которое будет использовано на следующей итерации,
* вклад в глобальную норму невязки <math>eps⁽ᵏ⁾</math>.

На рисунке — жёлтые блоки с надписями вида <math>A[i][j]⁽ᵏ⁾ = B[i][j]⁽ᵏ⁾</math>.

4) Четвёртая группа вершин (условия завершения) :

Состоит из двух типов вершин скалярной размерности (координата <math>k</math>):

* Вершины сравнения <math>eps⁽ᵏ⁾ < max\_eps</math> :
** Координата <math>k ∈ [1, it\_max]</math>.
** Аргумент — накопленное на итерации <math>k</math> значение <math>eps⁽ᵏ⁾</math>.
** На рисунке — фиолетовые овалы с надписью <math>eps⁽ᵏ⁾ < max\_eps</math>.

* Вершина проверки числа итераций <math>iteration = it\_max</math> : На рисунке — красный прямоугольник справа.

Обе вершины являются стоками-условиями (управляющие вершины).
При выполнении любого из условий (YES) происходит выход из цикла (break).
При невыполнении обоих условий (NO) алгоритм переходит к следующей итерации <math>k+1</math>.

Таким образом, граф имеет ярко выраженную волновую структуру по итерациям <math>k</math>, с полным барьером синхронизации в конце каждой итерации (все элементы нового слоя должны быть вычислены перед подсчётом невязки и переходом к следующей итерации).

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

Алгоритм обладает высоким потенциалом параллелизма:
* На каждой итерации все внутренние точки могут обновляться независимо
* Высота ЯПФ: <math>O(it\_max)</math> (последовательные итерации)
* Ширина ЯПФ: <math>O(N^2)</math> (все точки могут обрабатываться параллельно на одной итерации)

В MPI-реализации:
* Сетка разбивается на горизонтальные полосы
* Каждый процесс обрабатывает свою полосу
* Необходим обмен граничными строками между соседними процессами
* Используются неблокирующие операции MPI для перекрытия вычислений и коммуникаций

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

Входные данные:
* Размер сетки <math>N</math> (целое число)
* Матрица значений <math>A</math> размером <math>N \times N</math> (вещественные числа)
* Параметры: maxeps (точность), itmax (максимальное число итераций)

Выходные данные:
* Матрица <math>A</math> с решением (вещественные числа)
* Контрольная сумма <math>S</math> (вещественное число)
* Число выполненных итераций (целое)
* Время выполнения (в параллельной версии)

Объём данных: <math>O(N^2)</math>

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

# Детерминированность: При фиксированных входных данных и последовательном выполнении результат детерминирован.
# Сходимость: Метод сходится медленно (линейно), количество итераций пропорционально <math>N^2</math> для достижения заданной точности.
# Устойчивость: Алгоритм устойчив к ошибкам округления.
# Масштабируемость: Хорошо масштабируется на параллельных системах благодаря локальности данных.
# Вычислительная мощность: Отношение числа операций к объёму данных составляет <math>O(it\_max)</math>.

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

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

В последовательной реализации:
# Используются две матрицы <math>A</math> и <math>B</math> для хранения значений на текущей и предыдущей итерациях.
# Граничные условия заданы нулевыми.
# Начальное приближение: <math>A[i][j] = 1.0 + i + j</math> для внутренних точек.
# Реализован режим вычисления максимальной погрешности для контроля сходимости.
# Контрольная сумма вычисляется по формуле, включающей веса <math>(i+1)(j+1)</math>.

Ключевые особенности:

```c
// Вычисление нового значения
B[i][j] = (A[i-1][j] + A[i+1][j] + A[i][j-1] + A[i][j+1]) / 4.0;
// Обновление и вычисление погрешности
e = fabs(A[i][j] - B[i][j]);
A[i][j] = B[i][j];
eps = Max(eps, e);
```

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

MPI-реализация включает следующие особенности:

* Разбиение данных: Сетка разбивается на горизонтальные полосы, каждая обрабатывается отдельным процессом.
* Распределение нагрузки: При неравномерном разбиении (когда <math>N</math> не кратно числу процессов) первые процессы получают на одну строку больше.
* Обмен граничными данными: Используются неблокирующие операции <math>MPI\_Isend / MPI\_Irecv</math> для перекрытия вычислений и коммуникаций.
* Вычисление погрешности: Локальные погрешности собираются с помощью <math>MPI\_Allreduce</math> для нахождения глобального максимума.
* Вычисление контрольной суммы: Частичные суммы вычисляются на каждом процессе и собираются с помощью <math>MPI\_Reduce</math>.

```c
// Обмен граничными строками
if (rank > 0) {
MPI_Irecv(localA[0], N, MPI_FLOAT, rank-1, 0, MPI_COMM_WORLD, &req[req_count++]);
MPI_Isend(localA[1], N, MPI_FLOAT, rank-1, 0, MPI_COMM_WORLD, &req[req_count++]);
}
if (rank < size-1) {
MPI_Irecv(localA[local_rows+1], N, MPI_FLOAT, rank+1, 0, MPI_COMM_WORLD, &req[req_count++]);
MPI_Isend(localA[local_rows], N, MPI_FLOAT, rank+1, 0, MPI_COMM_WORLD, &req[req_count++]);
}
```

* Оптимизация: Пропуск вычислений для граничных строк на первом и последнем процессах.
* Измерение времени: Использование <math>MPI\_Wtime</math> для точного измерения времени выполнения.

=== Результаты прогонов===

Для получения полных результатов необходимо провести серию экспериментов с различными:
# Размерами сетки ( <math>N</math> = 512, 1024, 2048, 4096 )
# Количеством процессов ( 1, 2, 3, ... , 28 )
# Параметрами точности ( <math>max\_eps</math> = 0.1e-7 )

Результаты:
* Ускорение работы с ростом числа процессов (до определённого предела)
* Увеличение времени выполнения с ростом N
* Зависимость числа итераций от точности и размера сетки
* Накладные расходы на коммуникации в MPI-версии

== Литература ==

# Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. — М.: Наука, 1978.
# Самарский А. А., Гулин А. В. Численные методы. - M.: Наука, 1989.
# Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical Recipes: The Art of Scientific Computing. — 3rd ed. — Cambridge University Press, 2007.
# Gropp W., Lusk E., Skjellum A. Using MPI: Portable Parallel Programming with the Message-Passing Interface. — 3rd ed. — MIT Press, 2014.
# Документация по MPI: https://www.mpi-forum.org/docs/

Метод релаксации матрицы

2025-12-09T01:50:47Z

Овсиенко Олеся:

{{algorithm
| name = Метод релаксации для уравнения Лапласа
| serial_complexity = <math>O(it\_max \cdot N^2)</math>
| pf_height = <math>O(it\_max)</math>
| pf_width = <math>O(N^2)</math>
| input_data = <math>N^2</math> (матрица значений)
| output_data = <math>N^2</math> (матрица значений)
}}

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

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

Метод релаксации является одним из простейших итерационных методов решения уравнений в частных производных. В данной реализации он применяется для численного решения уравнения Лапласа на прямоугольной области с граничными условиями Дирихле. Алгоритм основан на дискретизации уравнения с использованием конечно-разностной схемы и последующем итеративном обновлении значений в узлах сетки до достижения заданной точности.

Метод широко используется в вычислительной физике для решения стационарных задач, таких как распределение потенциала, тепловое равновесие и др. Благодаря простоте реализации и естественному параллелизму (каждая точка сетки обновляется независимо на каждой итерации) алгоритм хорошо подходит для распараллеливания на многопроцессорных системах.

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

Исходная задача: решение уравнения Лапласа
<math>
\frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} = 0
</math>
в прямоугольной области <math>[0,1]\times[0,1]</math> с нулевыми граничными условиями.

Дискретизация на равномерной сетке <math>N \times N</math> с шагом <math>h = 1/(N-1)</math> приводит к системе линейных уравнений, которая решается методом Якоби:

Для каждого внутреннего узла <math>(i,j)</math> на итерации <math>k</math>:
<math>
u_{i,j}^{(k)} = \frac{u_{i-1,j}^{(k-1)} + u_{i+1,j}^{(k-1)} + u_{i,j-1}^{(k-1)} + u_{i,j+1}^{(k-1)}}{4}
</math>

Критерий остановки:
<math>
\max_{i,j} |u_{i,j}^{(k)} - u_{i,j}^{(k-1)}| < \varepsilon_{\text{max}}
</math>

Начальное приближение для внутренних точек:
<math>
u_{i,j}^{(0)} = 1 + i + j
</math>

Контрольная сумма для верификации:
<math>
S = \frac{1}{N^2} \sum_{i=0}^{N-1} \sum_{j=0}^{N-1} u_{i,j} \cdot (i+1) \cdot (j+1)
</math>

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

Вычислительное ядро алгоритма состоит из операций обновления значений во внутренних узлах сетки:
<math>
\text{new_val} = \frac{\text{left} + \text{right} + \text{top} + \text{bottom}}{4}
</math>

Для каждой внутренней точки на каждой итерации выполняется:
* 4 чтения значений соседей
* 3 операции сложения
* 1 операция деления
* 1 запись нового значения
* 1 операция вычисления погрешности (разности между старым и новым значением)

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

Алгоритм имеет итерационную структуру:

# Инициализация матрицы (граничные условия + начальное приближение)
# Для каждой итерации:
## Вычисление новых значений для всех внутренних точек (релаксация)
## Обновление матрицы
## Вычисление максимальной погрешности
## Проверка условия сходимости
# Вычисление контрольной суммы

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

* Инициализация матрицы A граничными условиями и начальными значениями, инициализация матрицы B нулями.
* Цикл по итерациям:
```c
for (it = 1; it <= itmax; it++) {
eps = 0.0;
relax(); // Вычисление B[i][j] как среднее соседей из A
resid(); // Обновление A[i][j] = B[i][j], вычисление погрешности
if (eps < maxeps) break;
}
```
* Вычисление и вывод контрольной суммы

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

Для сетки размером <math>N \times N</math>:
* Каждая итерация требует <math>O(N^2)</math> операций
* Количество итераций зависит от сходимости, ограничено `itmax`
* Общая сложность: <math>O(it\_max \cdot N^2)</math>

Конкретно для каждой внутренней точки на каждой итерации:
* 4 операции чтения
* 3 сложения
* 1 деление
* 1 запись
* 1 вычитание и взятие модуля для погрешности

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

[[file:information_graph.png|thumb|center|1150px|Информационный граф метода релаксации для <math>N</math> = 4 , <math>max\_it</math> = 2]]

1) Первая группа вершин (входные данные и инициализация) :

Расположена в двумерной области с координатами <math>(i, j)</math>.
Диапазоны изменения координат: <math>i ∈ [0, N−1] , j ∈ [0, N−1]</math>.

Операция:
* если <math>i = 0</math> или <math>i = N−1</math> или <math>j = 0</math> или <math>j = N−1</math> → <math>A[i][j] = 0</math> (граничные условия),
* иначе <math>A[i][j] = 1 + i + j</math> (начальное приближение внутри области).

Результат: элементы массива <math>A[i][j]</math> на итерации 0.
Все вершины этой группы являются источниками (входными данными алгоритма).
На рисунке соответствуют синим прямоугольникам слева с надписью <math>A[i][j]⁽⁰⁾</math>.

2) Вторая группа вершин (релаксация — вычисление нового слоя) :

Расположена в трёхмерной области с координатами <math>(i, j, k)</math>.

Диапазоны изменения координат:
<math>i ∈ [1, N−2] , j ∈ [1, N−2] , k ∈ [1, it\_max]</math>, где <math>k</math> — номер выполненной итерации.

Соответствующая операция:
<math>B[i][j] = (A[i−1][j] + A[i+1][j] + A[i][j−1] + A[i][j+1]) / 4.0</math>
(усреднение по четырём соседям — шаблон «крест»).

Аргументы операции:
четыре значения <math>A[⋅][⋅]</math> с предыдущего слоя (итерации <math>k−1</math>).

Результат срабатывания: элемент нового слоя <math>B[i][j]⁽ᵏ⁾</math>.
На рисунке — зелёные блоки с надписью <math>B[i][j]⁽ᵏ⁾</math>.

3) Третья группа вершин (вычисление невязки и обновление <math>A</math>) :

Расположена в той же трёхмерной области с координатами <math>(i, j, k)</math>.
Операция выполняется сразу после второй группы на той же итерации <math>k</math> :

# <math>e = |A[i][j]⁽ᵏ⁻¹⁾ − B[i][j]⁽ᵏ⁾|</math>
# <math>A[i][j]⁽ᵏ⁾ = B[i][j]⁽ᵏ⁾</math>
# <math>eps⁽ᵏ⁾ = max(eps⁽ᵏ⁾, e)</math>

Аргументы: значения <math>A[i][j]⁽ᵏ⁻¹⁾</math> из первой группы вершин и <math>B[i][j]⁽ᵏ⁾</math> из второй группы вершин.

Результат:
* обновлённое значение <math>A[i][j]⁽ᵏ⁾</math>, которое будет использовано на следующей итерации,
* вклад в глобальную норму невязки <math>eps⁽ᵏ⁾</math>.

На рисунке — жёлтые блоки с надписями вида <math>A[i][j]⁽ᵏ⁾ = B[i][j]⁽ᵏ⁾</math>.

4) Четвёртая группа вершин (условия завершения) :

Состоит из двух типов вершин скалярной размерности (координата <math>k</math>):

* Вершины сравнения <math>eps⁽ᵏ⁾ < max\_eps</math> :
** Координата <math>k ∈ [1, it\_max]</math>.
** Аргумент — накопленное на итерации <math>k</math> значение <math>eps⁽ᵏ⁾</math>.
** На рисунке — фиолетовые овалы с надписью <math>eps⁽ᵏ⁾ < max\_eps</math>.

* Вершина проверки числа итераций <math>iteration = it\_max</math> : На рисунке — красный прямоугольник справа.

Обе вершины являются стоками-условиями (управляющие вершины).
При выполнении любого из условий (YES) происходит выход из цикла (break).
При невыполнении обоих условий (NO) алгоритм переходит к следующей итерации <math>k+1</math>.

Таким образом, граф имеет ярко выраженную волновую структуру по итерациям <math>k</math>, с полным барьером синхронизации в конце каждой итерации (все элементы нового слоя должны быть вычислены перед подсчётом невязки и переходом к следующей итерации).

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

Алгоритм обладает высоким потенциалом параллелизма:
* На каждой итерации все внутренние точки могут обновляться независимо
* Высота ЯПФ: <math>O(it\_max)</math> (последовательные итерации)
* Ширина ЯПФ: <math>O(N^2)</math> (все точки могут обрабатываться параллельно на одной итерации)

В MPI-реализации:
* Сетка разбивается на горизонтальные полосы
* Каждый процесс обрабатывает свою полосу
* Необходим обмен граничными строками между соседними процессами
* Используются неблокирующие операции MPI для перекрытия вычислений и коммуникаций

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

Входные данные:
* Размер сетки <math>N</math> (целое число)
* Матрица значений <math>A</math> размером <math>N \times N</math> (вещественные числа)
* Параметры: maxeps (точность), itmax (максимальное число итераций)

Выходные данные:
* Матрица <math>A</math> с решением (вещественные числа)
* Контрольная сумма <math>S</math> (вещественное число)
* Число выполненных итераций (целое)
* Время выполнения (в параллельной версии)

Объём данных: <math>O(N^2)</math>

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

# Детерминированность: При фиксированных входных данных и последовательном выполнении результат детерминирован.
# Сходимость: Метод сходится медленно (линейно), количество итераций пропорционально <math>N^2</math> для достижения заданной точности.
# Устойчивость: Алгоритм устойчив к ошибкам округления.
# Масштабируемость: Хорошо масштабируется на параллельных системах благодаря локальности данных.
# Вычислительная мощность: Отношение числа операций к объёму данных составляет <math>O(it\_max)</math>.

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

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

В последовательной реализации:
# Используются две матрицы <math>A</math> и <math>B</math> для хранения значений на текущей и предыдущей итерациях.
# Граничные условия заданы нулевыми.
# Начальное приближение: <math>A[i][j] = 1.0 + i + j</math> для внутренних точек.
# Реализован режим вычисления максимальной погрешности для контроля сходимости.
# Контрольная сумма вычисляется по формуле, включающей веса <math>(i+1)(j+1)</math>.

Ключевые особенности:

```c
// Вычисление нового значения
B[i][j] = (A[i-1][j] + A[i+1][j] + A[i][j-1] + A[i][j+1]) / 4.0;
// Обновление и вычисление погрешности
e = fabs(A[i][j] - B[i][j]);
A[i][j] = B[i][j];
eps = Max(eps, e);
```

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

MPI-реализация включает следующие особенности:

* Разбиение данных: Сетка разбивается на горизонтальные полосы, каждая обрабатывается отдельным процессом.
* Распределение нагрузки: При неравномерном разбиении (когда <math>N</math> не кратно числу процессов) первые процессы получают на одну строку больше.
* Обмен граничными данными: Используются неблокирующие операции <math>MPI\_Isend / MPI\_Irecv</math> для перекрытия вычислений и коммуникаций.
* Вычисление погрешности: Локальные погрешности собираются с помощью <math>MPI\_Allreduce</math> для нахождения глобального максимума.
* Вычисление контрольной суммы: Частичные суммы вычисляются на каждом процессе и собираются с помощью <math>MPI\_Reduce</math>.

```c
// Обмен граничными строками
if (rank > 0) {
MPI_Irecv(localA[0], N, MPI_FLOAT, rank-1, 0, MPI_COMM_WORLD, &req[req_count++]);
MPI_Isend(localA[1], N, MPI_FLOAT, rank-1, 0, MPI_COMM_WORLD, &req[req_count++]);
}
if (rank < size-1) {
MPI_Irecv(localA[local_rows+1], N, MPI_FLOAT, rank+1, 0, MPI_COMM_WORLD, &req[req_count++]);
MPI_Isend(localA[local_rows], N, MPI_FLOAT, rank+1, 0, MPI_COMM_WORLD, &req[req_count++]);
}
```

* Оптимизация: Пропуск вычислений для граничных строк на первом и последнем процессах.
* Измерение времени: Использование <math>MPI\_Wtime</math> для точного измерения времени выполнения.

=== Результаты прогонов===

Для получения полных результатов необходимо провести серию экспериментов с различными:
# Размерами сетки ( <math>N</math> = 512, 1024, 2048, 4096 )
# Количеством процессов ( 1, 2, 3, ... , 28 )
# Параметрами точности ( <math>max\_eps</math> = 0.1e-7 )

Результаты:
* Ускорение работы с ростом числа процессов (до определённого предела)
* Увеличение времени выполнения с ростом N
* Зависимость числа итераций от точности и размера сетки
* Накладные расходы на коммуникации в MPI-версии

== Литература ==

# Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. — М.: Наука, 1978.
# Самарский А. А., Гулин А. В. Численные методы. - M.: Наука, 1989.
# Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical Recipes: The Art of Scientific Computing. — 3rd ed. — Cambridge University Press, 2007.
# Gropp W., Lusk E., Skjellum A. Using MPI: Portable Parallel Programming with the Message-Passing Interface. — 3rd ed. — MIT Press, 2014.
# Документация по MPI: https://www.mpi-forum.org/docs/

Метод релаксации матрицы

2025-12-09T00:37:13Z

Овсиенко Олеся:

{{algorithm
| name = Метод релаксации для уравнения Лапласа
| serial_complexity = <math>O(it\_max \cdot N^2)</math>
| pf_height = <math>O(it\_max)</math>
| pf_width = <math>O(N^2)</math>
| input_data = <math>N^2</math> (матрица значений)
| output_data = <math>N^2</math> (матрица значений)
}}

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

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

Метод релаксации является одним из простейших итерационных методов решения уравнений в частных производных. В данной реализации он применяется для численного решения уравнения Лапласа на прямоугольной области с граничными условиями Дирихле. Алгоритм основан на дискретизации уравнения с использованием конечно-разностной схемы и последующем итеративном обновлении значений в узлах сетки до достижения заданной точности.

Метод широко используется в вычислительной физике для решения стационарных задач, таких как распределение потенциала, тепловое равновесие и др. Благодаря простоте реализации и естественному параллелизму (каждая точка сетки обновляется независимо на каждой итерации) алгоритм хорошо подходит для распараллеливания на многопроцессорных системах.

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

Исходная задача: решение уравнения Лапласа
<math>
\frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} = 0
</math>
в прямоугольной области <math>[0,1]\times[0,1]</math> с нулевыми граничными условиями.

Дискретизация на равномерной сетке <math>N \times N</math> с шагом <math>h = 1/(N-1)</math> приводит к системе линейных уравнений, которая решается методом Якоби:

Для каждого внутреннего узла <math>(i,j)</math> на итерации <math>k</math>:
<math>
u_{i,j}^{(k)} = \frac{u_{i-1,j}^{(k-1)} + u_{i+1,j}^{(k-1)} + u_{i,j-1}^{(k-1)} + u_{i,j+1}^{(k-1)}}{4}
</math>

Критерий остановки:
<math>
\max_{i,j} |u_{i,j}^{(k)} - u_{i,j}^{(k-1)}| < \varepsilon_{\text{max}}
</math>

Начальное приближение для внутренних точек:
<math>
u_{i,j}^{(0)} = 1 + i + j
</math>

Контрольная сумма для верификации:
<math>
S = \frac{1}{N^2} \sum_{i=0}^{N-1} \sum_{j=0}^{N-1} u_{i,j} \cdot (i+1) \cdot (j+1)
</math>

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

Вычислительное ядро алгоритма состоит из операций обновления значений во внутренних узлах сетки:
<math>
\text{new_val} = \frac{\text{left} + \text{right} + \text{top} + \text{bottom}}{4}
</math>

Для каждой внутренней точки на каждой итерации выполняется:
* 4 чтения значений соседей
* 3 операции сложения
* 1 операция деления
* 1 запись нового значения
* 1 операция вычисления погрешности (разности между старым и новым значением)

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

Алгоритм имеет итерационную структуру:

# Инициализация матрицы (граничные условия + начальное приближение)
# Для каждой итерации:
## Вычисление новых значений для всех внутренних точек (релаксация)
## Обновление матрицы
## Вычисление максимальной погрешности
## Проверка условия сходимости
# Вычисление контрольной суммы

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

* Инициализация матрицы A граничными условиями и начальными значениями, инициализация матрицы B нулями.
* Цикл по итерациям:
```c
for (it = 1; it <= itmax; it++) {
eps = 0.0;
relax(); // Вычисление B[i][j] как среднее соседей из A
resid(); // Обновление A[i][j] = B[i][j], вычисление погрешности
if (eps < maxeps) break;
}
```
* Вычисление и вывод контрольной суммы

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

Для сетки размером <math>N \times N</math>:
* Каждая итерация требует <math>O(N^2)</math> операций
* Количество итераций зависит от сходимости, ограничено `itmax`
* Общая сложность: <math>O(it\_max \cdot N^2)</math>

Конкретно для каждой внутренней точки на каждой итерации:
* 4 операции чтения
* 3 сложения
* 1 деление
* 1 запись
* 1 вычитание и взятие модуля для погрешности

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

Граф алгоритма представляет собой регулярную структуру:

[[file:information_graph.png|thumb|center|970px|Информационный граф метода релаксации для <math>N</math> = 4 , <math>max\_it</math> = 2]]

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

Алгоритм обладает высоким потенциалом параллелизма:
* На каждой итерации все внутренние точки могут обновляться независимо
* Высота ЯПФ: <math>O(it\_max)</math> (последовательные итерации)
* Ширина ЯПФ: <math>O(N^2)</math> (все точки могут обрабатываться параллельно на одной итерации)

В MPI-реализации:
* Сетка разбивается на горизонтальные полосы
* Каждый процесс обрабатывает свою полосу
* Необходим обмен граничными строками между соседними процессами
* Используются неблокирующие операции MPI для перекрытия вычислений и коммуникаций

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

Входные данные:
* Размер сетки <math>N</math> (целое число)
* Матрица значений <math>A</math> размером <math>N \times N</math> (вещественные числа)
* Параметры: maxeps (точность), itmax (максимальное число итераций)

Выходные данные:
* Матрица <math>A</math> с решением (вещественные числа)
* Контрольная сумма <math>S</math> (вещественное число)
* Число выполненных итераций (целое)
* Время выполнения (в параллельной версии)

Объём данных: <math>O(N^2)</math>

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

# Детерминированность: При фиксированных входных данных и последовательном выполнении результат детерминирован.
# Сходимость: Метод сходится медленно (линейно), количество итераций пропорционально <math>N^2</math> для достижения заданной точности.
# Устойчивость: Алгоритм устойчив к ошибкам округления.
# Масштабируемость: Хорошо масштабируется на параллельных системах благодаря локальности данных.
# Вычислительная мощность: Отношение числа операций к объёму данных составляет <math>O(it\_max)</math>.

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

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

В последовательной реализации:
# Используются две матрицы <math>A</math> и <math>B</math> для хранения значений на текущей и предыдущей итерациях.
# Граничные условия заданы нулевыми.
# Начальное приближение: <math>A[i][j] = 1.0 + i + j</math> для внутренних точек.
# Реализован режим вычисления максимальной погрешности для контроля сходимости.
# Контрольная сумма вычисляется по формуле, включающей веса <math>(i+1)(j+1)</math>.

Ключевые особенности:

```c
// Вычисление нового значения
B[i][j] = (A[i-1][j] + A[i+1][j] + A[i][j-1] + A[i][j+1]) / 4.0;
// Обновление и вычисление погрешности
e = fabs(A[i][j] - B[i][j]);
A[i][j] = B[i][j];
eps = Max(eps, e);
```

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

MPI-реализация включает следующие особенности:

* Разбиение данных: Сетка разбивается на горизонтальные полосы, каждая обрабатывается отдельным процессом.
* Распределение нагрузки: При неравномерном разбиении (когда <math>N</math> не кратно числу процессов) первые процессы получают на одну строку больше.
* Обмен граничными данными: Используются неблокирующие операции <math>MPI\_Isend / MPI\_Irecv</math> для перекрытия вычислений и коммуникаций.
* Вычисление погрешности: Локальные погрешности собираются с помощью <math>MPI\_Allreduce</math> для нахождения глобального максимума.
* Вычисление контрольной суммы: Частичные суммы вычисляются на каждом процессе и собираются с помощью <math>MPI\_Reduce</math>.

```c
// Обмен граничными строками
if (rank > 0) {
MPI_Irecv(localA[0], N, MPI_FLOAT, rank-1, 0, MPI_COMM_WORLD, &req[req_count++]);
MPI_Isend(localA[1], N, MPI_FLOAT, rank-1, 0, MPI_COMM_WORLD, &req[req_count++]);
}
if (rank < size-1) {
MPI_Irecv(localA[local_rows+1], N, MPI_FLOAT, rank+1, 0, MPI_COMM_WORLD, &req[req_count++]);
MPI_Isend(localA[local_rows], N, MPI_FLOAT, rank+1, 0, MPI_COMM_WORLD, &req[req_count++]);
}
```

* Оптимизация: Пропуск вычислений для граничных строк на первом и последнем процессах.
* Измерение времени: Использование <math>MPI\_Wtime</math> для точного измерения времени выполнения.

=== Результаты прогонов===

Для получения полных результатов необходимо провести серию экспериментов с различными:
# Размерами сетки ( <math>N</math> = 512, 1024, 2048, 4096 )
# Количеством процессов ( 1, 2, 3, ... , 28 )
# Параметрами точности ( <math>maxeps</math> = 0.1e-7 )

Результаты:
* Ускорение работы с ростом числа процессов (до определённого предела)
* Увеличение времени выполнения с ростом N
* Зависимость числа итераций от точности и размера сетки
* Накладные расходы на коммуникации в MPI-версии

== Литература ==

1. Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. — М.: Наука, 1978.

2. Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical Recipes: The Art of Scientific Computing. — 3rd ed. — Cambridge University Press, 2007.

3. Gropp W., Lusk E., Skjellum A. Using MPI: Portable Parallel Programming with the Message-Passing Interface. — 3rd ed. — MIT Press, 2014.

4. Документация по MPI: https://www.mpi-forum.org/docs/

Метод релаксации матрицы

2025-12-09T00:31:09Z

Овсиенко Олеся:

{{algorithm
| name = Метод релаксации для уравнения Лапласа
| serial_complexity = <math>O(it\_max \cdot N^2)</math>
| pf_height = <math>O(it\_max)</math>
| pf_width = <math>O(N^2)</math>
| input_data = <math>N^2</math> (матрица значений)
| output_data = <math>N^2</math> (матрица значений)
}}

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

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

Метод релаксации является одним из простейших итерационных методов решения уравнений в частных производных. В данной реализации он применяется для численного решения уравнения Лапласа на прямоугольной области с граничными условиями Дирихле. Алгоритм основан на дискретизации уравнения с использованием конечно-разностной схемы и последующем итеративном обновлении значений в узлах сетки до достижения заданной точности.

Метод широко используется в вычислительной физике для решения стационарных задач, таких как распределение потенциала, тепловое равновесие и др. Благодаря простоте реализации и естественному параллелизму (каждая точка сетки обновляется независимо на каждой итерации) алгоритм хорошо подходит для распараллеливания на многопроцессорных системах.

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

Исходная задача: решение уравнения Лапласа
<math>
\frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} = 0
</math>
в прямоугольной области <math>[0,1]\times[0,1]</math> с нулевыми граничными условиями.

Дискретизация на равномерной сетке <math>N \times N</math> с шагом <math>h = 1/(N-1)</math> приводит к системе линейных уравнений, которая решается методом Якоби:

Для каждого внутреннего узла <math>(i,j)</math> на итерации <math>k</math>:
<math>
u_{i,j}^{(k)} = \frac{u_{i-1,j}^{(k-1)} + u_{i+1,j}^{(k-1)} + u_{i,j-1}^{(k-1)} + u_{i,j+1}^{(k-1)}}{4}
</math>

Критерий остановки:
<math>
\max_{i,j} |u_{i,j}^{(k)} - u_{i,j}^{(k-1)}| < \varepsilon_{\text{max}}
</math>

Начальное приближение для внутренних точек:
<math>
u_{i,j}^{(0)} = 1 + i + j
</math>

Контрольная сумма для верификации:
<math>
S = \frac{1}{N^2} \sum_{i=0}^{N-1} \sum_{j=0}^{N-1} u_{i,j} \cdot (i+1) \cdot (j+1)
</math>

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

Вычислительное ядро алгоритма состоит из операций обновления значений во внутренних узлах сетки:
<math>
\text{new_val} = \frac{\text{left} + \text{right} + \text{top} + \text{bottom}}{4}
</math>

Для каждой внутренней точки на каждой итерации выполняется:
* 4 чтения значений соседей
* 3 операции сложения
* 1 операция деления
* 1 запись нового значения
* 1 операция вычисления погрешности (разности между старым и новым значением)

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

Алгоритм имеет итерационную структуру:

# Инициализация матрицы (граничные условия + начальное приближение)
# Для каждой итерации:
## Вычисление новых значений для всех внутренних точек (релаксация)
## Обновление матрицы
## Вычисление максимальной погрешности
## Проверка условия сходимости
# Вычисление контрольной суммы

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

* Инициализация матрицы A граничными условиями и начальными значениями, инициализация матрицы B нулями.
* Цикл по итерациям:
```c
for (it = 1; it <= itmax; it++) {
eps = 0.0;
relax(); // Вычисление B[i][j] как среднее соседей из A
resid(); // Обновление A[i][j] = B[i][j], вычисление погрешности
if (eps < maxeps) break;
}
```
* Вычисление и вывод контрольной суммы

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

Для сетки размером <math>N \times N</math>:
* Каждая итерация требует <math>O(N^2)</math> операций
* Количество итераций зависит от сходимости, ограничено `itmax`
* Общая сложность: <math>O(it\_max \cdot N^2)</math>

Конкретно для каждой внутренней точки на каждой итерации:
* 4 операции чтения
* 3 сложения
* 1 деление
* 1 запись
* 1 вычитание и взятие модуля для погрешности

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

Граф алгоритма представляет собой регулярную структуру:

<gallery>
File:information_graph.png|Информационный граф метода релаксации для <math>N</math> = 4, <math>max\_it</math> = 2
</gallery>

[[Файл:information_graph.png|Информационный граф метода релаксации для <math>N</math> = 4, <math>max\_it</math> = 2]]

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

Алгоритм обладает высоким потенциалом параллелизма:
* На каждой итерации все внутренние точки могут обновляться независимо
* Высота ЯПФ: <math>O(it\_max)</math> (последовательные итерации)
* Ширина ЯПФ: <math>O(N^2)</math> (все точки могут обрабатываться параллельно на одной итерации)

В MPI-реализации:
* Сетка разбивается на горизонтальные полосы
* Каждый процесс обрабатывает свою полосу
* Необходим обмен граничными строками между соседними процессами
* Используются неблокирующие операции MPI для перекрытия вычислений и коммуникаций

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

Входные данные:
* Размер сетки <math>N</math> (целое число)
* Матрица значений <math>A</math> размером <math>N \times N</math> (вещественные числа)
* Параметры: maxeps (точность), itmax (максимальное число итераций)

Выходные данные:
* Матрица <math>A</math> с решением (вещественные числа)
* Контрольная сумма <math>S</math> (вещественное число)
* Число выполненных итераций (целое)
* Время выполнения (в параллельной версии)

Объём данных: <math>O(N^2)</math>

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

# Детерминированность: При фиксированных входных данных и последовательном выполнении результат детерминирован.
# Сходимость: Метод сходится медленно (линейно), количество итераций пропорционально <math>N^2</math> для достижения заданной точности.
# Устойчивость: Алгоритм устойчив к ошибкам округления.
# Масштабируемость: Хорошо масштабируется на параллельных системах благодаря локальности данных.
# Вычислительная мощность: Отношение числа операций к объёму данных составляет <math>O(it\_max)</math>.

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

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

В последовательной реализации:
# Используются две матрицы <math>A</math> и <math>B</math> для хранения значений на текущей и предыдущей итерациях.
# Граничные условия заданы нулевыми.
# Начальное приближение: <math>A[i][j] = 1.0 + i + j</math> для внутренних точек.
# Реализован режим вычисления максимальной погрешности для контроля сходимости.
# Контрольная сумма вычисляется по формуле, включающей веса <math>(i+1)(j+1)</math>.

Ключевые особенности:

```c
// Вычисление нового значения
B[i][j] = (A[i-1][j] + A[i+1][j] + A[i][j-1] + A[i][j+1]) / 4.0;
// Обновление и вычисление погрешности
e = fabs(A[i][j] - B[i][j]);
A[i][j] = B[i][j];
eps = Max(eps, e);
```

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

MPI-реализация включает следующие особенности:

* Разбиение данных: Сетка разбивается на горизонтальные полосы, каждая обрабатывается отдельным процессом.
* Распределение нагрузки: При неравномерном разбиении (когда <math>N</math> не кратно числу процессов) первые процессы получают на одну строку больше.
* Обмен граничными данными: Используются неблокирующие операции <math>MPI\_Isend / MPI\_Irecv</math> для перекрытия вычислений и коммуникаций.
* Вычисление погрешности: Локальные погрешности собираются с помощью <math>MPI\_Allreduce</math> для нахождения глобального максимума.
* Вычисление контрольной суммы: Частичные суммы вычисляются на каждом процессе и собираются с помощью <math>MPI\_Reduce</math>.

```c
// Обмен граничными строками
if (rank > 0) {
MPI_Irecv(localA[0], N, MPI_FLOAT, rank-1, 0, MPI_COMM_WORLD, &req[req_count++]);
MPI_Isend(localA[1], N, MPI_FLOAT, rank-1, 0, MPI_COMM_WORLD, &req[req_count++]);
}
if (rank < size-1) {
MPI_Irecv(localA[local_rows+1], N, MPI_FLOAT, rank+1, 0, MPI_COMM_WORLD, &req[req_count++]);
MPI_Isend(localA[local_rows], N, MPI_FLOAT, rank+1, 0, MPI_COMM_WORLD, &req[req_count++]);
}
```

* Оптимизация: Пропуск вычислений для граничных строк на первом и последнем процессах.
* Измерение времени: Использование <math>MPI\_Wtime</math> для точного измерения времени выполнения.

=== Результаты прогонов===

Для получения полных результатов необходимо провести серию экспериментов с различными:
# Размерами сетки ( <math>N</math> = 512, 1024, 2048, 4096 )
# Количеством процессов ( 1, 2, 3, ... , 28 )
# Параметрами точности ( <math>maxeps</math> = 0.1e-7 )

Результаты:
* Ускорение работы с ростом числа процессов (до определённого предела)
* Увеличение времени выполнения с ростом N
* Зависимость числа итераций от точности и размера сетки
* Накладные расходы на коммуникации в MPI-версии

== Литература ==

1. Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. — М.: Наука, 1978.

2. Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical Recipes: The Art of Scientific Computing. — 3rd ed. — Cambridge University Press, 2007.

3. Gropp W., Lusk E., Skjellum A. Using MPI: Portable Parallel Programming with the Message-Passing Interface. — 3rd ed. — MIT Press, 2014.

4. Документация по MPI: https://www.mpi-forum.org/docs/

Метод релаксации матрицы

2025-12-09T00:18:34Z

Овсиенко Олеся:

Файл:Information graph.png

2025-12-09T00:16:05Z

Овсиенко Олеся:

Метод релаксации матрицы

2025-11-05T10:08:30Z

Овсиенко Олеся: Новая страница: «''417 группа, ММП ВМК МГУ''<br> ''Овсиенко Олеся Павловна''<br> == Математическая постановка мето...»

''417 группа, ММП ВМК МГУ''<br>
''Овсиенко Олеся Павловна''<br>

== Математическая постановка метода релаксации матрицы ==

Требуется численно решить краевую задачу для уравнения Лапласа на прямоугольной области:

<math>
\frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} = 0, \quad (x,y) \in \Omega = [0,1] \times [0,1]
</math>

с граничными условиями Дирихле:

<math>
u(x,y) = g(x,y), \quad (x,y) \in \partial\Omega,
</math>

где <math>\partial\Omega</math> — граница области.

==== Дискретизация задачи ====

Вводится равномерная сетка с шагом <math>h = \frac{1}{N-1}</math>:

<math>
x_i = i \cdot h, \quad y_j = j \cdot h, \quad i,j = 0, 1, \dots, N-1.
</math>

Аппроксимируя вторые производные конечными разностями, получаем дискретный аналог уравнения Лапласа для внутренних узлов сетки:

<math>
\frac{u_{i-1,j} - 2u_{i,j} + u_{i+1,j}}{h^2} + \frac{u_{i,j-1} - 2u_{i,j} + u_{i,j+1}}{h^2} = 0,
</math>

что после преобразования даёт:

<math>
u_{i,j} = \frac{u_{i-1,j} + u_{i+1,j} + u_{i,j-1} + u_{i,j+1}}{4}.
</math>

==== Итерационный метод решения ====

Для решения полученной системы линейных уравнений используется метод Якоби (релаксации). На каждой итерации <math>k</math> новые значения вычисляются как:

<math>
u_{i,j}^{(k)} = \frac{u_{i-1,j}^{(k-1)} + u_{i+1,j}^{(k-1)} + u_{i,j-1}^{(k-1)} + u_{i,j+1}^{(k-1)}}{4},
</math>

где <math>i,j = 1, 2, \dots, N-2</math> — индексы внутренних узлов.

==== Критерий остановки ====

Итерационный процесс прекращается, когда максимальное изменение между итерациями становится меньше заданной точности:

<math>
\max_{i,j} |u_{i,j}^{(k)} - u_{i,j}^{(k-1)}| < \varepsilon_{\text{max}}.
</math>

==== Начальные и граничные условия ====

В конкретной реализации:
* Граничные условия: <math>u_{0,j} = u_{N-1,j} = u_{i,0} = u_{i,N-1} = 0</math>
* Начальное приближение для внутренних точек: <math>u_{i,j}^{(0)} = 1 + i + j</math>

==== Контроль корректности ====

Для верификации результата вычисляется контрольная сумма:

<math>
S = \frac{1}{N^2} \sum_{i=0}^{N-1} \sum_{j=0}^{N-1} u_{i,j} \cdot (j+1) \cdot (i+1),
</math>

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