Участник:Egor Luckjanow 403/Алгоритм Грамма-Шмидта - История изменений

Egor Luckjanow 403 в 18:03, 12 декабря 2021

2021-12-12T18:03:48Z

← Предыдущая версия		Версия от 18:03, 12 декабря 2021
Строка 65:		Строка 65:
	=== Локальность данных и вычислений ===		=== Локальность данных и вычислений ===
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	Метод Грамма-Шмидта ~~плохо приспособлен для параллельной~~ реализации. ~~Единственный способ, известный автору --~~ отдать каждому процессу по группе столбцов <math>q_i</math> для вычисления.		Метод Грамма-Шмидта не предполагает блочной реализации, в которой процессы, обрабатывающие блоки, никак не зависели бы друг от друга.
			Есть вариант отдать каждому процессу по группе столбцов <math>q_i</math> для вычисления.
	Число пересылок тогда составляет <math>n(n+1)/2</math>.		Число пересылок тогда составляет <math>n(n+1)/2</math>.
	==== Код возможной реализации ====		==== Код возможной реализации ====

Egor Luckjanow 403 в 17:58, 12 декабря 2021

2021-12-12T17:58:15Z

← Предыдущая версия		Версия от 17:58, 12 декабря 2021
Строка 51:		Строка 51:
	Сложность последовательного алгоритма -- <math>O(n^3)</math>.		Сложность последовательного алгоритма -- <math>O(n^3)</math>.
	=== Информационный граф ===		=== Информационный граф ===
			[[Файл:Информационный граффф.png\|слева\|Информационный граф]]
	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
	Параллельная сложность (в терминах операций сложения и умножения) -- <math>O(n^2)</math>.		Параллельная сложность (в терминах операций сложения и умножения) -- <math>O(n^2)</math>.
Строка 181:		Строка 182:
	</source>		</source>
	==== Результаты работы данного кода ====		==== Результаты работы данного кода ====
	[[Файл:Результаты запусков.png\|~~обрамить~~\|слева\|Результаты запусков]]		[[Файл:Результаты запусков.png\|никакой\|слева\|Результаты запусков]]

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

Egor Luckjanow 403: /* Результаты работы данного кода */

2021-12-12T17:07:28Z

Результаты работы данного кода

← Предыдущая версия		Версия от 17:07, 12 декабря 2021
Строка 181:		Строка 181:
	</source>		</source>
	==== Результаты работы данного кода ====		==== Результаты работы данного кода ====
	[[Файл:Результаты запусков\|обрамить\|слева\|Результаты запусков]]		[[Файл:Результаты запусков.png\|обрамить\|слева\|Результаты запусков]]

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

Egor Luckjanow 403: /* Результаты работы данного кода */

2021-12-12T17:06:54Z

Результаты работы данного кода

← Предыдущая версия		Версия от 17:06, 12 декабря 2021
Строка 181:		Строка 181:
	</source>		</source>
	==== Результаты работы данного кода ====		==== Результаты работы данного кода ====
	[[Файл:Результаты запусков~~.png~~\|~~мини~~]]		[[Файл:Результаты запусков\|обрамить\|слева\|Результаты запусков]]

	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	Алгоритм увеличивает время своей работы при добавлении независимых вычислительных ядер.		Алгоритм увеличивает время своей работы при добавлении независимых вычислительных ядер.

Egor Luckjanow 403 в 17:04, 12 декабря 2021

2021-12-12T17:04:57Z

← Предыдущая версия		Версия от 17:04, 12 декабря 2021
Строка 136:		Строка 136:
	if (i == j)		if (i == j)
	A[j + i * n] = rand();		A[j + i * n] = rand();
	~~//A[j + i * n] = 1;~~
	else		else
	A[j + i * n] = rand();		A[j + i * n] = rand();
	~~//A[j + i * n] = 0;~~
	int id;		int id;
	int ione = 1;		int ione = 1;
Строка 155:		Строка 153:
	for (int j = 0; j < nmon; ++j)		for (int j = 0; j < nmon; ++j)
	{		{
	~~//MPI_Recv(s + i1 * n, n, MPI_DOUBLE, i / nmon, 1, world, &status);~~
	double arg = -ddot(&n, A + (id * nmon + i1) * n, &ione, s + j * n, &ione) / ddot(&n, s + j * n, &ione, s + j * n, &ione);		double arg = -ddot(&n, A + (id * nmon + i1) * n, &ione, s + j * n, &ione) / ddot(&n, s + j * n, &ione, s + j * n, &ione);
	daxpy(&n, &arg, s + j * n, &ione, q + i1 * n, &ione);		daxpy(&n, &arg, s + j * n, &ione, q + i1 * n, &ione);
Строка 183:		Строка 180:
	}		}
	</source>		</source>
			==== Результаты работы данного кода ====
			[[Файл:Результаты запусков.png\|мини]]
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	Алгоритм увеличивает время своей работы при добавлении независимых вычислительных ядер.		Алгоритм увеличивает время своей работы при добавлении независимых вычислительных ядер.

