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

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

2017-02-08T07:29:54Z

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

← Предыдущая версия		Версия от 07:29, 8 февраля 2017
Строка 217:		Строка 217:
	[http://pastebin.com/SbNrh7nz Используемая параллельная реализация алгоритма на языке C++]		[http://pastebin.com/SbNrh7nz Используемая параллельная реализация алгоритма на языке C++]

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

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

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

2017-02-08T07:28:15Z

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

← Предыдущая версия		Версия от 07:28, 8 февраля 2017
Строка 214:		Строка 214:

	Ниже на рисунке изображен трехмерный график, показывающий зависимость времени выполнения программы от входных данных/		Ниже на рисунке изображен трехмерный график, показывающий зависимость времени выполнения программы от входных данных/
	[[Файл:Lancos SO.png\|center\|800px\|График зависимости времени выполнения программы от входных данных]]		[[Файл:Lancos SO1.png\|center\|800px\|График зависимости времени выполнения программы от входных данных]]
	[http://pastebin.com/SbNrh7nz Используемая параллельная реализация алгоритма на языке C++]		[http://pastebin.com/SbNrh7nz Используемая параллельная реализация алгоритма на языке C++]

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

2017-02-08T06:51:50Z

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

← Предыдущая версия		Версия от 06:51, 8 февраля 2017
Строка 217:		Строка 217:
	[http://pastebin.com/SbNrh7nz Используемая параллельная реализация алгоритма на языке C++]		[http://pastebin.com/SbNrh7nz Используемая параллельная реализация алгоритма на языке C++]

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

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

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

2017-02-08T06:51:00Z

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

← Предыдущая версия		Версия от 06:51, 8 февраля 2017
Строка 205:		Строка 205:

	Для проведения расчетов и получения полноценной картины поведения алгоритма в зависимости от входных данных и числа процессоров, программа была запущена на следующих параметрах:		Для проведения расчетов и получения полноценной картины поведения алгоритма в зависимости от входных данных и числа процессоров, программа была запущена на следующих параметрах:
	* в качестве размера входной матрицы подавались значения в диапазоне [2000:50000] c шагом 2000.		* В каждом запуске искалось первые 10 собственных значений и собственных векторов.
			* В качестве размера входной матрицы подавались значения в диапазоне [2000:50000] c шагом 2000.
	* Число процессоров варьировалось от 4, 8, 16, 32, 64, 128.		* Число процессоров варьировалось от 4, 8, 16, 32, 64, 128.

	Сборка осуществлялась с параметрами:		Сборка осуществлялась с параметрами:
	* openmpi/1.5.5-icc		* openmpi/1.5.5-icc
			* intel/13.1.0

	* intel/13.1.0
	Ниже на рисунке изображен трехмерный график, показывающий зависимость времени выполнения программы от входных данных/		Ниже на рисунке изображен трехмерный график, показывающий зависимость времени выполнения программы от входных данных/
	[[Файл:Lancos SO.png\|center\|800px\|График зависимости времени выполнения программы от входных данных]]		[[Файл:Lancos SO.png\|center\|800px\|График зависимости времени выполнения программы от входных данных]]
	[http://pastebin.com/SbNrh7nz Используемая параллельная реализация алгоритма на языке C++]		[http://pastebin.com/SbNrh7nz Используемая параллельная реализация алгоритма на языке C++]

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

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

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

2017-02-08T06:33:46Z

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

← Предыдущая версия		Версия от 06:33, 8 февраля 2017
Строка 212:		Строка 212:
	* intel/13.1.0		* intel/13.1.0
	Ниже на рисунке изображен трехмерный график, показывающий зависимость времени выполнения программы от входных данных/		Ниже на рисунке изображен трехмерный график, показывающий зависимость времени выполнения программы от входных данных/
	[[Файл:~~Lancos_SO~~.~~jpg~~\|center\|800px\|График зависимости времени выполнения программы от входных данных]]		[[Файл:Lancos SO.png\|center\|800px\|График зависимости времени выполнения программы от входных данных]]
	[http://pastebin.com/SbNrh7nz Используемая параллельная реализация алгоритма на языке C++]		[http://pastebin.com/SbNrh7nz Используемая параллельная реализация алгоритма на языке C++]

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

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

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

2017-02-08T06:31:19Z

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

← Предыдущая версия		Версия от 06:31, 8 февраля 2017
Строка 212:		Строка 212:
	* intel/13.1.0		* intel/13.1.0
	Ниже на рисунке изображен трехмерный график, показывающий зависимость времени выполнения программы от входных данных/		Ниже на рисунке изображен трехмерный график, показывающий зависимость времени выполнения программы от входных данных/
	[[Файл:~~time_dependance~~.jpg\|center\|800px\|График зависимости времени выполнения программы от входных данных]]		[[Файл:Lancos_SO.jpg\|center\|800px\|График зависимости времени выполнения программы от входных данных]]
	[http://pastebin.com/SbNrh7nz Используемая параллельная реализация алгоритма на языке C++]		[http://pastebin.com/SbNrh7nz Используемая параллельная реализация алгоритма на языке C++]

ASA в 11:56, 7 февраля 2017

2017-02-07T11:56:54Z

← Предыдущая версия		Версия от 11:56, 7 февраля 2017
Строка 1:		Строка 1:
	{{~~assignment~~}}		{{Assignment\|ASA}}

	Автор: [https://algowiki-project.org/ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Abdulpotiev Абдулпотиев А.А.]		Автор: [https://algowiki-project.org/ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Abdulpotiev Абдулпотиев А.А.]

Abdulpotiev в 20:31, 6 февраля 2017

2017-02-06T20:31:28Z

← Предыдущая версия		Версия от 20:31, 6 февраля 2017
Строка 1:		Строка 1:
			{{assignment}}
	Автор: [https://algowiki-project.org/ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Abdulpotiev Абдулпотиев А.А.]		Автор: [https://algowiki-project.org/ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Abdulpotiev Абдулпотиев А.А.]

Abdulpotiev: /* Математическое описание алгоритма */

2017-02-06T20:24:05Z

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

← Предыдущая версия		Версия от 20:24, 6 февраля 2017
Строка 66:		Строка 66:
	Где <math>v_i</math> - это столбцы ортогональной матрицы <math>V</math> из спектрального разложения <math>T_k = V \Lambda V^T</math>, а <math>y_{k,i} = Q_k v_i</math> - столбцы матрицы <math>Q_k V</math> - векторы Ритца.		Где <math>v_i</math> - это столбцы ортогональной матрицы <math>V</math> из спектрального разложения <math>T_k = V \Lambda V^T</math>, а <math>y_{k,i} = Q_k v_i</math> - столбцы матрицы <math>Q_k V</math> - векторы Ритца.

	Матрица <math>T_j</math>		Матрица <math>T_j</math>:

	:<math>		:<math>
	T_j = \begin{pmatrix}		T_j = \begin{pmatrix}

Abdulpotiev: /* Математическое описание алгоритма */

2017-02-06T20:23:06Z

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

← Предыдущая версия		Версия от 20:23, 6 февраля 2017
Строка 44:		Строка 44:
	Тогда алгоритм Ланцоша вычисления собственных векторов и собственных значений матрицы <math>A</math> с выборочной ортогонализацией имеет следующий вид:		Тогда алгоритм Ланцоша вычисления собственных векторов и собственных значений матрицы <math>A</math> с выборочной ортогонализацией имеет следующий вид:



	<math>1)</math>: Считается норма вектора <math> b: \; \; \\|b\\|_2 = \sqrt{\sum\limits_{j=1}^{n} b_j^2},</math>		<math>1)</math>: Считается норма вектора <math> b: \; \; \\|b\\|_2 = \sqrt{\sum\limits_{j=1}^{n} b_j^2},</math>
	<math>2)</math> Находится первый вектор матрицы <math> Q: \; \; q_{1} = \frac{b}{\\|b\\|_2},</math>		<math>2)</math> Находится первый вектор матрицы <math> Q: \; \; q_{1} = \frac{b}{\\|b\\|_2},</math>