Участник:Valeriya Shervarly/Ортогонализация Грама-Шмидта - История изменений

ASA в 11:30, 18 ноября 2016

2016-11-18T11:30:48Z

← Предыдущая версия		Версия от 11:30, 18 ноября 2016
Строка 1:		Строка 1:
	~~{{Assignment\|ASA}}~~

	Авторы описания: Шерварлы В.Г.		Авторы описания: Шерварлы В.Г.

Valeriya Shervarly в 19:01, 11 ноября 2016

2016-11-11T19:01:33Z

← Предыдущая версия		Версия от 19:01, 11 ноября 2016
Строка 91:		Строка 91:
	== Информационный граф ==		== Информационный граф ==

	~~Информацинный~~ граф алгоритма изображен на рисунке ниже. Используются следующие обозначения:		Информационный граф алгоритма изображен на рисунке ниже. Используются следующие обозначения:
	* <math>a_i, i=1, ..., n</math> - операции присваивания <math>b_i = a_i</math>		* <math>a_i, i=1, ..., n</math> - операции присваивания <math>b_i = a_i</math>
	* <math>s_{ij} = b_i - proj_{b_j}a_i</math>		* <math>s_{ij} = b_i - proj_{b_j}a_i</math>
Строка 120:		Строка 120:
	Классический алгоритм (CGS) является численно-неустойчивым из-за частой потери ортогональности, вызванной ошибками округления в процессе вычислений.		Классический алгоритм (CGS) является численно-неустойчивым из-за частой потери ортогональности, вызванной ошибками округления в процессе вычислений.

	Существует модификации алгоритма Грама-Шмидта, которые являются более ~~устойчивами~~, например, модифицированный алгоритм Грама-Шмидта (MGS), блочные и итеративные варианты CGS и MGS. MGS численно эквивалентен методу Хаусхолдера QR-разложения, примененного к матрице, полученной из исходной путем добавления к ней сверху прямоугольной матрицы из нулевых элементов.		Существует модификации алгоритма Грама-Шмидта, которые являются более устойчивыми, например, модифицированный алгоритм Грама-Шмидта (MGS), блочные и итеративные варианты CGS и MGS. MGS численно эквивалентен методу Хаусхолдера QR-разложения, примененного к матрице, полученной из исходной путем добавления к ней сверху прямоугольной матрицы из нулевых элементов.

	Как можно видеть на изображении информационного графа алгоритма, существуют вершины с большой степенью исхода. Эти вершины соответствуют (в том числе) вычислению вектора <math>b_i</math> и результат этого вычисления должен быть сообщен всем вершинам, вычисляющим <math>proj_{b_i}a_j</math> для <math>j=1,..., n</math>.		Как можно видеть на изображении информационного графа алгоритма, существуют вершины с большой степенью исхода. Эти вершины соответствуют (в том числе) вычислению вектора <math>b_i</math> и результат этого вычисления должен быть сообщен всем вершинам, вычисляющим <math>proj_{b_i}a_j</math> для <math>j=1,..., n</math>.

ASA в 10:01, 1 ноября 2016

2016-11-01T10:01:26Z

← Предыдущая версия		Версия от 10:01, 1 ноября 2016
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment\|ASA}}

	Авторы описания: Шерварлы В.Г.		Авторы описания: Шерварлы В.Г.

Valeriya Shervarly в 14:09, 31 октября 2016

2016-10-31T14:09:39Z

← Предыдущая версия		Версия от 14:09, 31 октября 2016
Строка 59:		Строка 59:
	== Схема реализации последовательного алгоритма ==		== Схема реализации последовательного алгоритма ==

	Определим входные и выходные данные (два множества векторов):		Определим входные и выходные данные (два множества векторов, n - количество векторов в множестве):

	input: a = (a[1], ..., a[n])		input: a = (a[1], ..., a[n])

Valeriya Shervarly в 14:08, 31 октября 2016

2016-10-31T14:08:07Z

← Предыдущая версия		Версия от 14:08, 31 октября 2016
Строка 1:		Строка 1:
			{{Assignment}}

	Авторы описания: Шерварлы В.Г.		Авторы описания: Шерварлы В.Г.

Строка 33:		Строка 35:

	<math>\\|b\\| = \sqrt{<b,b>}</math>		<math>\\|b\\| = \sqrt{<b,b>}</math>


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

			Вычислительным ядром алгоритма является вычисление оператора проекции <math>proj_{b}a = \frac{<a, b>}{\\|b\\|^2} * b</math>.


