Участник:MukhayevD/Метод Ньютона - История изменений

ASA в 07:50, 1 декабря 2016

2016-12-01T07:50:51Z

← Предыдущая версия		Версия от 07:50, 1 декабря 2016
Строка 1:		Строка 1:
	~~{{assignment}}~~
	Автор: [[Участник:MukhayevD\|Мухаев Д.Н.]]		Автор: [[Участник:MukhayevD\|Мухаев Д.Н.]]

MukhayevD в 16:13, 30 ноября 2016

2016-11-30T16:13:54Z

← Предыдущая версия		Версия от 16:13, 30 ноября 2016
Строка 1:		Строка 1:
			{{assignment}}
	Автор: [[Участник:MukhayevD\|Мухаев Д.Н.]]		Автор: [[Участник:MukhayevD\|Мухаев Д.Н.]]

MukhayevD: /* Существующие реализации алгоритма */

2016-11-25T16:38:13Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 16:38, 25 ноября 2016
Строка 106:		Строка 106:
	Как видно из рисунков вне зависимости от размерности задачи не удалось добиться времени больше <math> 0.1 </math> секунды, в виду этого можно предположить, что время зависит от физического расположения процессоров, но тем не менее есть общая тенденция, что время работы возрастает вместе с размерностью и количеством процессоров.		Как видно из рисунков вне зависимости от размерности задачи не удалось добиться времени больше <math> 0.1 </math> секунды, в виду этого можно предположить, что время зависит от физического расположения процессоров, но тем не менее есть общая тенденция, что время работы возрастает вместе с размерностью и количеством процессоров.

	=== Существующие реализации алгоритма ===		=== 2.7 Существующие реализации алгоритма ===

	1. Последовательные реализации		1. Последовательные реализации

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

2016-11-25T16:37:54Z

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

← Предыдущая версия		Версия от 16:37, 25 ноября 2016
Строка 89:		Строка 89:
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==

	=== Масштабируемость алгоритма и его реализации ===		===2.4 Масштабируемость алгоритма и его реализации ===
	Так как сам по себе метод является последовательным то, следовательно о его масштабируемости не может быть и речи.		Так как сам по себе метод является последовательным то, следовательно о его масштабируемости не может быть и речи.

MukhayevD в 16:35, 25 ноября 2016

2016-11-25T16:35:58Z

← Предыдущая версия		Версия от 16:35, 25 ноября 2016
Строка 1:		Строка 1:
	~~{{algorithm~~		Автор: [[Участник:MukhayevD\|Мухаев Д.Н.]]
	~~\| name =~~
	~~\| serial_complexity =~~
	~~\| input_data =~~
	\| ~~output_data =~~
	}}

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

MukhayevD: /* Существующие реализации алгоритма */

2016-11-25T16:29:00Z

