Участница:Larisayaryzheva/Решение СЛАУ методом сопряжённых градиентов - История изменений

Larisayaryzheva: /* Программная реализация алгоритма */

2025-12-06T19:55:15Z

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

← Предыдущая версия		Версия от 19:55, 6 декабря 2025
Строка 160:		Строка 160:

	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
			=== Особенности реализации последовательного алгоритма ===
			=== Возможные способы и особенности параллельной реализации алгоритма ===
			=== Результаты прогонов ===
			=== Выводы для классов архитектур ===

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

Larisayaryzheva: /* Свойства алгоритма */

2025-12-05T07:51:35Z

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

← Предыдущая версия		Версия от 07:51, 5 декабря 2025
Строка 158:		Строка 158:

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

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

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

Larisayaryzheva: /* Входные и выходные данные алгоритма */

2025-12-05T07:48:52Z

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

← Предыдущая версия		Версия от 07:48, 5 декабря 2025
Строка 152:		Строка 152:

	Выходными данными алгоритма являются приближённое решение системы <math>x_k</math>. При достижении заданной точности <math>\\|r_k\\| \le \varepsilon\\|b\\|</math> метод считается сошедшимся.		Выходными данными алгоритма являются приближённое решение системы <math>x_k</math>. При достижении заданной точности <math>\\|r_k\\| \le \varepsilon\\|b\\|</math> метод считается сошедшимся.

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

			Метод сопряжённых градиентов обладает рядом особенностей, важных при его практической реализации. Алгоритм включает регулярную последовательность операций, из которых основная вычислительная сложность приходится на вычисление матричного произведения <math> Ad_{k} </math>. Остальные операции имеют координатный параллелизм и могут эффективно вычисляться на параллельных архитектурах. Несмотря на то что последовательная сложность одной итерации составляет <math> O(n^2) </math>, большая часть вычислений хорошо векторизуется, а редукции, возникающие при подсчёте норм и скалярных произведений, имеют логарифмическую параллельную сложность.

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

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

Larisayaryzheva: /* Входные и выходные данные алгоритма */

2025-12-05T07:24:56Z

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

← Предыдущая версия		Версия от 07:24, 5 декабря 2025
Строка 149:		Строка 149:
	Входными данными метода сопряжённых градиентов являются матрица системы <math>A \in \mathbb{R}^{n \times n}</math>, вектор правой части <math>b \in \mathbb{R}^n</math> и начальное приближение решения <math>x_0</math>. Матрица <math>A</math> должна быть симметричной и положительно определённой, что гарантирует сходимость метода и корректность вычисления сопряжённых направлений. В практических задачах матрица может быть как плотной, так и разреженной. Структурные свойства <math>A</math> (диагональное преобладание, блочная структура) могут дополнительно уменьшать вычислительные затраты и повышать эффективность параллельной реализации.		Входными данными метода сопряжённых градиентов являются матрица системы <math>A \in \mathbb{R}^{n \times n}</math>, вектор правой части <math>b \in \mathbb{R}^n</math> и начальное приближение решения <math>x_0</math>. Матрица <math>A</math> должна быть симметричной и положительно определённой, что гарантирует сходимость метода и корректность вычисления сопряжённых направлений. В практических задачах матрица может быть как плотной, так и разреженной. Структурные свойства <math>A</math> (диагональное преобладание, блочная структура) могут дополнительно уменьшать вычислительные затраты и повышать эффективность параллельной реализации.

	Вектор правой части <math>b</math> и начальное приближение <math>x_0</math> являются плотными векторами размерности <math>n</math>. Начальное приближение может быть выбрано произвольно. На вход также ~~подаются параметры~~ остановки: допустимая погрешность <math>\varepsilon~~</math> и максимальное число итераций <math>k_{\max}~~</math>.		Вектор правой части <math>b</math> и начальное приближение <math>x_0</math> являются плотными векторами размерности <math>n</math>. Начальное приближение может быть выбрано произвольно. На вход также подаётся параметр остановки: допустимая погрешность <math>\varepsilon</math>.

	Выходными данными алгоритма являются приближённое решение системы <math>x_k</math>. При достижении заданной точности <math>\\|r_k\\| \le \varepsilon\\|b\\|</math> метод считается сошедшимся.		Выходными данными алгоритма являются приближённое решение системы <math>x_k</math>. При достижении заданной точности <math>\\|r_k\\| \le \varepsilon\\|b\\|</math> метод считается сошедшимся.