Строка 39:		Строка 46:
	На уровне макроструктуры будем рассматривать <math>\frac{<a, b>}{\\|b\\|^2} * b</math> как отдельную макрооперацию <math>proj_{b}a</math>.		На уровне макроструктуры будем рассматривать <math>\frac{<a, b>}{\\|b\\|^2} * b</math> как отдельную макрооперацию <math>proj_{b}a</math>.

			Таким образом, на верхнем уровне алгоритм можно описать так (на каждом шаге выполняем вычисление очередного вектора итогового множества векторов):

			'''Шаг 1''':

	== ~~Вычислительное ядро алгоритма ==~~		::<math>b_1 = a_1</math>

			'''Шаг i''' (i = 2, ..., n, где n - количество векторов):

	~~Вычислительным ядром алгоритма является вычисление макроопераций~~ <math>proj_{b}a</math>~~, определенных выше.~~		::<math>b_i = a_i - \sum^{i-1}_{k=1}{proj_{b_k}a_i}</math>


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

			Определим входные и выходные данные (два множества векторов):

	input: a = (a[1], ..., a[n])		input: a = (a[1], ..., a[n])
	output: b = (b[1], ..., b[n])		output: b = (b[1], ..., b[n])

			И далее последовательно находим каждый из векторов <math>b_i</math>, используя полученные на предыдущих итерациях цикла векторы <math>b_1, ..., b_{i-1}</math>:

	b[1] = a[1]		b[1] = a[1]
	for j = 2,...,n		for i = 2,...,n
	b[j] = a[j]		b[i] = a[i]
	for k = 1,...,j-1		Comment: во вложенном цикле вычисляем <math>b_i = a_i - \sum^{i-1}_{k=1}{proj_{b_k}a_i}</math>
	b[j] = b[j] - <a[j],b[k]>/<b[k],b[k]>*b[k]		for k = 1,...,i-1
			b[i] = b[i] - <a[i],b[k]>/<b[k],b[k]>*b[k]

ASA в 13:58, 27 октября 2016

2016-10-27T13:58:29Z

← Предыдущая версия		Версия от 13:58, 27 октября 2016
Строка 1:		Строка 1:
	~~{{Assignment}}~~

	Авторы описания: Шерварлы В.Г.		Авторы описания: Шерварлы В.Г.

Valeriya Shervarly в 22:48, 23 октября 2016

2016-10-23T22:48:20Z

← Предыдущая версия		Версия от 22:48, 23 октября 2016
Строка 1:		Строка 1:
			{{Assignment}}

			Авторы описания: Шерварлы В.Г.

	= ЧАСТЬ. Свойства и структура алгоритмов =		= ЧАСТЬ. Свойства и структура алгоритмов =
Строка 59:		Строка 61:
	== Последовательная сложность алгоритма ==		== Последовательная сложность алгоритма ==

	Последовательная сложность выражается следующими формулами		Последовательная сложность алгоритма выражается следующими формулами
	(<math>n</math> - количество векторов,		(<math>n</math> - количество векторов,
	<math>m</math> - количество компонент вектора):		<math>m</math> - количество компонент вектора):
Строка 157:		Строка 159:
	# Канатников А.Н., Крищенко А.П. "Линейная алгебра."		# Канатников А.Н., Крищенко А.П. "Линейная алгебра."
	# Å. Björck. "Numerics of Gram-Schmidt orthogonalization"		# Å. Björck. "Numerics of Gram-Schmidt orthogonalization"
			# B. Milde, M. Schneider. "Parallel Implementation of Classical Gram-Schmidt Orthogonalization on CUDA Graphics Cards"

Valeriya Shervarly в 23:42, 22 октября 2016

2016-10-22T23:42:25Z

← Предыдущая версия		Версия от 23:42, 22 октября 2016
Строка 74:		Строка 74:
	== Информационный граф ==		== Информационный граф ==

			Информацинный граф алгоритма изображен на рисунке ниже. Используются следующие обозначения:
			* <math>a_i, i=1, ..., n</math> - операции присваивания <math>b_i = a_i</math>
			* <math>s_{ij} = b_i - proj_{b_j}a_i</math>
			* <math>a_i^{(*)}</math> и <math>f_{ij}</math> отличаются от <math>a_i</math> и <math>s_{ij}</math> соответственно тем, что в этот момент завершается вычисление вектора <math>b_i</math>, являющегося и частью выходных данных, и необходимой информацией для последующего этапа. Так же в этих вершинах можно вычислять величину <math>\\|b_i\\|^2</math>, необходимую для вычисления соответствующих <math>proj_{b}a</math>.
			* Разными оттенками зеленого цвета показана ярусно-параллельная форма графа алгоритма (вершины одного яруса выделены одним цветом). Высота ЯПФ - <math>n</math>, ширина ЯПФ - <math>n</math>.

			[[Файл:CGS--infograph.png]]

	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
