Алгоритм Ланцоша с выборочной ортогонализацией - История изменений

ASA в 13:08, 3 февраля 2017

2017-02-03T13:08:37Z

← Предыдущая версия		Версия от 13:08, 3 февраля 2017
Строка 1:		Строка 1:
	~~%{{assignment}}~~
	Авторы: Басалаев М.Н. 619, Тевдорадзе С.З. 614. Авторы внесли равнозначный вклад в каждый из разделов данной статьи.		Авторы: Басалаев М.Н. 619, Тевдорадзе С.З. 614. Авторы внесли равнозначный вклад в каждый из разделов данной статьи.

Syuzana в 07:11, 24 января 2017

2017-01-24T07:11:07Z

← Предыдущая версия		Версия от 07:11, 24 января 2017
Строка 1:		Строка 1:
	{{assignment}}		%{{assignment}}
	Авторы: Басалаев М.Н. 619, Тевдорадзе С.З. 614. Авторы внесли равнозначный вклад в каждый из разделов данной статьи.		Авторы: Басалаев М.Н. 619, Тевдорадзе С.З. 614. Авторы внесли равнозначный вклад в каждый из разделов данной статьи.

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


			<math> b=a+c </math>



	===Общее описание алгоритма===		===Общее описание алгоритма===
	Алгоритм Лáнцоша представляет собой мощный метод для нахождения нескольких собственных значений и собственных векторов симметричной матрицы А и для решения систем линейных уравнений. Алгоритм особенно эффективен, если матрица А разреженная и большого размера. Однако любая практическая реализация этого алгоритма страдает от ошибок округления, т.к. векторы Ланцоша теряют взаимную ортогональность. Для того чтобы поддерживать некоторый уровень ортогональности, появились методы полной переортогонализации и выборочной ортогонализации. В этой работе мы рассмотрим последний метод в качестве способа для поддержания ортогональности среди векторов Ланцоша. Он обладает почти столь же высокой точностью, как алгоритм с полной переортогонализацией, и почти столь же низкой стоимостью, как алгоритм без ортогонализации <ref>"The Lanczos Algorithm With Partial Reorthogonalization", Horst D. Simon, Mathematics of computation, volume 42, number 165, pages 115-142 (1984)</ref>.		Алгоритм Лáнцоша представляет собой мощный метод для нахождения нескольких собственных значений и собственных векторов симметричной матрицы А и для решения систем линейных уравнений. Алгоритм особенно эффективен, если матрица А разреженная и большого размера. Однако любая практическая реализация этого алгоритма страдает от ошибок округления, т.к. векторы Ланцоша теряют взаимную ортогональность. Для того чтобы поддерживать некоторый уровень ортогональности, появились методы полной переортогонализации и выборочной ортогонализации. В этой работе мы рассмотрим последний метод в качестве способа для поддержания ортогональности среди векторов Ланцоша. Он обладает почти столь же высокой точностью, как алгоритм с полной переортогонализацией, и почти столь же низкой стоимостью, как алгоритм без ортогонализации <ref>"The Lanczos Algorithm With Partial Reorthogonalization", Horst D. Simon, Mathematics of computation, volume 42, number 165, pages 115-142 (1984)</ref>.

Syuzana: /* Общее описание алгоритма */

2017-01-23T23:26:58Z

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

← Предыдущая версия		Версия от 23:26, 23 января 2017
Строка 28:		Строка 28:

	После следует вычисление собственных значений <math> \theta_j </math> и собственных векторов <math>v_j </math> полученной трехдиагональной матрицы <math>T_j</math>, для чего существует, например, метод "разделяй и властвуй"<ref>Дж. Деммель «Вычислительная линейная алгебра», c. 232, алгоритм 5.2</ref>		После следует вычисление собственных значений <math> \theta_j </math> и собственных векторов <math>v_j </math> полученной трехдиагональной матрицы <math>T_j</math>, для чего существует, например, метод "разделяй и властвуй"<ref>Дж. Деммель «Вычислительная линейная алгебра», c. 232, алгоритм 5.2</ref>

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===
	<math> \beta_0=0,q_0=0</math>		<math> \beta_0=0,q_0=0</math>