Larisayaryzheva: /* Входные и выходные данные алгоритма */

2025-12-05T07:23:49Z

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

← Предыдущая версия		Версия от 07:23, 5 декабря 2025
Строка 151:		Строка 151:
	Вектор правой части <math>b</math> и начальное приближение <math>x_0</math> являются плотными векторами размерности <math>n</math>. Начальное приближение может быть выбрано произвольно. На вход также подаются параметры остановки: допустимая погрешность <math>\varepsilon</math> и максимальное число итераций <math>k_{\max}</math>.		Вектор правой части <math>b</math> и начальное приближение <math>x_0</math> являются плотными векторами размерности <math>n</math>. Начальное приближение может быть выбрано произвольно. На вход также подаются параметры остановки: допустимая погрешность <math>\varepsilon</math> и максимальное число итераций <math>k_{\max}</math>.

	Выходными данными алгоритма являются приближённое решение системы <math>x_k</math>~~, последняя невязка <math>r_k = b - A x_k</math>, число выполненных итераций и значение нормы невязки в момент остановки~~. При достижении заданной точности <math>\\|r_k\\| \le \varepsilon\\|b\\|</math> метод считается сошедшимся.		Выходными данными алгоритма являются приближённое решение системы <math>x_k</math>. При достижении заданной точности <math>\\|r_k\\| \le \varepsilon\\|b\\|</math> метод считается сошедшимся.

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

Larisayaryzheva: /* Ресурс параллелизма алгоритма */

2025-12-05T07:20:43Z

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

← Предыдущая версия		Версия от 07:20, 5 декабря 2025
Строка 144:		Строка 144:

	В итоге общая параллельная сложность метода равна <math> O(k\log n) </math>, где k – число операций, а максимальный потенциальный ресурс параллелизма на одной итерации составляет <math> O(n) </math>.		В итоге общая параллельная сложность метода равна <math> O(k\log n) </math>, где k – число операций, а максимальный потенциальный ресурс параллелизма на одной итерации составляет <math> O(n) </math>.

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

			Входными данными метода сопряжённых градиентов являются матрица системы <math>A \in \mathbb{R}^{n \times n}</math>, вектор правой части <math>b \in \mathbb{R}^n</math> и начальное приближение решения <math>x_0</math>. Матрица <math>A</math> должна быть симметричной и положительно определённой, что гарантирует сходимость метода и корректность вычисления сопряжённых направлений. В практических задачах матрица может быть как плотной, так и разреженной. Структурные свойства <math>A</math> (диагональное преобладание, блочная структура) могут дополнительно уменьшать вычислительные затраты и повышать эффективность параллельной реализации.

			Вектор правой части <math>b</math> и начальное приближение <math>x_0</math> являются плотными векторами размерности <math>n</math>. Начальное приближение может быть выбрано произвольно. На вход также подаются параметры остановки: допустимая погрешность <math>\varepsilon</math> и максимальное число итераций <math>k_{\max}</math>.

			Выходными данными алгоритма являются приближённое решение системы <math>x_k</math>, последняя невязка <math>r_k = b - A x_k</math>, число выполненных итераций и значение нормы невязки в момент остановки. При достижении заданной точности <math>\\|r_k\\| \le \varepsilon\\|b\\|</math> метод считается сошедшимся.

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

Larisayaryzheva: /* Ресурс параллелизма алгоритма */

2025-12-05T07:12:35Z

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

