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

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

2017-12-04T08:01:47Z

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

← Предыдущая версия		Версия от 08:01, 4 декабря 2017
Строка 101:		Строка 101:
	=== Информационный граф ===		=== Информационный граф ===

	~~Пересылка данных происходит от каждого процесса к первому~~. ~~При~~ этом ~~в первом процессе так же происходят вычисления~~, ~~поэтому может возникнуть задержка при пересылке данных, если вычисления~~ в ~~первом процессе ещё не завершены. Однако выделять под обработку пересланных данных отдельный~~ процесс ~~нерационально: в таком случае на нём будет застой во время вычислений на всех остальных процессах~~.		Информационный граф алгоритма представлен на рисунке 1. Каждой зелёной вершине соответствует одна итерация алгоритма (при этом запущено <math>n</math> различных процессов), далее все полученные результаты пересылаются в один процесс для последующей обработки и вывода (синяя вершина).
			[[file:Newtone scheme.png\|thumb\|center\|512px\|Рисунок 1. Информационный граф алгоритма.]]
	[[file:~~Newton_scheme~~.png\|thumb\|center\|512px\|Рисунок 1. ~~Граф~~ алгоритма.]]

	При этом первый процесс не пересылает свои данные к себе (в привычном понимании пересылки), а просто сохраняет полученные результаты в отдельный массив.

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

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

2017-12-04T06:44:57Z

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

← Предыдущая версия		Версия от 06:44, 4 декабря 2017
Строка 151:		Строка 151:

	[[file:Newton_scale_results.jpg\|thumb\|center\|512px\|Рисунок 3. Зависимость от числа процессоров.]]		[[file:Newton_scale_results.jpg\|thumb\|center\|512px\|Рисунок 3. Зависимость от числа процессоров.]]


			Приведённые выше результаты были получены на суперкомпьютере “Ломоносов”.
			Компиляция осуществлялась с помощью команды mpicc библиотеки OpenMPI, версия компилятора — gcc 1.8.4. При этом использовался ключ -std=c99, необходимый для использования описанной в языке Си реализации комплексных чисел.

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

Chist в 17:14, 24 ноября 2017

2017-11-24T17:14:48Z

← Предыдущая версия		Версия от 17:14, 24 ноября 2017
Строка 1:		Строка 1:
			Чистяков И.А., метод Ньютона

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

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

2017-11-24T17:13:54Z

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

← Предыдущая версия		Версия от 17:13, 24 ноября 2017
Строка 6:		Строка 6:
	Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Модификацией метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства.		Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Модификацией метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства.

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

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

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

2017-11-20T12:42:24Z

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

← Предыдущая версия		Версия от 12:42, 20 ноября 2017
Строка 143:		Строка 143:
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===

	На рисунке 2 показана зависимость времени работы программы от количества процессоров и степени многочлена (рассматривались ~~полиномы~~ вида <math>z^p - 1 = 0</math>).		На рисунке 2 показана зависимость времени работы программы от количества процессоров и степени многочлена (рассматривались уравнения вида <math>z^p - 1 = 0</math>).

	[[file:Newton_scale_results_3d.jpg\|thumb\|center\|512px\|Рисунок 2. Масштабируемость алгоритма.]]		[[file:Newton_scale_results_3d.jpg\|thumb\|center\|512px\|Рисунок 2. Масштабируемость алгоритма.]]

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

2017-11-20T11:35:29Z

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

← Предыдущая версия		Версия от 11:35, 20 ноября 2017
Строка 143:		Строка 143:
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===

	На рисунке 2 ~~показаны результаты~~ работы программы ~~при нахождении корней уравнения~~ <math>z^4 - 1 = 0</math> на сетке с <math>1024 \times 1024</math> узлами. Красным отмечено время работы параллельного участка программы (включает в себя время на пересылку данных). Для сравнения синим цветом обозначена функция <math>y(x) = 128 / x</math>. Из этого можно сделать вывод, что время работы программы обратно пропорционально числу процессоров.		На рисунке 2 показана зависимость времени работы программы от количества процессоров и степени многочлена (рассматривались полиномы вида <math>z^p - 1 = 0</math>).

	[[file:~~newton_scale_results~~.jpg\|thumb\|center\|512px\|Рисунок 2. Масштабируемость алгоритма.]]		[[file:Newton_scale_results_3d.jpg\|thumb\|center\|512px\|Рисунок 2. Масштабируемость алгоритма.]]

			Как видно из рисунка, время выполнения пропорционально степени полинома и обратно пропорционально числу процессоров, что согласуется с теоретическими результатами. На рисунке 3 показана зависимость времени работы от числа процессоров при фиксированной степени полинома <math>p = 4</math>. Можно заметить, что в данном случае полученные результаты достаточно хорошо аппроксимируются функцией <math>y(x) = 50 / x</math>.

			[[file:Newton_scale_results.jpg\|thumb\|center\|512px\|Рисунок 3. Зависимость от числа процессоров.]]

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

Chist: /* Ресурс параллелизма алгоритма */

2017-11-20T06:25:14Z

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

← Предыдущая версия		Версия от 06:25, 20 ноября 2017
Строка 107:		Строка 107:

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

			Алгоритм является строго последовательным, однако существует возможность распараллеливания благодаря перебору. Таким образом сложность алгоритма равна <math>O(\frac{N \cdot M}{n})</math>.

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

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

2017-11-19T22:26:00Z

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

← Предыдущая версия		Версия от 22:26, 19 ноября 2017
Строка 140:		Строка 140:

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

			На рисунке 2 показаны результаты работы программы при нахождении корней уравнения <math>z^4 - 1 = 0</math> на сетке с <math>1024 \times 1024</math> узлами. Красным отмечено время работы параллельного участка программы (включает в себя время на пересылку данных). Для сравнения синим цветом обозначена функция <math>y(x) = 128 / x</math>. Из этого можно сделать вывод, что время работы программы обратно пропорционально числу процессоров.

			[[file:newton_scale_results.jpg\|thumb\|center\|512px\|Рисунок 2. Масштабируемость алгоритма.]]

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

Chist: /* Схема реализации последовательного алгоритма */

2017-11-19T22:14:46Z

Схема реализации последовательного алгоритма

← Предыдущая версия		Версия от 22:14, 19 ноября 2017
Строка 77:		Строка 77:
	=== Схема реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===

	Последовательный алгоритм является частным случаем описанного алгоритма при <math>n = 1</math>.		Последовательный алгоритм является частным случаем описанного алгоритма при <math>n = 1</math>. При этом не возникает затрат на пересылку информации о найденных корнях к одному процессу, что позволяет более эффективно работать с памятью.

	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

Chist: /* Программная реализация алгоритма */

2017-11-19T22:12:24Z

Программная реализация алгоритма

← Предыдущая версия		Версия от 22:12, 19 ноября 2017
Строка 144:		Строка 144:

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

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

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