Строка 150:		Строка 155:

	# https://ru.wikipedia.org/wiki/Процесс_Грама_―_Шмидта		# https://ru.wikipedia.org/wiki/Процесс_Грама_―_Шмидта
	#		# Канатников А.Н., Крищенко А.П. "Линейная алгебра."
			# Å. Björck. "Numerics of Gram-Schmidt orthogonalization"

Valeriya Shervarly в 00:15, 22 октября 2016

2016-10-22T00:15:33Z

← Предыдущая версия		Версия от 00:15, 22 октября 2016
Строка 80:		Строка 80:

	Возможно параллельное вычисление всех <math>proj_{b_j}a_i, i=1,...n</math> для уже найденных <math>b_j</math> вместо вычисления каждого вектора <math>b_j</math> по очереди. Таким образом после каждой итерации будет получен один посчитанный вектор, необходимый для расчетов на следующей итерации. Однако степень распараллеливания будет падать на каждой итерации, что вместе с необходимостью синхронизации и многочисленными обменами информации может снизить эффективность распараллеливания.		Возможно параллельное вычисление всех <math>proj_{b_j}a_i, i=1,...n</math> для уже найденных <math>b_j</math> вместо вычисления каждого вектора <math>b_j</math> по очереди. Таким образом после каждой итерации будет получен один посчитанный вектор, необходимый для расчетов на следующей итерации. Однако степень распараллеливания будет падать на каждой итерации, что вместе с необходимостью синхронизации и многочисленными обменами информации может снизить эффективность распараллеливания.

			Сложность параллельного варианта равна <math>O(nm)</math>, где <math>n</math> - количество векторов, <math>m</math> - количество компонент вектора. Можно сократить эту величину до <math>O(n\log{m})</math>, если еще параллельно проводить вычисление каждой макрооперации <math>proj_{b}a</math>, однако, опять же, не стоит забывать о расходах на синхронизацию и обмен информацией.


Строка 85:		Строка 87:

	'''Входные данные:'''		'''Входные данные:'''
	N линейно независимых векторов (процесс Грама — Шмидта может применяться также к бесконечной последовательности линейно независимых векторов, а также к линейно зависимым векторам. В последнем случае вектор <math>a_j</math> получится нулевым, если он зависит от векторов <math>a_1, ..., a_{j-1}</math>, и алгоритм должен сразу отбрасывать нулевые векторы)		N линейно независимых векторов (процесс Грама — Шмидта может применяться также к бесконечной последовательности линейно независимых векторов, а также к линейно зависимым векторам. В последнем случае вектор <math>a_j</math> получится нулевым, если он зависит от векторов <math>a_1, ..., a_{j-1}</math>, и алгоритм должен сразу отбрасывать нулевые векторы). Объем входных данных: <math>mN</math>, где <math>N</math> - количество векторов, <math>m</math> - количество компонент вектора

	'''Выходные данные:'''		'''Выходные данные:'''
	N ортогональных векторов, линейная оболочка которых совпадает с линейной оболочкой входного множества векторов.		N ортогональных векторов, линейная оболочка которых совпадает с линейной оболочкой входного множества векторов, объем выходных данных: <math>mN</math>.

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

	~~== Свойства~~ алгоритма ==		Вычислительная мощность алгоритма: <math>O(n)</math>. Отношение последовательной сложности к параллельной - <math>\frac{mn^2}{mn}</math> <math>(</math>или <math>\frac{mn^2}{n\log{m}})</math>.

	Классический алгоритм (CGS) является численно-неустойчивым из-за частой потери ортогональности, вызванной ошибками округления в процессе вычислений.		Классический алгоритм (CGS) является численно-неустойчивым из-за частой потери ортогональности, вызванной ошибками округления в процессе вычислений.