← Предыдущая версия		Версия от 07:12, 5 декабря 2025
Строка 141:		Строка 141:
	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	Метод сопряжённых градиентов обладает параллельной структурой, так как его вычислительное ядро состоит из операций, которые могут выполняться независимо на элементах векторов или столбцах матрицы. Параллельная сложность алгоритма определяется шириной ярусов его информационного графа - множеством вершин, не имеющих зависимостей между собой. За счёт координатного параллелизма каждый компонент вектора вычисляется независимо, поэтому при размере задачи <math> n </math> в один момент времени может быть выполнено <math> O(n) </math> операций, связанных с обновлениями векторов. Наиболее трудоемкой задачей в методе сопряжённых векторов является матричное умножение <math> Ad_{k} </math>. Данная операция обладает хорошим покоординатным параллелизмом и может быть ускорена. Другим источником параллелизма являются редукции, возникающие при вычислении скалярных произведений и норм векторов. Эти операции имеют сложность <math> O(n) </math>, но их параллельное время составляет <math> O(log~~\quad~~ n) </math>. Последовательные зависимости между итерациями формируют скошенный параллелизм и не позволяют выполнять итерации независимо.		Метод сопряжённых градиентов обладает параллельной структурой, так как его вычислительное ядро состоит из операций, которые могут выполняться независимо на элементах векторов или столбцах матрицы. Параллельная сложность алгоритма определяется шириной ярусов его информационного графа - множеством вершин, не имеющих зависимостей между собой. За счёт координатного параллелизма каждый компонент вектора вычисляется независимо, поэтому при размере задачи <math> n </math> в один момент времени может быть выполнено <math> O(n) </math> операций, связанных с обновлениями векторов. Наиболее трудоемкой задачей в методе сопряжённых векторов является матричное умножение <math> Ad_{k} </math>. Данная операция обладает хорошим покоординатным параллелизмом и может быть ускорена. Другим источником параллелизма являются редукции, возникающие при вычислении скалярных произведений и норм векторов. Эти операции имеют сложность <math> O(n) </math>, но их параллельное время составляет <math> O(\log n) </math>. Последовательные зависимости между итерациями формируют скошенный параллелизм и не позволяют выполнять итерации независимо.

	В итоге общая параллельная сложность метода равна <math> O(k\~~quad~~ log ~~\quad~~ n ) </math>, где k – число операций, а максимальный потенциальный ресурс параллелизма на одной итерации составляет <math> O(n) </math>.		В итоге общая параллельная сложность метода равна <math> O(k\log n) </math>, где k – число операций, а максимальный потенциальный ресурс параллелизма на одной итерации составляет <math> O(n) </math>.

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

Larisayaryzheva: /* Ресурс параллелизма алгоритма */

2025-12-05T07:10:10Z

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

← Предыдущая версия		Версия от 07:10, 5 декабря 2025
Строка 141:		Строка 141:
	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	Метод сопряжённых градиентов обладает параллельной структурой, так как его вычислительное ядро состоит из операций, которые могут выполняться независимо на элементах векторов или столбцах матрицы. Параллельная сложность алгоритма определяется шириной ярусов его информационного графа - множеством вершин, не имеющих зависимостей между собой. За счёт координатного параллелизма каждый компонент вектора вычисляется независимо, поэтому при размере задачи <math> n </math> в один момент времени может быть выполнено <math> O(n) </math> операций, связанных с обновлениями векторов. Наиболее трудоемкой задачей в методе сопряжённых векторов является матричное умножение <math> Ad_{k} </math>. Данная операция обладает хорошим покоординатным параллелизмом и может быть ускорена. Другим источником параллелизма являются редукции, возникающие при вычислении скалярных произведений и норм векторов. Эти операции имеют сложность <math> O(n) </math>, но их параллельное время составляет <math> O(log n) </math>. Последовательные зависимости между итерациями формируют скошенный параллелизм и не позволяют выполнять итерации независимо.		Метод сопряжённых градиентов обладает параллельной структурой, так как его вычислительное ядро состоит из операций, которые могут выполняться независимо на элементах векторов или столбцах матрицы. Параллельная сложность алгоритма определяется шириной ярусов его информационного графа - множеством вершин, не имеющих зависимостей между собой. За счёт координатного параллелизма каждый компонент вектора вычисляется независимо, поэтому при размере задачи <math> n </math> в один момент времени может быть выполнено <math> O(n) </math> операций, связанных с обновлениями векторов. Наиболее трудоемкой задачей в методе сопряжённых векторов является матричное умножение <math> Ad_{k} </math>. Данная операция обладает хорошим покоординатным параллелизмом и может быть ускорена. Другим источником параллелизма являются редукции, возникающие при вычислении скалярных произведений и норм векторов. Эти операции имеют сложность <math> O(n) </math>, но их параллельное время составляет <math> O(log\quad n) </math>. Последовательные зависимости между итерациями формируют скошенный параллелизм и не позволяют выполнять итерации независимо.

	В итоге общая параллельная сложность метода равна <math> O(k ~~logn~~) </math>, где k – число операций.		В итоге общая параллельная сложность метода равна <math> O(k\quad log \quad n ) </math>, где k – число операций, а максимальный потенциальный ресурс параллелизма на одной итерации составляет <math> O(n) </math>.

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