Syuzana в 16:52, 19 декабря 2016

2016-12-19T16:52:00Z

← Предыдущая версия		Версия от 16:52, 19 декабря 2016
Строка 1:		Строка 1:
	{{assignment}}		{{assignment}}
	Авторы: ~~Беслаев~~ М.Н. 619, Тевдорадзе С.З. 614. Авторы внесли равнозначный вклад в каждый из разделов данной статьи.		Авторы: Басалаев М.Н. 619, Тевдорадзе С.З. 614. Авторы внесли равнозначный вклад в каждый из разделов данной статьи.

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

Syuzana в 16:31, 19 декабря 2016

2016-12-19T16:31:04Z

← Предыдущая версия		Версия от 16:31, 19 декабря 2016
Строка 1:		Строка 1:
	Авторы: Беслаев М. ?, Тевдорадзе С.З. 614. Авторы внесли равнозначный вклад в каждый из разделов данной статьи.		{{assignment}}
			Авторы: Беслаев М.Н. 619, Тевдорадзе С.З. 614. Авторы внесли равнозначный вклад в каждый из разделов данной статьи.

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

Syuzana: /* Масштабируемость алгоритма и его реализации */

2016-12-19T16:28:48Z

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

← Предыдущая версия		Версия от 16:28, 19 декабря 2016
Строка 196:		Строка 196:

	[[File:time_dependance.jpg\| center\|border \|800px]]		[[File:time_dependance.jpg\| center\|border \|800px]]
			[http://pastebin.com/SbNrh7nz Используемая параллельная реализация алгоритма на языке C++]

	На данном графике отчетливо видно, что время выполнения алгоритма сильно уменьшается с увеличением количества процессов при расчете матрицы любой размерности. При этом наблюдается некоторое снижение производительности в случае наибольших размеров матриц. Данный факт является следствием большого количества данных, необходимого для обмена между процессами. Отсюда опытным путем можно установить, что наибольшая производительность алгоритма будет достигнута, если размерность матрицы не будет превышать 30000-35000.		На данном графике отчетливо видно, что время выполнения алгоритма сильно уменьшается с увеличением количества процессов при расчете матрицы любой размерности. При этом наблюдается некоторое снижение производительности в случае наибольших размеров матриц. Данный факт является следствием большого количества данных, необходимого для обмена между процессами. Отсюда опытным путем можно установить, что наибольшая производительность алгоритма будет достигнута, если размерность матрицы не будет превышать 30000-35000.

Syuzana: /* Масштабируемость алгоритма и его реализации */

2016-12-19T16:18:48Z

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

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

	Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:		Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
	*Число процессоров ~~<math>~~4,8,16,32,64,128~~</math>~~		*Число процессоров 4, 8, 16, 32, 64, 128.
	*Размерность матрицы ~~<math>~~ от 1000 до 50000~~</math>~~		*Размерность матрицы от 1000 до 50000
	Сборка осуществлялась с параметрами:		Сборка осуществлялась с параметрами:
	*openmpi/1.5.5-icc		*openmpi/1.5.5-icc
	*intel/13.1.0		*intel/13.1.0

	[[~~Файл~~:~~Time_dependance~~.jpg\|~~200px~~\| ~~frame~~ \|~~рис. 2: Оценка маштабируемости алгоритма~~]]		[[File:time_dependance.jpg\| center\|border \|800px]]


	На данном графике отчетливо видно, что время выполнения алгоритма сильно уменьшается с увеличением количества процессов при расчете матрицы любой размерности. При этом наблюдается некоторое снижение производительности в случае наибольших размеров матриц. Данный факт является следствием большого количества данных, необходимого для обмена между процессами. Отсюда опытным путем можно установить, что наибольшая производительность алгоритма будет достигнута, если размерность матрицы не будет превышать 30000-35000.		На данном графике отчетливо видно, что время выполнения алгоритма сильно уменьшается с увеличением количества процессов при расчете матрицы любой размерности. При этом наблюдается некоторое снижение производительности в случае наибольших размеров матриц. Данный факт является следствием большого количества данных, необходимого для обмена между процессами. Отсюда опытным путем можно установить, что наибольшая производительность алгоритма будет достигнута, если размерность матрицы не будет превышать 30000-35000.

Syuzana: /* Масштабируемость алгоритма и его реализации */

2016-12-19T16:07:20Z

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

← Предыдущая версия		Версия от 16:07, 19 декабря 2016
Строка 195:		Строка 195:
	*intel/13.1.0		*intel/13.1.0

	[[Файл:Time_dependance.jpg\|~~50px~~\| frame \|рис. 2: Оценка маштабируемости алгоритма]]		[[Файл:Time_dependance.jpg\|200px\| frame \|рис. 2: Оценка маштабируемости алгоритма]]

	На данном графике отчетливо видно, что время выполнения алгоритма сильно уменьшается с увеличением количества процессов при расчете матрицы любой размерности. При этом наблюдается некоторое снижение производительности в случае наибольших размеров матриц. Данный факт является следствием большого количества данных, необходимого для обмена между процессами. Отсюда опытным путем можно установить, что наибольшая производительность алгоритма будет достигнута, если размерность матрицы не будет превышать 30000-35000.		На данном графике отчетливо видно, что время выполнения алгоритма сильно уменьшается с увеличением количества процессов при расчете матрицы любой размерности. При этом наблюдается некоторое снижение производительности в случае наибольших размеров матриц. Данный факт является следствием большого количества данных, необходимого для обмена между процессами. Отсюда опытным путем можно установить, что наибольшая производительность алгоритма будет достигнута, если размерность матрицы не будет превышать 30000-35000.

Syuzana: /* Масштабируемость алгоритма и его реализации */

2016-12-19T16:05:38Z

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

← Предыдущая версия		Версия от 16:05, 19 декабря 2016
Строка 184:		Строка 184:
	=== Локальность данных и вычислений===		=== Локальность данных и вычислений===
	=== Возможные способы и особенности параллельной реализации алгоритма===		=== Возможные способы и особенности параллельной реализации алгоритма===
	~~=== Масштабируемость алгоритма и его реализации===~~

	~~ЭТО~~		=== Масштабируемость алгоритма и его реализации ===
			Исследование масштабируемости реализации алгоритма проводилось с использованием стандарта MPI на суперкомпьютере "Ломоносов".

			Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
			*Число процессоров <math>4,8,16,32,64,128</math>
			*Размерность матрицы <math> от 1000 до 50000</math>
			Сборка осуществлялась с параметрами:
			*openmpi/1.5.5-icc
			*intel/13.1.0

			[[Файл:Time_dependance.jpg\|50px\| frame \|рис. 2: Оценка маштабируемости алгоритма]]

			На данном графике отчетливо видно, что время выполнения алгоритма сильно уменьшается с увеличением количества процессов при расчете матрицы любой размерности. При этом наблюдается некоторое снижение производительности в случае наибольших размеров матриц. Данный факт является следствием большого количества данных, необходимого для обмена между процессами. Отсюда опытным путем можно установить, что наибольшая производительность алгоритма будет достигнута, если размерность матрицы не будет превышать 30000-35000.

	=== Динамические характеристики и эффективность реализации алгоритма===		=== Динамические характеристики и эффективность реализации алгоритма===

Syuzana в 15:58, 19 декабря 2016

2016-12-19T15:58:04Z

← Предыдущая версия		Версия от 15:58, 19 декабря 2016
Строка 1:		Строка 1:
			Авторы: Беслаев М. ?, Тевдорадзе С.З. 614. Авторы внесли равнозначный вклад в каждый из разделов данной статьи.

	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
	===Общее описание алгоритма===		===Общее описание алгоритма===