Строка 97:		Строка 100:
	Существует модификации алгоритма Грама-Шмидта, которые являются более устойчивами, например, модифицированный алгоритм Грама-Шмидта (MGS), блочные и итеративные варианты CGS и MGS. MGS численно эквивалентен методу Хаусхолдера QR-разложения, примененного к матрице, полученной из исходной путем добавления к ней сверху прямоугольной матрицы из нулевых элементов.		Существует модификации алгоритма Грама-Шмидта, которые являются более устойчивами, например, модифицированный алгоритм Грама-Шмидта (MGS), блочные и итеративные варианты CGS и MGS. MGS численно эквивалентен методу Хаусхолдера QR-разложения, примененного к матрице, полученной из исходной путем добавления к ней сверху прямоугольной матрицы из нулевых элементов.

			Как можно видеть на изображении информационного графа алгоритма, существуют вершины с большой степенью исхода. Эти вершины соответствуют (в том числе) вычислению вектора <math>b_i</math> и результат этого вычисления должен быть сообщен всем вершинам, вычисляющим <math>proj_{b_i}a_j</math> для <math>j=1,..., n</math>.

	= ЧАСТЬ. Программная реализация алгоритма =		= ЧАСТЬ. Программная реализация алгоритма =
Строка 135:		Строка 138:
	GramSchmidt[{{-2, 1, 0}, {-2, 0, 1}, {-0.5, -1, 1}}]		GramSchmidt[{{-2, 1, 0}, {-2, 0, 1}, {-0.5, -1, 1}}]

	* библиотека [https://github.com/fplll/fplll fplll] ~~(функция GSO) (GNU LESSER GENERAL PUBLIC LICENSE)~~		* библиотека [https://github.com/fplll/fplll fplll]

	* [http://numerics.mathdotnet.com/ Math.NET Numerics] ~~(функция MathNet.Numerics.LinearAlgebra.Factorization.GramSchmidt<T>)~~		* [http://numerics.mathdotnet.com/ Math.NET Numerics]

	* библиотека [https://www.nag.co.uk/ NAG] ~~([http://www.nag.co.uk/numeric/Fl/manual/pdf/F05/f05aaf.pdf F05AAF])~~		* библиотека [https://www.nag.co.uk/ NAG]

	* библиотека [https://www.mcs.anl.gov/petsc/documentation/index.html PETSc] ~~(KSPGMRESClassicalGramSchmidtOrthogonalization)~~		* библиотека [https://www.mcs.anl.gov/petsc/documentation/index.html PETSc]

Valeriya Shervarly в 12:29, 21 октября 2016

2016-10-21T12:29:00Z

← Предыдущая версия		Версия от 12:29, 21 октября 2016
Строка 34:		Строка 34:
	<math>\\|b\\| = \sqrt{<b,b>}</math>		<math>\\|b\\| = \sqrt{<b,b>}</math>

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

	Вычислительным ядром алгоритма является весь алгоритм (за исключением инициализации первого вектора ортогонального базиса <math>b_1</math>).

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

	На уровне макроструктуры будем рассматривать <math>\frac{<a, b>}{\\|b\\|^2} * b</math> как отдельную макрооперацию <math>proj_{b}a</math>.		На уровне макроструктуры будем рассматривать <math>\frac{<a, b>}{\\|b\\|^2} * b</math> как отдельную макрооперацию <math>proj_{b}a</math>.


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

			Вычислительным ядром алгоритма является вычисление макроопераций <math>proj_{b}a</math>, определенных выше.


Строка 57:		Строка 59:
	== Последовательная сложность алгоритма ==		== Последовательная сложность алгоритма ==

	~~Сложность~~ алгоритма - <math>O(n^3)</math>		Последовательная сложность выражается следующими формулами
			(<math>n</math> - количество векторов,
			<math>m</math> - количество компонент вектора):

			* количество умножений: <math>\frac{3mn(n-1)}{2}</math>

			* количество делений: <math>\frac{n(n-1)}{2}</math>

			* количество сложений и вычитаний: <math>\frac{n(n-1)(2m - 1)}{2}</math>

			Общая сложность алгоритма - <math>O(mn^2)</math>


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




Строка 83:		Строка 97:
	Существует модификации алгоритма Грама-Шмидта, которые являются более устойчивами, например, модифицированный алгоритм Грама-Шмидта (MGS), блочные и итеративные варианты CGS и MGS. MGS численно эквивалентен методу Хаусхолдера QR-разложения, примененного к матрице, полученной из исходной путем добавления к ней сверху прямоугольной матрицы из нулевых элементов.		Существует модификации алгоритма Грама-Шмидта, которые являются более устойчивами, например, модифицированный алгоритм Грама-Шмидта (MGS), блочные и итеративные варианты CGS и MGS. MGS численно эквивалентен методу Хаусхолдера QR-разложения, примененного к матрице, полученной из исходной путем добавления к ней сверху прямоугольной матрицы из нулевых элементов.


	~~Алгоритм является детерминированным.~~