Larisayaryzheva: /* Ресурс параллелизма алгоритма */

2025-12-05T07:06:35Z

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

← Предыдущая версия		Версия от 07:06, 5 декабря 2025
Строка 140:		Строка 140:

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

			Метод сопряжённых градиентов обладает параллельной структурой, так как его вычислительное ядро состоит из операций, которые могут выполняться независимо на элементах векторов или столбцах матрицы. Параллельная сложность алгоритма определяется шириной ярусов его информационного графа - множеством вершин, не имеющих зависимостей между собой. За счёт координатного параллелизма каждый компонент вектора вычисляется независимо, поэтому при размере задачи <math> n </math> в один момент времени может быть выполнено <math> O(n) </math> операций, связанных с обновлениями векторов. Наиболее трудоемкой задачей в методе сопряжённых векторов является матричное умножение <math> Ad_{k} </math>. Данная операция обладает хорошим покоординатным параллелизмом и может быть ускорена. Другим источником параллелизма являются редукции, возникающие при вычислении скалярных произведений и норм векторов. Эти операции имеют сложность <math> O(n) </math>, но их параллельное время составляет <math> O(log n) </math>. Последовательные зависимости между итерациями формируют скошенный параллелизм и не позволяют выполнять итерации независимо.

			В итоге общая параллельная сложность метода равна <math> O(k logn) </math>, где k – число операций.

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

Larisayaryzheva: /* Информационный граф */

2025-11-29T19:24:31Z

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

← Предыдущая версия		Версия от 19:24, 29 ноября 2025
Строка 138:		Строка 138:
	Информационный граф метода сопряжённых градиентов отражает последовательность основных макроопераций внутри одной итерации метода и зависимость данных между ними. Вершины графа соответствуют вычислению матрично-векторного произведения <math> q = Ad_k </math>, вычислению коэффициентов <math> α_k </math> и <math> β_k </math>, обновлению решения <math> x_{k+1} </math>, невязки <math> g_{k+1} </math> и направления <math> d_{k+1} </math>. Граф имеет ярусно-параллельную структуру: отдельные этапы должны выполняться последовательно, однако операции обновления векторов полностью параллелизуемы по компонентам. Итерации метода образуют цикл: после вычисления <math> d_{k+1} </math> выполняется проверка критерия остановки, и при необходимости управление возвращается к вычислению нового матричного произведения.		Информационный граф метода сопряжённых градиентов отражает последовательность основных макроопераций внутри одной итерации метода и зависимость данных между ними. Вершины графа соответствуют вычислению матрично-векторного произведения <math> q = Ad_k </math>, вычислению коэффициентов <math> α_k </math> и <math> β_k </math>, обновлению решения <math> x_{k+1} </math>, невязки <math> g_{k+1} </math> и направления <math> d_{k+1} </math>. Граф имеет ярусно-параллельную структуру: отдельные этапы должны выполняться последовательно, однако операции обновления векторов полностью параллелизуемы по компонентам. Итерации метода образуют цикл: после вычисления <math> d_{k+1} </math> выполняется проверка критерия остановки, и при необходимости управление возвращается к вычислению нового матричного произведения.
	[[Файл:Информационный граф итерации метода сопряжённых градиентов.png\|900px]]		[[Файл:Информационный граф итерации метода сопряжённых градиентов.png\|900px]]

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

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