Участник:Vika3410/Метод Разделяй и властвуй - История изменений

IgorS в 10:28, 9 января 2017

2017-01-09T10:28:53Z

← Предыдущая версия		Версия от 10:28, 9 января 2017
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment\|IgorS}}

	Авторы статьи: [[Участник:NikoSergAlex\|Сергеев Никита]] (группа 614) (1.1, 1.2, 1.5, 1.6, 1.7, 1.8, 1.10, 2.4), [[Участница:Vika3410\|Стрельцова Виктория]] (группа 614) (1.2, 1.3, 1.4, 1.6, 1.7, 1.9, 1.10, 2.4)		Авторы статьи: [[Участник:NikoSergAlex\|Сергеев Никита]] (группа 614) (1.1, 1.2, 1.5, 1.6, 1.7, 1.8, 1.10, 2.4), [[Участница:Vika3410\|Стрельцова Виктория]] (группа 614) (1.2, 1.3, 1.4, 1.6, 1.7, 1.9, 1.10, 2.4)

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

2016-12-31T12:37:54Z

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

← Предыдущая версия		Версия от 12:37, 31 декабря 2016
Строка 214:		Строка 214:
	На рисунке 3 изображена структура алгоритма.		На рисунке 3 изображена структура алгоритма.

	[[File:~~Сергеев 5~~.~~jpg~~\|thumb\|center\|left\|1000px\|Рис. 3. Дерево алгоритма "Разделяй и властвуй"]]		[[File:Sergeev_5.png\|thumb\|center\|left\|1000px\|Рис. 3. Дерево алгоритма "Разделяй и властвуй"]]

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

2016-12-31T11:59:16Z

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

@@ Строка 213: / Строка 213: @@
 == Информационный граф ==
 На рисунке 3 изображена структура алгоритма.
 [[File:Сергеев 5.jpg|thumb|center|left|1000px|Рис. 3. Дерево алгоритма "Разделяй и властвуй"]]
 == Ресурс параллелизма алгоритма ==

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

2016-12-31T11:04:34Z

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

