Участник:Nikita270a - История изменений

Nikita270a в 22:14, 17 октября 2016

2016-10-17T22:14:03Z

← Предыдущая версия		Версия от 22:14, 17 октября 2016
Строка 1:		Строка 1:
	{{algorithm		{{algorithm
	\| name = Алгоритм Ланцоша с полной переортогонализацией		\| name = Алгоритм Ланцоша с полной переортогонализацией
	\| serial_complexity = <math>O(n^2)~~</math>~~		\| serial_complexity = <math>O(n^2)+O(nk^2) </math>
	~~\| pf_height = <math>~~O(~~k)</math>~~
	~~\| pf_width = <math>O(n~~^2)</math>
	\| input_data = <math>\frac{n(n + 1)}{2}</math>		\| input_data = <math>\frac{n(n + 1)}{2}</math>
	\| output_data = <math>k(n + 1)</math>		\| output_data = <math>k(n + 1)</math>
Строка 17:		Строка 15:
	В отличие от прямых алгоритмов требует мешьше памяти и мощности, что является несомненным плюсом для больших матриц.		В отличие от прямых алгоритмов требует мешьше памяти и мощности, что является несомненным плюсом для больших матриц.

	Несмотря на свою скорость работы и экономию памяти, сначала не был популярным алгоритмом из – за недостаточной вычислительной устойчивости. В 1970 году Ojalvo и Newman показали способ сделать алгоритм достаточно устойчивым. В этой же статье алгоритм был применен к расчету инженерной конструкции с большим количеством узлов, которые подвергались динамической нагрузке.		Несмотря на свою скорость работы и экономию памяти, сначала не был популярным алгоритмом из – за недостаточной вычислительной устойчивости. В 1970 году Ojalvo и Newman [http://arc.aiaa.org/doi/abs/10.2514/3.5878?journalCode=aiaaj] показали способ сделать алгоритм достаточно устойчивым. В этой же статье алгоритм был применен к расчету инженерной конструкции с большим количеством узлов, которые подвергались динамической нагрузке.


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

	Метод осуществляет поиск трехдиагональной симметричной матрицы <math>T_k=Q_k^TAQ_k</math>. Причем собственные значения <math>T_k</math> таковы, что приближают собственные значения исходной матрицы <math>A</math>. То есть на каждом <math>k</math>-м шаге из ортонормированных векторов Ланцоша строится матрица <math>Q_k = [q_1,q_2,...,q_k]</math> и в качестве приближенных собственных значений матрицы <math>A</math> принимаются числа Ритца.		Метод осуществляет поиск трехдиагональной симметричной матрицы <math>T_k=Q_k^TAQ_k</math>. Причем собственные значения <math>T_k</math> таковы, что приближают собственные значения исходной матрицы <math>A</math>. То есть на каждом <math>k</math>-м шаге из ортонормированных векторов Ланцоша строится матрица <math>Q_k = [q_1,q_2,...,q_k]</math> и в качестве приближенных собственных значений матрицы <math>A</math> принимаются числа Ритца.

			Из-за ошибок округления вектора <math> A^{k-1}x_1 </math>, формирующие подпространство Крылова, становятся неортогональными. Чтобы решить данную прорблему, проводят переортогонализацию методом Грамма-Шмидта.

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

	В данном случае первая операция выполняет умножение симметричной матрицы <math>A</math> размерности <math>n</math>X<math>n</math> на <math>n</math>-мерный вектор <math>q</math>, вследствие чего вычислительная сложность выполнения заключается в <math>n^2</math> умножений и <math>n^2-n</math> сложений. Второе действие является процессом ортогонализации Грама-Шмидта. В последнем действии вычисляются <math>k^2n+k(n+2)</math> умножений и <math>k^2n + k(n + 1) + 2</math> операций сложения.		В данном случае первая операция выполняет умножение симметричной матрицы <math>A</math> размерности <math>n</math>X<math>n</math> на <math>n</math>-мерный вектор <math>q</math>, вследствие чего вычислительная сложность выполнения заключается в <math>n^2</math> умножений и <math>n^2-n</math> сложений. Второе действие является процессом ортогонализации Грама-Шмидта. В последнем действии вычисляются <math>k^2n+k(n+2)</math> умножений и <math>k^2n + k(n + 1) + 2</math> операций сложения.

			== Макроструктура алгоритма ==
			*1. Скалярное произведение: <math> (x,y) </math>.

			*2. Суммирование: <math> x+\alpha y </math>.


	== Схема ==		== Схема ==
Строка 62:		Строка 68:
	</math>		</math>


			==Вычислительная сложность==
			Количество операций складывается из количества операций для классического метода Ланцоша[https://books.google.ru/books?id=T8EPBwAAQBAJ&pg=PA242&lpg=PA242&dq=lanczos+algorithm+complexity&source=bl&ots=kWVnVP_uJp&sig=a-4GTEt6vRE8YhR1R6dOPwvOSIk&hl=en&sa=X&ved=0ahUKEwiQ2u3U4-LPAhWvbZoKHe0QBaw4ChDoAQg7MAY#v=onepage&q=lanczos%20algorithm%20complexity&f=false] и и количества операций для переортогонализации методом грамма-Шмидта[http://stackoverflow.com/questions/27986225/computational-complexity-of-gram-schmidt-orthogonalization-algorithm].

			Итоговая сложность составляет <math>O(n^2)+O(nk^2) </math>.

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

	[[Файл:Graph.jpg]]		[[Файл:Graph.jpg]]

			== Входные и выходные данные==
			На вход принимается сама матрица <math> A \in R^{n \times n}</math>, случайный вектор <math>b</math> (впрочем возможен вариант, при котором этот вектор генерируется случайным образом).
			Ввиду симметричности входной матрицы достаточно передать лишь ее верхнюю треугольную матрицу, что дает объем входных данных <math>\frac{n(n + 1)}{2}</math>.


			Выходными данными для <math>j</math>ой итерации являются вектор <math> Aq_j </math> и собственное число <math> \lambda </math>. Общий объем выходных данных <math>k(n+1)</math>.

			==Свойства алгоритма==
			Если <math>A</math> эрмитова матрица, то алгоритм Ланцоша и Bi-Lanczos сходятся к одинаковым трехдиагональным матрицам ритца[http://ta.twi.tudelft.nl/nw/users/vuik/papers/DUT-TWI-96-44.pdf].

			При реализации классического алгоритма Ланцоша возникает большая погрешность при округлении. Вариант с полной переортогонализацией позволяет избегать больших погрешностей, однако является более ресурсоемким. Существует промежуточный вариант с частичной переортогонализацией.

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

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

			Хотя алгоритм является итерационным, возможно распараллелить внутри каждой итерации умножение матрицы на вектор и процесс переортогонализации Грамма-Шмидта.

			Процесс умножения матриц matvec можно распараллелить несколькими способами[https://eprint.iacr.org/2011/416.pdf].



	== Библиотеки реализующие алгоритм==		== Библиотеки реализующие алгоритм==
Строка 77:		Строка 110:
	GrapLab https://turi.com/products/create/open_source.html C++		GrapLab https://turi.com/products/create/open_source.html C++

	С ~~частично~~ переортаганализацией		С частичной переортаганализацией

	LANSO/PLANSO http://web.cs.ucdavis.edu/~bai/ET/lanczos_methods/overview_PLANSO.html Fortran (уже распараллелена)		LANSO/PLANSO http://web.cs.ucdavis.edu/~bai/ET/lanczos_methods/overview_PLANSO.html Fortran (уже распараллелена)

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

			Ojalvo, I.U. and Newman, M., "Vibration modes of large structures by an automatic matrix-reduction method", AIAA J., 8 (7), 1234–1239 (1970).

Nikita270a в 23:43, 16 октября 2016

2016-10-16T23:43:40Z

← Предыдущая версия		Версия от 23:43, 16 октября 2016
Строка 49:		Строка 49:
	\begin{align}		\begin{align}
	q_1 = b/\|\|b\|\|_2, \beta_0 = 0, q_0 = 0 \\		q_1 = b/\|\|b\|\|_2, \beta_0 = 0, q_0 = 0 \\
	~~for~~ j = 1 ,...,k \\		j = 1 ,...,k \\
	q_1&=b/\|\|b\|\|,\beta_0=0,q_o=0. \\		q_1&=b/\|\|b\|\|,\beta_0=0,q_o=0. \\
	z&=Aq_j, \\		z&=Aq_j, \\

Nikita270a в 21:20, 16 октября 2016

2016-10-16T21:20:22Z

← Предыдущая версия		Версия от 21:20, 16 октября 2016
Строка 9:		Строка 9:


	Авторы: ~~Ялексейчук~~ Н.Н 616, Ястребов К.С. 609.		Авторы: Алексейчук Н.Н 616, Ястребов К.С. 609.

	== Общее описание алгоритма. ==		== Общее описание алгоритма. ==
Строка 30:		Строка 30:
	<math> K_m(v,A) = span[x_1, Ax_1, A^2x_1, ..., A^{k-1}x_1] </math>		<math> K_m(v,A) = span[x_1, Ax_1, A^2x_1, ..., A^{k-1}x_1] </math>

	В качестве входных данных для алгоритма Ланцоша подаются квадратная матрица размерности <math>n</math>X<math>n</math>: <math>A=A^T</math>; а так же вектор начального приближения <math>b</math>. Метод осуществляет поиск трехдиагональной симметричной матрицы <math>T_k=Q_k^TAQ_k</math>. Причем собственные значения <math>T_k</math> таковы, что приближают собственные значения исходной матрицы <math>A</math>. То есть на каждом <math>k</math>-м шаге из ортонормированных векторов Ланцоша строится матрица <math>Q_k = [q_1,q_2,...,q_k]</math> и в качестве приближенных собственных значений матрицы <math>A</math> принимаются числа Ритца. Пусть <math>T_k=VAV^T</math> есть спектральное разложение матрицы <math>T_k</math>, столбцы матрицы <math>Q_kV</math> рассматриваются как приближения к соответсвующим собственным векторам матрицы <math>A</math><ref>Дж. Деммель «Вычислительная линейная алгебра» (стр. 391)</ref>:		В качестве входных данных для алгоритма Ланцоша подаются квадратная матрица размерности <math>n</math>X<math>n</math>: <math>A=A^T</math>; а так же вектор начального приближения <math>b</math>.

			Метод осуществляет поиск трехдиагональной симметричной матрицы <math>T_k=Q_k^TAQ_k</math>. Причем собственные значения <math>T_k</math> таковы, что приближают собственные значения исходной матрицы <math>A</math>. То есть на каждом <math>k</math>-м шаге из ортонормированных векторов Ланцоша строится матрица <math>Q_k = [q_1,q_2,...,q_k]</math> и в качестве приближенных собственных значений матрицы <math>A</math> принимаются числа Ритца.

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

			Вычислительным ядром данного алгоритма являются следующие шаги:
			*1. <math>Aq=( \sum\nolimits_{i=^n}a_{1i}q_i, \sum\nolimits_{i=2}^na_{2i}q_i, ..., \sum\nolimits_{i=1}^na_{ni}q_i)</math>.

			*2. <math>z=z-\sum\nolimits_{i=1}^{k}(z^Tq_i)q_i.</math>

			В данном случае первая операция выполняет умножение симметричной матрицы <math>A</math> размерности <math>n</math>X<math>n</math> на <math>n</math>-мерный вектор <math>q</math>, вследствие чего вычислительная сложность выполнения заключается в <math>n^2</math> умножений и <math>n^2-n</math> сложений. Второе действие является процессом ортогонализации Грама-Шмидта. В последнем действии вычисляются <math>k^2n+k(n+2)</math> умножений и <math>k^2n + k(n + 1) + 2</math> операций сложения.

	== Схема ==		== Схема ==
Строка 55:		Строка 65:
	== Информационный граф ==		== Информационный граф ==

			[[Файл:Graph.jpg]]

	== Библиотеки реализующие алгоритм==		== Библиотеки реализующие алгоритм==

Nikita270a в 21:04, 15 октября 2016

2016-10-15T21:04:32Z

← Предыдущая версия		Версия от 21:04, 15 октября 2016
Строка 30:		Строка 30:
	<math> K_m(v,A) = span[x_1, Ax_1, A^2x_1, ..., A^{k-1}x_1] </math>		<math> K_m(v,A) = span[x_1, Ax_1, A^2x_1, ..., A^{k-1}x_1] </math>

	В качестве входных данных для алгоритма Ланцоша подаются квадратная матрица размерности <math>n</math>X<math>n</math>: <math>A=A^T</math>; а так же вектор начального приближения <math>b</math>. Метод осуществляет поиск трехдиагональной симметричной матрицы <math>T_k=Q_k^TAQ_k</math>. Причем собственные значения <math>T_k</math> таковы, что приближают собственные значения исходной матрицы <math>A</math>. То есть на каждом <math>k</math>-м шаге из ортонормированных векторов Ланцоша строится матрица <math>Q_k = [q_1,q_2,...,q_k]</math> и в качестве приближенных собственных значений матрицы <math>A</math> принимаются числа Ритца. Пусть <math>~~T<sub>k</sub>~~=VAV~~<sup>~~T~~</sup>~~</math> есть спектральное разложение матрицы <math>T_k</math>, столбцы матрицы <math>Q_kV</math> рассматриваются как приближения к соответсвующим собственным векторам матрицы <math>A</math><ref>Дж. Деммель «Вычислительная линейная алгебра» (стр. 391)</ref>:		В качестве входных данных для алгоритма Ланцоша подаются квадратная матрица размерности <math>n</math>X<math>n</math>: <math>A=A^T</math>; а так же вектор начального приближения <math>b</math>. Метод осуществляет поиск трехдиагональной симметричной матрицы <math>T_k=Q_k^TAQ_k</math>. Причем собственные значения <math>T_k</math> таковы, что приближают собственные значения исходной матрицы <math>A</math>. То есть на каждом <math>k</math>-м шаге из ортонормированных векторов Ланцоша строится матрица <math>Q_k = [q_1,q_2,...,q_k]</math> и в качестве приближенных собственных значений матрицы <math>A</math> принимаются числа Ритца. Пусть <math>T_k=VAV^T</math> есть спектральное разложение матрицы <math>T_k</math>, столбцы матрицы <math>Q_kV</math> рассматриваются как приближения к соответсвующим собственным векторам матрицы <math>A</math><ref>Дж. Деммель «Вычислительная линейная алгебра» (стр. 391)</ref>:

Nikita270a в 21:01, 15 октября 2016

2016-10-15T21:01:32Z

← Предыдущая версия		Версия от 21:01, 15 октября 2016
Строка 9:		Строка 9:


			Авторы: Ялексейчук Н.Н 616, Ястребов К.С. 609.

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

Nikita270a: Новая страница: «{{algorithm | name = Алгоритм Ланцоша с полной переортогонализацией | serial_complexity = $O(n^2)$
2016-10-15T21:00:31Z

Новая страница: «{{algorithm | name = Алгоритм Ланцоша с полной переортогонализацией | serial_complexity = <math>O(n^2)</mat…»

Новая страница
{{algorithm
| name = Алгоритм Ланцоша с полной переортогонализацией
| serial_complexity = <math>O(n^2)</math>
| pf_height = <math>O(k)</math>
| pf_width = <math>O(n^2)</math>
| input_data = <math>\frac{n(n + 1)}{2}</math>
| output_data = <math>k(n + 1)</math>
}}

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

Алгоритм Ланцоша ищет собвственные значения и собственные векторы для симетричной матрицы A вещественных чисел. Является итерацонным алгоритмом. Алгоритм Ланцоша использует степенной метод (<math> b_{k+1} = \frac{Ab_k}{||Ab_k||} </math>) для поиска наибольших собственных значений и векторов матриц.

В отличие от прямых алгоритмов требует мешьше памяти и мощности, что является несомненным плюсом для больших матриц.

Несмотря на свою скорость работы и экономию памяти, сначала не был популярным алгоритмом из – за недостаточной вычислительной устойчивости. В 1970 году Ojalvo и Newman показали способ сделать алгоритм достаточно устойчивым. В этой же статье алгоритм был применен к расчету инженерной конструкции с большим количеством узлов, которые подвергались динамической нагрузке.

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

Памятка:
Степенной метод нахождения наибольшего собственного числа матрицы можно сформулировать в предельном виде: если <math> b_0 </math> – случайный вектор, и <math> b_n+1 = Ab_n </math>, тогда для больших чисел n предел <math>x_n/||x_n|| </math> стремится к нормированному наибольшему собственному вектору.

Алгоритм Ланцоша комбинирует метод Ланцоша для нахождения крыловского подпространства и метод Релэя – Ритца.

Подпространство Крылова для степенного метода:
<math> K_m(v,A) = span[x_1, Ax_1, A^2x_1, ..., A^{k-1}x_1] </math>

В качестве входных данных для алгоритма Ланцоша подаются квадратная матрица размерности <math>n</math>X<math>n</math>: <math>A=A^T</math>; а так же вектор начального приближения <math>b</math>. Метод осуществляет поиск трехдиагональной симметричной матрицы <math>T_k=Q_k^TAQ_k</math>. Причем собственные значения <math>T_k</math> таковы, что приближают собственные значения исходной матрицы <math>A</math>. То есть на каждом <math>k</math>-м шаге из ортонормированных векторов Ланцоша строится матрица <math>Q_k = [q_1,q_2,...,q_k]</math> и в качестве приближенных собственных значений матрицы <math>A</math> принимаются числа Ритца. Пусть <math>T<sub>k</sub>=VAV<sup>T</sup></math> есть спектральное разложение матрицы <math>T_k</math>, столбцы матрицы <math>Q_kV</math> рассматриваются как приближения к соответсвующим собственным векторам матрицы <math>A</math><ref>Дж. Деммель «Вычислительная линейная алгебра» (стр. 391)</ref>:

== Схема ==
Input: A, b (random vector with unit norm)
: <math>

\begin{align}
q_1 = b/||b||_2, \beta_0 = 0, q_0 = 0 \\
for j = 1 ,...,k \\
q_1&=b/||b||,\beta_0=0,q_o=0. \\
z&=Aq_j, \\
\alpha_j&=q_j^Tz, \\
z&=z-\alpha_jq_j-\beta_{j-1}q_{j-1}, \\
\beta&=||z||,\\
q_{j+1}&=z/\beta_j, \quad j \in [1, k].

\end{align}

</math>

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

== Библиотеки реализующие алгоритм==

The IETL Project http://www.comp-phys.org/software/ietl/ C++

NAG Library http://www.nag.com/content/nag-library C, C++, Fortran, C#, MATLAB, R

ARPACK https://people.sc.fsu.edu/~jburkardt/m_src/arpack/arpack.html MATLAB

GrapLab https://turi.com/products/create/open_source.html C++

С частично переортаганализацией

LANSO/PLANSO http://web.cs.ucdavis.edu/~bai/ET/lanczos_methods/overview_PLANSO.html Fortran (уже распараллелена)