Существующие реализации алгоритма

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

	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

			1. Последовательные реализации

			**ALIAS C++. Язык реализации - C++. Распространяется бесплатно, исходные коды и примеры использования можно скачать на сайте<ref name="ALIAS">https://www-sop.inria.fr/coprin/logiciels/ALIAS/ALIAS-C++/ALIAS-C++.html</ref>.
			**Numerical Recipes. Язык реализации - C++. Исходный код можно найти в секции 9.7 книги Numerical recipes(third edition)<ref name="RECIPES">http://numerical.recipes</ref>. Бесплатно доступны<ref name="RECIPES_old">http://numerical.recipes/oldverswitcher.html</ref> предыдущие издания для языков C, Fortran77, Fortran90.
			**Sundials. Язык реализации - C, также есть интерфейс для использования в Fortran-программах. Распространяется<ref name="SUNDIALS_seq">http://computation.llnl.gov/projects/sundials/kinsol</ref> по лицензии BSD.

			2. Параллельные реализации
			**Построение параллельной реализации метода Ньютона для решения задач линейного программирования описано в работе В.А. Гаранжа, А.И. Голикова, Ю.Г. Евтушенко, М.Х. Нгуена "Параллельная реализации метода Ньютона для решения больших задач линейного программирования" <ref name="CCAS">http://www.ccas.ru/personal/evtush/p/paper1.pdf</ref>.
			**Построение параллельной реализации метода Ньютона для решения задач оптимизации, описываются в работе V. A. Garanzha, A. I. Golikov, Yu. G. Evtushenko, and M. Kh. Nguen "Parallel Implementation of Newton’s Method for Solving Large-Scale Linear Programs" <ref name="IMPL_OPT">http://www.ccas.ru/personal/evtush/p/CMMP1303.pdf</ref>.
			**Построение параллельной реализации метода Ньютона, а также результаты некоторых экспериментов, описываются в работе Renato N. Elias Alvaro L. G. A. Coutinho Marcos A. D. Martins Rubens M. Sydenstricker "PARALLEL INEXACT NEWTON-TYPE METHODS FOR THE SUPG/PSPG SOLUTION OF STEADY INCOMPRESSIBLE 3D NAVIER-STOKES EQUATIONS IN PC CLUSTERS" <ref name="SUPG">http://www.nacad.ufrj.br/~rnelias/papers/CIL14-020.pdf</ref>.
			**Описание использования и результатов экспериментов с параллельной реализацией метода Ньютона в задаче фильтрации вязкой сжимаемой многофазной многокомпонентной смеси в пористой среде описано в работе К.Ю.Богачева "Эффективное решение задачи фильтрации вязкой сжимаемой многофазной многокомпонентной смеси на параллельных ЭВМ"<ref name="BOGACHEV">http://academy.hpc-russia.ru/files/reservoirdynamics_bogachev.pdf</ref>.

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

	<references \>		<references \>

MukhayevD: /* Информационный граф */

2016-11-25T16:16:46Z

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

← Предыдущая версия		Версия от 16:16, 25 ноября 2016
Строка 65:		Строка 65:
	На рисунке ниже изображена структура информационного графа алгоритма. Блок IN представляет собой выбор начального приближения, блок IT - итерацию алгоритма, блок OUT - концу работы алгоритма.		На рисунке ниже изображена структура информационного графа алгоритма. Блок IN представляет собой выбор начального приближения, блок IT - итерацию алгоритма, блок OUT - концу работы алгоритма.

	[[Файл:MNP1.~~png~~\|center\|frame\|Рисунок 1. Информационный граф]]		[[Файл:MNP1.PNG\|center\|frame\|Рисунок 1. Информационный граф]]

	Как видно, алгоритм строго последовательный.		Как видно, алгоритм строго последовательный.
	Ниже подробнее рассмотрено как можно разделить нагрузку связанную с вычислениями <math> f(x) </math> между процессорами. Каждое слагаемое полинома считается отдельно.		Ниже подробнее рассмотрено как можно разделить нагрузку связанную с вычислениями <math> f(x) </math> между процессорами. Каждое слагаемое полинома считается отдельно.
	[[Файл:MNP2.~~png~~\|center\|frame\|Рисунок 2. Итерация]]
			[[Файл:MNP2.PNG\|center\|frame\|Рисунок 2. Итерация]]

	Аналогично для <math> f^'(x) </math>.		Аналогично для <math> f^'(x) </math>.

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

2016-11-25T16:10:10Z

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

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

	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
			Так как сам по себе метод является последовательным то, следовательно о его масштабируемости не может быть и речи.

			Поверка масштабируемости реализации метода проводилась на следующих тестах:

			* 1) <math> (x-1)g(x) </math>, где <math> g(x) </math> - произвольный полином степени <math> n-1 </math>.

			[[Файл:MNP4.png\|center\|frame\|Рисунок 1.]]


			* 2) <math> 1 + 2x + 2x^2 + ... + 2x^{n-1} + x^n </math>


			[[Файл:MNP3.png\|center\|frame\|Рисунок 2.]]

			Как видно из рисунков вне зависимости от размерности задачи не удалось добиться времени больше <math> 0.1 </math> секунды, в виду этого можно предположить, что время зависит от физического расположения процессоров, но тем не менее есть общая тенденция, что время работы возрастает вместе с размерностью и количеством процессоров.

	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