← Предыдущая версия		Версия от 11:04, 31 декабря 2016
Строка 124:		Строка 124:

	Основной выигрыш от использования дефляции состоит не в том, что убыстряется решение векового уравнения - этот этап в любом случае стоит лишь <math>O(n^{2})</math> операций. Выигрыш заключается в ускорении матричного умножения на последнем шаге алгоритма. Действительно, если <math>u_{i}=0</math>, то соответствующий собственный вектор есть i-й столбец <math>e_{i}</math> единичной матрицы. Это означает, что <math>e_{i}</math> является i-м столбцом в матрице <math>Q_{'}</math>, следовательно при формировании матрицы <math>Q</math> применяя левое умножение <math>Q_{1}</math> на <math>Q_{2}</math> вычисление i-го столбца не будет требовать никаких затрат. Аналогичное упрощение возможно в случае <math>d_{i} = d_{i+1}</math>. При дефляции многих собственных значений устраняется большая часть работы, которая связана с матричным умножением.		Основной выигрыш от использования дефляции состоит не в том, что убыстряется решение векового уравнения - этот этап в любом случае стоит лишь <math>O(n^{2})</math> операций. Выигрыш заключается в ускорении матричного умножения на последнем шаге алгоритма. Действительно, если <math>u_{i}=0</math>, то соответствующий собственный вектор есть i-й столбец <math>e_{i}</math> единичной матрицы. Это означает, что <math>e_{i}</math> является i-м столбцом в матрице <math>Q_{'}</math>, следовательно при формировании матрицы <math>Q</math> применяя левое умножение <math>Q_{1}</math> на <math>Q_{2}</math> вычисление i-го столбца не будет требовать никаких затрат. Аналогичное упрощение возможно в случае <math>d_{i} = d_{i+1}</math>. При дефляции многих собственных значений устраняется большая часть работы, которая связана с матричным умножением.

			Далее пойдет речь о решении '''векового уравнения''', которое является одной из основных частей алгоритма.

			Предположим, что некоторое <math>u_{i}</math>, хотя и мало, все же недостаточно мало для того, чтобы была зарегистрирована дефляция. В этом случае применение метода Ньютона к решению векового уравнения встречается с затруднениями. Вспомним, что пересчет приближённого решения <math>u_{j}</math> уравнения <math>f(\lambda) = 0</math> в методе Ньютона основан на следующих положениях:

			1. Вблизи точки <math>\lambda = \lambda_{j}</math> функция <math>f(\lambda)</math> аппроксимируется линейной функцией <math>l(\lambda)</math>; график есть прямая линия, касающаяся графика функции <math>f(\lambda)</math> при <math>\lambda = \lambda_{j}</math>.

			2. В качестве <math>\lambda_{j+1}</math> берётся нуль этого линейного приближения, т.е. <math>l(\lambda_{j+1})=0</math>.

			Функция, показанная на рис.1, не доставляет видимых трудностей методу Ньютона, поскольку вблизи каждого своего нуля <math>f(\lambda)</math> достаточно хорошо аппроксимируется линейными функциями. Однако рассмотрим график функции на рис. 2. Она получена из функции на рис. 1 заменой значения .5 для <math>u_{i}^{2}</math> на .001. Это новое значение недостаточно мало для того, чтобы вызвать дефляцию. График функции в левой части рис.2 визуально не отличим от её вертикальных и горизонтальных асимптот, поэтому в правой части укрупненно воспроизведён фрагмент графика, прилегающий к вертикальной асимптоте <math>\lambda = 2</math>. Видно, что график слишком быстро "выполняет поворот" и для большей части значений <math>\lambda</math> почти горизонтален. Поэтому, применяя метод Ньютона почти к любому начальному приближению <math>\lambda_{0}</math>, мы получаем линейное приближение <math>l(\lambda)</math> с почти горизонтальным графиком и малым положительным угловым коэффициентом. В результате <math>\lambda_{1}</math> является отрицательным числом, огромным по абсолютной величине, которое совершенно бесполезно в качестве приближения к истинному корню.

			[[File:Сергеев 2.jpg\|thumb\|center\|800px\|Рис. 2. График функции <math> f(\lambda) = 1 + \frac{10^{-3}}{1 - \lambda} + \frac{10^{-3}}{2 - \lambda} + \frac{10^{-3}}{3 - \lambda} + \frac{10^{-3}}{4 - \lambda}</math>]]

			Чтобы найти выход из этого положения, можно модифицировать метод Ньютона следующим образом: раз <math>f(\lambda)</math> нельзя хорошо приблизить линейной функцией <math>l(\lambda)</math>, попробуем взять в качестве приближения какую-нибудь другую простую функцию <math>h(\lambda)</math>. Нет ничего особого именно в прямых линиях: для метода Ньютона вместо <math>l(\lambda)</math> можно взять любое приближение <math>h(\lambda)</math>, значения и нули которого легко вычисляются. Функция <math>f(\lambda)</math> имеет полюсы в точках <math>d_{i}</math> и <math>d_{i+1}</math>, которые определяют её поведение в соответствующих окрестностях. Поэтому при поиске корня в интервале <math>(d_{i+1}, d_{i})</math> естественно выбрать функцию <math>h(\lambda)</math>, также имеющую эти полюсы, т.е. функцию вида
			<math>h(\lambda)= \frac{c_{1}}{d_{i}-\lambda} + \frac{c_{2}}{d_{i+1}-\lambda} + c_{3}</math>

			Константы <math>c_{1},c_{2}</math> и <math>c_{3}</math> обеспечивающие, что <math>h(\lambda)</math> есть приближение к <math>f(\lambda)</math>, можно выбрать несколькими способами. Отметим, что если <math>c_{1},c_{2}</math> и <math>c_{3}</math> уже известны, то уравнение <math>h(\lambda)=0</math> легко решается относительно <math>\lambda</math>, поскольку сводится к эквивалентному квадратному уравнению
			<math>c_{1}(d_{i+1}-\lambda)+c_{2}(d_{i}-\lambda)+c_{3}(d_{i}-\lambda)(d_{i+1}-\lambda)=0</math>

			Пусть <math>\lambda_{j}</math> - приближённое значение корня. определим <math>c_{1},c_{2}</math> и <math>c_{3}</math> так, чтобы
			<math>\frac{c_{1}}{d_{i}-\lambda} + \frac{c_{2}}{d_{i+1}-\lambda} + c_{3} = h(\lambda) \approx f(\lambda) = 1 + \rho \sum_{k=1, n} \frac{u_{k}^{2}} {d_{k}-\lambda} </math>
			для <math>\lambda</math> в окрестности <math>\lambda_{j}</math>. Заметим, что
			<math>f(\lambda) = 1 + \rho \sum_{k=1, i} \frac{u_{k}^{2}} {d_{k}-\lambda} + \rho \sum_{k=i+1, n} \frac{u_{k}^{2}} {d_{k}-\lambda} \equiv 1 + \psi_{1}(\lambda) + \psi_{2}(\lambda)</math>.

			Если <math>\lambda \in (d_{i+1},d_{i})</math>, то <math>\psi_{1}(\lambda)</math> есть сумма положительных слагаемых, а <math>\psi_{2}(\lambda)</math> - сумма отрицательных. Поэтому и <math>\psi_{1}(\lambda)</math>, и <math>\psi_{2}(\lambda)</math> могут быть вычислены с высокой точностью; однако при их сложении вполне вероятно взаимное уничтожение верных разрядов и потеря относительной точности в сумме. Возьмем числа <math>c_{1}</math> и <math>\hat{c_{1}}</math>, такие, что функция
			<math>h_{1}(\lambda) \equiv \hat{c_{1}} + \frac{c_{1}}{d_{i}-\lambda}</math> удовлетворяет условиям <math>h_{1}(\lambda_{j}) = \psi_{1}(\lambda_{j})</math> и <math>h_{1}^{'}(\lambda_{j})=\psi_{1}^{'}(\lambda_{j})</math> (*)

			Это означает, что гипербола, являющаяся графиком функции <math>h_{1}(\lambda)</math>, касается графика функции <math>\psi_{i}(\lambda)</math> при <math>\lambda = \lambda_{j}</math>. Два условия в (*) - это обычные условия метода Ньютона, за исключением того, что вместо прямой в качестве приближения используется гипербола. Легко проверить, что <math>c_{1}=\psi_{1}^{'}(\lambda_{j})(d_{i} - \lambda_{j})^{2}</math> и <math>\hat{c_{1}}=\psi_{1}(\lambda_{j}) - \psi_{1}^{'}(\lambda_{j})(d_{i} - \lambda_{j})</math>.

			Подобным же образом выбираем <math>c_{2}</math> и <math>\hat{c_{2}}</math> так, чтобы функция
			<math>h_{2}(\lambda) \equiv \hat{c_{2}} + \frac{c_{2}}{d_{i+1}-\lambda}</math> удовлетворяла условиям
			<math>h_{2}(\lambda_{j}) = \psi_{2}(\lambda_{j})</math> и <math>h_{2}^{'}(\lambda_{j})=\psi_{2}^{'}(\lambda_{j})</math>

			Наконец, полагаем
			<math>h(\lambda) = 1 + h_{1}(\lambda) + h_{2}(\lambda) = (1 + \hat{c_{1}} + \hat{c_{2}} + \frac{c_{1}}{d_{i}-\lambda} + \frac{c_{2}}{d_{i+1}-\lambda} \equiv c_{3} + \frac{c_{1}}{d_{i}-\lambda} + \frac{c_{2}}{d_{i+1}-\lambda}</math>.

	== Вычислительное ядро алгоритма ==		== Вычислительное ядро алгоритма ==

NikoSergAlex: /* Макроструктура алгоритма */

2016-12-31T11:04:07Z

Макроструктура алгоритма

@@ Строка 132: / Строка 132: @@
 == Макроструктура алгоритма ==
 В разделе [[#Информационный граф]] описана структура алгоритма, в которой есть блок умножения матриц для вычисления собственных векторов, являющийся вычислительным ядром алгоритма. В соответствующем разделе ([[#Вычислительное ядро алгоритма]]) мы упоминали о том, что данному блоку предшествует вычисление собственных значений, которое производится [https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%9D%D1%8C%D1%8E%D1%82%D0%BE%D0%BD%D0%B0 методом Ньютона].
 == Схема реализации последовательного алгоритма ==

NikoSergAlex в 10:54, 31 декабря 2016

2016-12-31T10:54:50Z

← Предыдущая версия		Версия от 10:54, 31 декабря 2016
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment}}

	Авторы статьи: [[Участник:NikoSergAlex\|Сергеев Никита]] (группа 614) (1.1, 1.2, 1.5, 1.6, 1.7, 1.8, 1.10), [[Участница:Vika3410\|Стрельцова Виктория]] (группа 614) (1.2, 1.3, 1.4, 1.6, 1.7, 1.9, 1.10)		Авторы статьи: [[Участник:NikoSergAlex\|Сергеев Никита]] (группа 614) (1.1, 1.2, 1.5, 1.6, 1.7, 1.8, 1.10, 2.4), [[Участница:Vika3410\|Стрельцова Виктория]] (группа 614) (1.2, 1.3, 1.4, 1.6, 1.7, 1.9, 1.10, 2.4)
	{{algorithm		{{algorithm
	\| name = Метод "Разделяй и властвуй" вычисления собственных значений и векторов трёхдиагональной матрицы		\| name = Метод "Разделяй и властвуй" вычисления собственных значений и векторов трёхдиагональной матрицы
Строка 9:		Строка 9:
	крайне редко: <math> O(n^{2}) </math>		крайне редко: <math> O(n^{2}) </math>
	\| pf_width =		\| pf_width =
	\| input_data = <math> 2n - 1 </math>		\| input_data = <math> 2n + 1 </math>
	\| output_data = <math> n + ~~n^2~~ </math>		\| output_data = <math> n(n + 1) </math>
	}}		}}

NikoSergAlex: /* Входные и выходные данные алгоритма */

2016-12-31T10:51:22Z

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

← Предыдущая версия		Версия от 10:51, 31 декабря 2016
Строка 254:		Строка 254:
	'''Выходные данные''': Вектор собственных значений длины <math> n </math> и <math> n </math> собственных векторов длины <math> n </math> , соответствующих собственным значениям исходной матрицы.		'''Выходные данные''': Вектор собственных значений длины <math> n </math> и <math> n </math> собственных векторов длины <math> n </math> , соответствующих собственным значениям исходной матрицы.

	'''Объём выходных данных''': <math> ~~n + n^{2} =~~ n(n + 1) </math>		'''Объём выходных данных''': <math>n(n + 1) </math>

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

NikoSergAlex: /* Входные и выходные данные алгоритма */

2016-12-31T10:50:50Z

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

← Предыдущая версия		Версия от 10:50, 31 декабря 2016
Строка 237:		Строка 237:
	'''Входные данные''': трёхдиагональная симметрическая матрица, описанная в разделе [[#Математическое описание алгоритма]].		'''Входные данные''': трёхдиагональная симметрическая матрица, описанная в разделе [[#Математическое описание алгоритма]].

	~~'''Объём входных данных''':~~ <math> 2n - 1 </math> ~~(в силу симметричности достаточно хранить только диагональ и над/поддиагональные элементы).~~		<math>
			L = \begin{bmatrix}
			a_{1} & b_{1}&&&&& \\
			b_{1} & \ddots & \ddots \\
			& \ddots & a_{m-1} & b_{m-1} \\
			&& b_{m-1} & a_{m} & b_{m} \\
			&&& b_{m} & a_{m+1} & b_{m+1} \\
			&&&& b_{m+1} & \ddots \\
			&&&&&& \ddots & b_{n-1} \\
			&&&&&& b_{n-1} & a_{n} \\
			\end{bmatrix}
			</math>

	'''~~Выходные данные~~''': ~~матрица собственных значений размера~~ <math> 1 * n </math> и ~~матрица собственных векторов размера <math> n * n <~~/~~math>~~		'''Объём входных данных''': <math> 2n + 1 </math> (в силу симметричности достаточно хранить только диагональ и над/под диагональные элементы).

	'''Объём выходных данных''': <math> n + n^2 </math>		'''Выходные данные''': Вектор собственных значений длины <math> n </math> и <math> n </math> собственных векторов длины <math> n </math> , соответствующих собственным значениям исходной матрицы.

			'''Объём выходных данных''': <math> n + n^{2} = n(n + 1) </math>

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

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

2016-12-31T10:48:24Z

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

← Предыдущая версия		Версия от 10:48, 31 декабря 2016
Строка 221:		Строка 221:

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

	- В листьях деревьев каждый процесс занимается вычислением независимо.		- В листьях деревьев каждый процесс занимается вычислением независимо.

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

2016-12-31T10:48:04Z

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

← Предыдущая версия		Версия от 10:48, 31 декабря 2016
Строка 216:		Строка 216:

	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
	~~Данная структура~~ алгоритма ~~позволяет выполнять рекурсивный~~ вызов функций для ~~двух подматриц исходной~~ матрицы ~~как последовательно~~, ~~так и~~ параллельно.		В структуре алгоритма имеем два параллельных блока - вызов рекурсивных функций ''dc_eig'' для вычисления собственных значений и векторов матриц <math>T_{1}</math> и <math>T_{2}</math> - это единственная часть алгоритма, в которой возможно использовать параллелизм.
	~~При последовательной~~ реализации ~~алгоритма вызов функций производится по очереди~~ - сначала ~~для одной подматрицы~~, затем ~~для другой~~. ~~При параллельной~~ реализации алгоритма ~~данные функции могут отрабатывать одновременно~~.
			Рекурсивное разделение матрицы ведёт к иерархии вычислительных подблоков с графом зависимости данных, который принимает вид двоичного дерева. Такая структура является естественным путем разделения вычислений между процессорами.

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

			В случае реализации без параллелизма, функции ''dc_eig'' отрабатывают последовательно - сначала со входными параметрами <math>T_{1}, Q_{1}, \Lambda_{1}</math>, затем - <math>T_{2}, Q_{2}, \Lambda_{2}</math>.

			Таким образом, благодаря параллелизму высота алгоритма параллельного составляет <math>log_{2}(n)</math>, тогда как при последовательной реализации высота алгоритма равна сумме геометрической прогрессии <math>1+2+4+8+...+2^{n-1} = 2^{n} - 1</math>, что значительно сокращает число итераций алгоритма.

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

	При размерности матрицы больше 3 параллельная реализация позволяет сократить количество этапов работы алгоритма больше, чем в два раза.		При размерности матрицы больше 3 параллельная реализация позволяет сократить количество этапов работы алгоритма больше, чем в два раза.