Участник:Sfedotov/Алгоритм Ланцоша с полной переортогонализацией - История изменений

ASA в 10:46, 25 ноября 2016

2016-11-25T10:46:59Z

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

	{{algorithm		{{algorithm

Sfedotov в 09:56, 24 ноября 2016

2016-11-24T09:56:03Z

← Предыдущая версия		Версия от 09:56, 24 ноября 2016
Строка 1:		Строка 1:
			{{Assignment}}

	{{algorithm		{{algorithm
	\| name = Алгоритм Ланцоша с полной переортогонализацией		\| name = Алгоритм Ланцоша с полной переортогонализацией
Строка 63:		Строка 65:
	*Найти собственные значения матрицы <math>T_j</math>		*Найти собственные значения матрицы <math>T_j</math>
	*Если <math>\beta_j=0</math> Выход		*Если <math>\beta_j=0</math> Выход
	[[file:Lanczos1.jpg\|thumb\|center\|450px\|Блок-схема алгоритма]]		[[file:Lanczos1.jpg\|thumb\|center\|450px\|'''Рисунок 1.''' Блок-схема алгоритма]]

	== Последовательная сложность алгоритма ==		== Последовательная сложность алгоритма ==
Строка 73:		Строка 75:
	Легко проверить, что ''m'' шагов этого алгоритма потребуют ''O''(''m''<sup>2</sup>''n'') флопов и ''O''(''mn'') слов памяти.		Легко проверить, что ''m'' шагов этого алгоритма потребуют ''O''(''m''<sup>2</sup>''n'') флопов и ''O''(''mn'') слов памяти.
	== Информационный граф ==		== Информационный граф ==
	[[file:Lanczos2.jpg\|thumb\|center\|300px\|Вычислительная схема ''j''-й итерации. Синим цветом помечены промежуточные данные]]		[[file:Lanczos2.jpg\|thumb\|center\|300px\|'''Рисунок 2.''' Вычислительная схема ''j''-й итерации. Синим цветом помечены промежуточные данные]]

	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
Строка 111:		Строка 113:
	{\|align="center"		{\|align="center"
	\|-valign="top"		\|-valign="top"
	\|[[file:Trlanlib_mpi1.png\|thumb\|center\|700px\|Рисунок 3: Производительность в зависимости от числа процессоров и размера матрицы.]]		\|[[file:Trlanlib_mpi1.png\|thumb\|center\|700px\|'''Рисунок 3.''' Производительность в зависимости от числа процессоров и размера матрицы.]]
	\|[[file:Trlanlib_mpi2.png\|thumb\|center\|700px\|Рисунок 4: Время выполнения в зависимости от числа процессоров и размера матрицы.]]		\|[[file:Trlanlib_mpi2.png\|thumb\|center\|700px\|'''Рисунок 4.''' Время выполнения в зависимости от числа процессоров и размера матрицы.]]
	\|}		\|}
	Можно заметить, что данная реализация немасштабируема и не дает ускорения при увеличении числа процессов. Из рисунков 3, 4 хорошо видно, что наилучшая производительность достигается с использованием только одного-двух процессов. Дальнейшее увеличение числа процессов лишь приводит к снижению эффективности. После 8-ми процессов ситуация стабилизируется и дальнейшее распараллеливание мало сказывается на результат		Можно заметить, что данная реализация немасштабируема и не дает ускорения при увеличении числа процессов. Из рисунков 3, 4 хорошо видно, что наилучшая производительность достигается с использованием только одного-двух процессов. Дальнейшее увеличение числа процессов лишь приводит к снижению эффективности. После 8-ми процессов ситуация стабилизируется и дальнейшее распараллеливание мало сказывается на результат

ASA в 12:49, 23 ноября 2016

2016-11-23T12:49:48Z

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

	{{algorithm		{{algorithm
	\| name = Алгоритм Ланцоша с полной переортогонализацией		\| name = Алгоритм Ланцоша с полной переортогонализацией

Sfedotov в 12:30, 23 ноября 2016

2016-11-23T12:30:04Z

← Предыдущая версия		Версия от 12:30, 23 ноября 2016
Строка 122:		Строка 122:
	\|		\|
	Модули:		Модули:
	mkl/11.2.0		mkl/4.0.2.146
	impi/4.1.0		impi/5.0.1-ofa
	компилятор mpif90, параметры компиляции:		компилятор mpif90, параметры компиляции:
	mpif90 -I/opt/intel/composer_xe_2013.2.146/mkl/include/ia32 -I/opt/intel/composer_xe_2013.2.146/mkl/include -O0 /opt/intel/composer_xe_2013.2.146/mkl/lib/intel64/libmkl_blas95_lp64.a /opt/intel/composer_xe_2013.2.146/mkl/lib/intel64/libmkl_lapack95_lp64.a -L/opt/intel/composer_xe_2013.2.146/mkl/lib/intel64 -lmkl_intel_lp64 -lmkl_intel_thread -lmkl_core -liomp5 -lpthread -lm -ldl simple.f90 -o simple lapack_aux.o ../../libtrlan_mpi.a		mpif90 -I/opt/intel/composer_xe_2013.2.146/mkl/include/ia32 -I/opt/intel/composer_xe_2013.2.146/mkl/include -O0 /opt/intel/composer_xe_2013.2.146/mkl/lib/intel64/libmkl_blas95_lp64.a /opt/intel/composer_xe_2013.2.146/mkl/lib/intel64/libmkl_lapack95_lp64.a -L/opt/intel/composer_xe_2013.2.146/mkl/lib/intel64 -lmkl_intel_lp64 -lmkl_intel_thread -lmkl_core -liomp5 -lpthread -lm -ldl simple.f90 -o simple lapack_aux.o ../../libtrlan_mpi.a

Sfedotov в 22:47, 21 ноября 2016

2016-11-21T22:47:21Z

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

	{{algorithm		{{algorithm
	\| name = Алгоритм Ланцоша с полной переортогонализацией		\| name = Алгоритм Ланцоша с полной переортогонализацией

Sfedotov в 22:41, 21 ноября 2016

2016-11-21T22:41:37Z

← Предыдущая версия		Версия от 22:41, 21 ноября 2016
Строка 105:		Строка 105:
	== Масштабируемость алгоритма и его реализации ==		== Масштабируемость алгоритма и его реализации ==
	Для исследования алгоритма была протестирована параллельная MPI-реализация библиотеки [http://crd-legacy.lbl.gov/~kewu/trlan.html TRLan] на языке Fortran90. Исследование проводилось на суперкомпьютере Ломоносов[http://parallel.ru/cluster/]		Для исследования алгоритма была протестирована параллельная MPI-реализация библиотеки [http://crd-legacy.lbl.gov/~kewu/trlan.html TRLan] на языке Fortran90. Исследование проводилось на суперкомпьютере Ломоносов[http://parallel.ru/cluster/]
	~~Параметры запуска~~ алгоритма:		Набор и границы значений изменяемых параметров реализации алгоритма:
	* размер матрицы от 5000 до 25000 с шагом 500.		* размер матрицы от 5000 до 25000 с шагом 500.
	* число процессоров от 8 ~~до 128~~ с шагом 8.		* число процессоров 1, 2, 4, [8:144] с шагом 8.
	~~В результате проведённых экспериментов максимальная эффективность реализации составила 9~~.~~03%, а минимальная - 0~~.~~31%.~~		Для всех запусков требовалось найти 10 минимальных собственных значений диагональной матрицы. Величины производительности и времени выполнения брались из вывода встроенной функции состояния trl_print_info. На следующих рисунках приведены графики производительности и времени выполнения данной реализации в зависимости от изменяемых параметров запуска:
	На следующих рисунках приведены графики производительности и ~~эффективности~~ данной реализации в зависимости от изменяемых параметров запуска.
	{\|align="center"		{\|align="center"
	\|-valign="top"		\|-valign="top"
	\|[[file:Trlanlib_mpi1.png\|thumb\|center\|700px\|~~График производительности~~ в зависимости от числа процессоров и размера матрицы.]]		\|[[file:Trlanlib_mpi1.png\|thumb\|center\|700px\|Рисунок 3: Производительность в зависимости от числа процессоров и размера матрицы.]]
	\|[[file:Trlanlib_mpi2.png\|thumb\|center\|700px\|~~График эффективности~~ в зависимости от числа процессоров и размера матрицы.]]		\|[[file:Trlanlib_mpi2.png\|thumb\|center\|700px\|Рисунок 4: Время выполнения в зависимости от числа процессоров и размера матрицы.]]
	\|}		\|}
			Можно заметить, что данная реализация немасштабируема и не дает ускорения при увеличении числа процессов. Из рисунков 3, 4 хорошо видно, что наилучшая производительность достигается с использованием только одного-двух процессов. Дальнейшее увеличение числа процессов лишь приводит к снижению эффективности. После 8-ми процессов ситуация стабилизируется и дальнейшее распараллеливание мало сказывается на результат
	{\| class="wikitable mw-collapsible mw-collapsed"		{\| class="wikitable mw-collapsible mw-collapsed"
	! Использованные модули и компиляторы		! Использованные модули и компиляторы
	\|-		\|-
	\|		\|
	~~module add slurm~~		Модули:
			mkl/11.2.0
	~~module add~~ impi		impi/4.1.0
			компилятор mpif90, параметры компиляции:
	~~module add mkl~~		mpif90 -I/opt/intel/composer_xe_2013.2.146/mkl/include/ia32 -I/opt/intel/composer_xe_2013.2.146/mkl/include -O0 /opt/intel/composer_xe_2013.2.146/mkl/lib/intel64/libmkl_blas95_lp64.a /opt/intel/composer_xe_2013.2.146/mkl/lib/intel64/libmkl_lapack95_lp64.a -L/opt/intel/composer_xe_2013.2.146/mkl/lib/intel64 -lmkl_intel_lp64 -lmkl_intel_thread -lmkl_core -liomp5 -lpthread -lm -ldl simple.f90 -o simple lapack_aux.o ../../libtrlan_mpi.a

	~~Для тестовой программы был использован~~ компилятор mpif90, ~~флаги~~ компиляции:
	-I~~${MKLROOT}~~/include/~~intel64/lp64~~ -I~~${MKLROOT}~~/include -O0
	~~линковки:~~
	~~${MKLROOT}~~/lib/intel64/libmkl_blas95_lp64.a ~~${MKLROOT}~~/lib/intel64/libmkl_lapack95_lp64.a -L~~${MKLROOT}~~/lib/intel64 -lmkl_intel_lp64 -lmkl_intel_thread -lmkl_core -liomp5 -lpthread -lm -ldl

	\|}		\|}

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

2016-11-21T11:18:07Z

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

	{{algorithm		{{algorithm
	\| name = Алгоритм Ланцоша с полной переортогонализацией		\| name = Алгоритм Ланцоша с полной переортогонализацией

Sfedotov в 15:38, 20 ноября 2016

2016-11-20T15:38:43Z

@@ Строка 1: / Строка 1: @@
 {{algorithm
 | name              = Алгоритм Ланцоша с полной переортогонализацией
@@ Строка 104: / Строка 106: @@
 == Возможные способы и особенности параллельной реализации алгоритма ==
 == Масштабируемость алгоритма и его реализации ==
 == Динамические характеристики и эффективность реализации алгоритма ==
 == Выводы для классов архитектур ==
@@ Строка 111: / Строка 140: @@
 *библиотека [https://en.wikipedia.org/wiki/ARPACK ARPACK]  на языке FORTRAN77
 *[http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library]
-*программный пакет [http://crd-legacy.lbl.gov/~kewu/trlan.html TRLan]
+*библиотека [http://crd-legacy.lbl.gov/~kewu/trlan.html TRLan]
 *[https://turi.com/products/create/open_source.html GraphLab] параллельная реализация на C++
 = Литература =
 <references \>

Sfedotov в 16:02, 18 ноября 2016

2016-11-18T16:02:12Z

← Предыдущая версия		Версия от 16:02, 18 ноября 2016
Строка 50:		Строка 50:

	== Макроструктура алгоритма ==		== Макроструктура алгоритма ==
	~~Основные состовляющие алгоритма это~~ умножение матрицы на вектор, процесс переортогонализации и поиск всех собственных значений и всех ~~собственных~~ векторов симметричной трехдиагональной матрицы.		Данный алгоритм разбивает исходную задачу поиска собственных значений и собственных векторов на два этапа: построение трехдиагональной матрицы и, непостредственно, сам поиск собственных значений и собственных векторов, аппроксимирующих исходные. Первый этап состоит из последовательного применения метода Ланцоша построения последовательности подпространств Крылова. На втором этапе одним из известных методов строятся оптимальные приближения. Из затратных операций можно выделить умножение матрицы на вектор, вычисление нормы вектора, процесс переортогонализации и поиск всех собственных значений и всех обственных векторов симметричной трехдиагональной матрицы.

	== Схема реализации последовательного алгоритма ==		== Схема реализации последовательного алгоритма ==
			В разделе [[#Математическое описание алгоритма]] уже представлено описание алгоритма.

			Пусть задана некая симметрическая матрица <math>A</math>

			Шаг 1: Вычислить <math>q_1, \beta_0, q_0</math>

			Шаг 2:В цикле последовательно вычислять матрицу <math>T_j,\alpha_j, \beta_j</math>

			*Найти собственные значения матрицы <math>T_j</math>
			*Если <math>\beta_j=0</math> Выход
	[[file:Lanczos1.jpg\|thumb\|center\|450px\|Блок-схема алгоритма]]		[[file:Lanczos1.jpg\|thumb\|center\|450px\|Блок-схема алгоритма]]

Строка 65:		Строка 76:

	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
	Алгоритм Ланцоша с полной переортогонализацией ~~в целом последовательный~~. На ''j''-м шаге вычисляются числа <math>\alpha_j, \beta_j</math> и ортонормированный вектор <math>q_{j+1}</math>, которые служат входными данными для ''j+1''-го шага. ~~Нетрудно заметить, что~~ процесс ортогонализации ''j''-го вектора Ритца ~~может быть вычислен параллельно~~, ~~как и~~ умножение исходной матрицы на вектор.		Алгоритм Ланцоша с полной переортогонализацией является итерационным. На ''j''-м шаге вычисляются числа <math>\alpha_j, \beta_j</math> и ортонормированный вектор <math>q_{j+1}</math>, которые служат входными данными для ''j+1''-го шага. Внутри одной итерации ресурсами параллелизма могут быть процесс ортогонализации ''j''-го вектора Ритца, умножение исходной матрицы на вектор, вычисление нормы вектора и другие векторные операции.
			Умножение вещественной симметричной матрицы ''A'' размера <math>n \times n</math> на вектор ''b'' длины ''n'' требует последовательного выполнения ''n'' ярусов умножений и сложений.

	== Входные и выходные данные алгоритма ==		== Входные и выходные данные алгоритма ==
Строка 80:		Строка 92:

	== Свойства алгоритма ==		== Свойства алгоритма ==
			*Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов с учётом ''k'' итераций оценивается в
			<math>\frac{kn^2}{k \log{n}}=\frac{n^2}{\log{n}}</math>
			*Вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных, оценивается в <math>\frac{k\,n^2}{0.5\,n^2+1.5\,n+k\,n+k+1}\approx 2\,k</math> так как в прикладных задачах часто требуется небольшое число собственных значений и справедливо <math>k<<n</math>
	*Алгоритм Ланцоша не требует хранения исходной матрицы полным массивом: метод использует исходную матрицу только в операциях умножения матрицы на вектор, что позволяет эффективно использовать разреженность матрицы или регулярность структуры матрицы. Поэтому алгоритм Ланцоша может быть использован для матриц таких больших порядков, когда методы вращений и отражений не могут быть применены.		*Алгоритм Ланцоша не требует хранения исходной матрицы полным массивом: метод использует исходную матрицу только в операциях умножения матрицы на вектор, что позволяет эффективно использовать разреженность матрицы или регулярность структуры матрицы. Поэтому алгоритм Ланцоша может быть использован для матриц таких больших порядков, когда методы вращений и отражений не могут быть применены.
	*Часто уже при небольшом <math>( j \sim 2 \sqrt{n})</math> числе шагов метода крайние пары Ритца <math>(\lambda_i,v_i\|[v_1,v_2,...,v_j]=Q_jV)</math> оказываются хорошими приближениями к крайним собственным парам исходной матрицы (имеются теоретические оценки скорости сходимости, обосновывающие эту возможность), а именно крайние собственные пары часто и нужны.		*Часто уже при небольшом <math>( j \sim 2 \sqrt{n})</math> числе шагов метода крайние пары Ритца <math>(\lambda_i,v_i\|[v_1,v_2,...,v_j]=Q_jV)</math> оказываются хорошими приближениями к крайним собственным парам исходной матрицы (имеются теоретические оценки скорости сходимости, обосновывающие эту возможность), а именно крайние собственные пары часто и нужны.

ASA в 14:31, 1 ноября 2016

2016-11-01T14:31:59Z

← Предыдущая версия		Версия от 14:31, 1 ноября 2016
Строка 1:		Строка 1:
	~~{{Assignment}}~~
	{{algorithm		{{algorithm
	\| name = Алгоритм Ланцоша с полной переортогонализацией		\| name = Алгоритм Ланцоша с полной переортогонализацией