MukhayevD в 21:03, 23 ноября 2016

2016-11-23T21:03:16Z

← Предыдущая версия		Версия от 21:03, 23 ноября 2016
Строка 37:		Строка 37:
	Последовательность исполнения метода следующая:		Последовательность исполнения метода следующая:

	1. Выбираем начальное приближение <math> x_0 </math>		1. Выбираем начальное приближение <math> x_0 </math>
			2. Находим значение функции <math> f(x_n) </math> в точке <math>x_n</math>.
	2. Находим значение функции <math> f(x_n) </math> в точке x_n.		3. Находим значение производной функции <math> f^'(x_n) </math> в точке <math>x_n</math>.
			4. Получаем следующий шаг итерации <math> x_{n+1} </math><math> x_{n+1} = x_n - f(x_n)/f^'(x+n) </math>
	3. Находим значение производной функции <math> f^'(x_n) </math> в точке x_n.		5. Находим погрешность <math> e = \|x_{n+1} - x_n\| </math>
			6. Если погрешность не превышает некоторого заранее заданного числа - останавливаемся.
	4. Получаем следующий шаг итерации <math> x_{n+1} </math>

	<math> x_{n+1} = x_n - f(x_n)/f^'(x+n) </math>

	5. Находим погрешность <math> e = \|x_{n+1} - x_n\| </math>

	6. Если погрешность не превышает некоторого заранее заданного числа - останавливаемся.

	<math> e < \varepsilon </math>		<math> e < \varepsilon </math>
Строка 80:		Строка 73:

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

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

			Пусть имеем <math> p </math> процессоров, в таком случае каждому процессору нужно будет произвести <math> (4n-3)/p </math> умножений.

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===

	~~=== Свойства~~ алгоритма ~~===~~		Входными данными алгоритма являются:

	~~== Программная реализация алгоритма ==~~		1. Функция в виде полинома.
			2. Область, в которой ищется корень <math> (a;b) </math>.
			3. Начальное приближение <math> x_0 </math>.
			4. Точность, с которой требуется найти решение.

	~~=== Особенности реализации последовательного алгоритма ===~~		На выход алгоритмом выдается число - предположительный корень найденный с заданной точностью.

	==~~= Локальность данных и вычислений ===~~		== Программная реализация алгоритма ==

	~~=== Возможные способы и особенности параллельной реализации~~ алгоритма ===

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

	~~==== Масштабируемость алгоритма ====~~

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

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

	~~=== Выводы для классов архитектур ===~~

	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

MukhayevD: /* Информационный граф */

2016-11-23T20:43:16Z

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

← Предыдущая версия		Версия от 20:43, 23 ноября 2016
Строка 71:		Строка 71:
	=== Информационный граф ===		=== Информационный граф ===
	На рисунке ниже изображена структура информационного графа алгоритма. Блок IN представляет собой выбор начального приближения, блок IT - итерацию алгоритма, блок OUT - концу работы алгоритма.		На рисунке ниже изображена структура информационного графа алгоритма. Блок IN представляет собой выбор начального приближения, блок IT - итерацию алгоритма, блок OUT - концу работы алгоритма.

	[[Файл:MNP1.png\|center\|frame\|Рисунок 1. Информационный граф]]		[[Файл:MNP1.png\|center\|frame\|Рисунок 1. Информационный граф]]

	Как видно, алгоритм строго последовательный.		Как видно, алгоритм строго последовательный.
	Ниже подробнее рассмотрено как можно разделить нагрузку связанную с вычислениями <math> f(x) </math> между процессорами. Каждое слагаемое полинома считается отдельно.		Ниже подробнее рассмотрено как можно разделить нагрузку связанную с вычислениями <math> f(x) </math> между процессорами. Каждое слагаемое полинома считается отдельно.