Egor Luckjanow 403 в 16:49, 12 декабря 2021

2021-12-12T16:49:05Z

@@ Строка 66: / Строка 66: @@
 Метод Грамма-Шмидта плохо приспособлен для параллельной реализации. Единственный способ, известный автору -- отдать каждому процессу по группе столбцов <math>q_i</math> для вычисления.
 Число пересылок тогда составляет <math>n(n+1)/2</math>.
 === Масштабируемость алгоритма и его реализации ===
 Алгоритм увеличивает время своей работы при добавлении независимых вычислительных ядер.

Egor Luckjanow 403 в 10:36, 6 декабря 2021

2021-12-06T10:36:00Z

← Предыдущая версия		Версия от 10:36, 6 декабря 2021
Строка 23:		Строка 23:
	for (int i = 0; i < N; ++i) {		for (int i = 0; i < N; ++i) {
	R[i * N + i] = 1;		R[i * N + i] = 1;
	~~//int one = 1;~~
	for (int k = 1; k < i + 1; ++k) {		for (int k = 1; k < i + 1; ++k) {
	R[i - k + i * N] = ddot(&N, A + i * N, &one, Q + (i - k) * N, &one) / ddot(&N, Q + (i - k) * N, &one, Q + (i - k) * N, &one);		R[i - k + i * N] = ddot(&N, A + i * N, &one, Q + (i - k) * N, &one) / ddot(&N, Q + (i - k) * N, &one, Q + (i - k) * N, &one);
Строка 29:		Строка 28:
	for (int j = 0; j < N; ++j) {		for (int j = 0; j < N; ++j) {
	Q[j + i * N] = A[j + i * N];		Q[j + i * N] = A[j + i * N];
	~~/*for (int k = 0; k < i; ++k) {~~
	~~Q[j + i * N] -= R[i - k - 1 + i * N] * Q[j + (i - k - 1) * N];~~
	~~}*/~~
	}		}
	for (int k = 0; k < i; ++k) {		for (int k = 0; k < i; ++k) {
Строка 37:		Строка 33:
	daxpy(&N, &tmp, Q + (i - k - 1) * N, &one, Q + i * N, &one);		daxpy(&N, &tmp, Q + (i - k - 1) * N, &one, Q + i * N, &one);
	}		}
	/*
	~~double norm = dnrm2(&N, Q + i * N, &one);~~
	~~for (int j = 0; j < N; ++j) {~~
	~~Q[j + i * N] /= norm;~~
	}
	~~for (int k = 0; k < i + 1; ++k) {~~
	~~R[k + i * N] *= norm;~~
	~~}*/~~
	for (int k = i + 1; k < N; ++k) {		for (int k = i + 1; k < N; ++k) {
	R[k + i * N] = 0;		R[k + i * N] = 0;
Строка 70:		Строка 58:
	=== Свойства алгоритма ===		=== Свойства алгоритма ===
	Алгоритм Грамма-Шмидта обладает свойством потери ортогональности. Поэтому для корректной его реализации необходимо время от времени делать реортогонализацию, а также обеспечить максимально возможную точность вычислений с плавающей точкой.		Алгоритм Грамма-Шмидта обладает свойством потери ортогональности. Поэтому для корректной его реализации необходимо время от времени делать реортогонализацию, а также обеспечить максимально возможную точность вычислений с плавающей точкой.
	Можно реализовать алгоритм для работы с рациональными матрицами. Тогда проблема с потерей ортогонализации пропадает (в виду идеальной точности вычислений в ~~поле частных колец~~ вида <math>\mathbb{Z}/<m></math> на компьютере).		Можно реализовать алгоритм для работы с рациональными матрицами. Тогда проблема с потерей ортогонализации пропадает (в виду идеальной точности вычислений в кольцах вида <math>\mathbb{Z}/<m></math> на компьютере).
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	Проблема с потерей ортогональности уже описана в свойствах алгоритма.		Проблема с потерей ортогональности уже описана в свойствах алгоритма.
	~~Следует также отметить большое количество пересылок.~~
	=== Локальность данных и вычислений ===		=== Локальность данных и вычислений ===
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
Строка 80:		Строка 67:
	Число пересылок тогда составляет <math>n(n+1)/2</math>.		Число пересылок тогда составляет <math>n(n+1)/2</math>.
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	Алгоритм увеличивает ~~свою работу~~ при добавлении независимых вычислительных ядер.		Алгоритм увеличивает время своей работы при добавлении независимых вычислительных ядер.
	Алгоритм обладает сильной масштабируемостью.		Алгоритм обладает сильной масштабируемостью.
	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===

Egor Luckjanow 403 в 10:26, 6 декабря 2021

2021-12-06T10:26:10Z

← Предыдущая версия		Версия от 10:26, 6 декабря 2021
Строка 69:		Строка 69:
	Выходные данные -- матрицы <math>Q</math> и <math>R</math> из QR-разложения поданной на вход матрицы.		Выходные данные -- матрицы <math>Q</math> и <math>R</math> из QR-разложения поданной на вход матрицы.
	=== Свойства алгоритма ===		=== Свойства алгоритма ===
	Алгоритм ~~Грама~~-Шмидта обладает свойством потери ортогональности. Поэтому для корректной его реализации необходимо время от времени делать реортогонализацию, а также обеспечить максимально возможную точность вычислений с плавающей точкой.		Алгоритм Грамма-Шмидта обладает свойством потери ортогональности. Поэтому для корректной его реализации необходимо время от времени делать реортогонализацию, а также обеспечить максимально возможную точность вычислений с плавающей точкой.
	Можно реализовать алгоритм для работы с рациональными матрицами. Тогда проблема с потерей ортогонализации пропадает (в виду идеальной точности вычислений в поле частных колец вида <math>\mathbb{Z}/<m></math> на компьютере).		Можно реализовать алгоритм для работы с рациональными матрицами. Тогда проблема с потерей ортогонализации пропадает (в виду идеальной точности вычислений в поле частных колец вида <math>\mathbb{Z}/<m></math> на компьютере).
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
Строка 77:		Строка 77:
	=== Локальность данных и вычислений ===		=== Локальность данных и вычислений ===
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	Метод ~~Грама~~-Шмидта плохо приспособлен для параллельной реализации. Единственный способ, известный автору -- отдать каждому процессу по группе столбцов <math>q_i</math> для вычисления.		Метод Грамма-Шмидта плохо приспособлен для параллельной реализации. Единственный способ, известный автору -- отдать каждому процессу по группе столбцов <math>q_i</math> для вычисления.
	Число пересылок тогда составляет <math>n(n+1)/2</math>.		Число пересылок тогда составляет <math>n(n+1)/2</math>.
			=== Масштабируемость алгоритма и его реализации ===
			Алгоритм увеличивает свою работу при добавлении независимых вычислительных ядер.
			Алгоритм обладает сильной масштабируемостью.
			=== Динамические характеристики и эффективность реализации алгоритма ===
			При выборе системы для запуска предпочтение следует отдавать скорости обмена данными между процессами.
			При выборе архитектуры необходимо учесть наличие возможности вычислений с высокой точностью.
			Параллельный алгоритм не дает разительного превосходства по времени исполнения в сравнении с последовательным, но все же имеет место заметное уменьшение времени исполнения при выполнении указанных условий.
			=== Выводы для классов архитектур ===
			Реализация архитектурно независима. Зависимы только макрооперации, которые предполагаются уже реализованными.
			=== Существующие реализации алгоритма ===
			В силу потери ортогональности алгоритм Грамма-Шмидта пользуется небольшой популярностью в сравнении с альтернативными методами QR-разложения, так что популярных параллельных реализаций нет.
			Альтернативный (не Грамм-Шмидт) метод представлен, например, в пакете LAPACK и является одним из лучших по производительности.
	== Литература ==		== Литература ==
	#Е. Е. Тыртышников, Методы численного анализа		#Е. Е. Тыртышников, Методы численного анализа

Egor Luckjanow 403 в 10:11, 6 декабря 2021

2021-12-06T10:11:28Z

@@ Строка 12: / Строка 12: @@
 <math>...</math><br>
 Мы применяем этот метод к столбцам исходной матрицы A и получаем разложение A = QR, где Q составлена из столбцов q_1,...,q_n, полученных в результате применения метода Грама-Шмидта, а R -- матрица коэффициентов, которая будет верхнетреугольной в силу вида метода.
 == Литература ==
 #Е. Е. Тыртышников, Методы численного анализа

Egor Luckjanow 403: Автора добавили, ибо мерзко как-то, когда у статьи автора нету...

2021-10-26T18:37:01Z

Автора добавили, ибо мерзко как-то, когда у статьи автора нету...

← Предыдущая версия		Версия от 18:37, 26 октября 2021
Строка 1:		Строка 1:
			Автор: Егор Лукьянов, студент 403 группы ВМК МГУ
	== Свойства и структура алгоритмов ==		== Свойства и структура алгоритмов ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===