Участник:Малков Кирилл/Алгоритм бидиагонализации матрицы методом отражений - История изменений

Малков Кирилл: /* Информационный граф */

2021-12-12T20:43:53Z

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

← Предыдущая версия		Версия от 20:43, 12 декабря 2021
Строка 34:		Строка 34:

	=== Информационный граф ===		=== Информационный граф ===
			Информационный граф для количества процессов равного 4.
	[[Файл:Diagram.png\|Информационный граф]]		[[Файл:Diagram.png\|Информационный граф]]
	<br><math>I-2uu^*</math> - вычисление матрицы отражения;		<br><math>I-2uu^*</math> - вычисление матрицы отражения;

Малков Кирилл: /* Программная реализация алгоритма */

2021-12-12T20:42:08Z

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

← Предыдущая версия		Версия от 20:42, 12 декабря 2021
Строка 328:		Строка 328:
	}		}
	</source>		</source>

			[[Файл:Безымянный777.png\|Результаты тестирования алгоритма на кластере ИВМ РАН]]
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	Для оптимальности работы алгоритма следует реализовать функцию умножения матрицы отражения матрицы отражения на произвольную матрицу, это заметно сократит время время его работы.		Для оптимальности работы алгоритма следует реализовать функцию умножения матрицы отражения матрицы отражения на произвольную матрицу, это заметно сократит время время его работы.
Строка 338:		Строка 340:
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	Параллельная реализация алгоритма наиболее эффективна на машинах с быстрым обменом данных меду процессами		Параллельная реализация алгоритма наиболее эффективна на машинах с быстрым обменом данных меду процессами
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

	== Литература ==		== Литература ==
	Е. Е. Тыртышников, "Методы численного анализа".		Е. Е. Тыртышников, "Методы численного анализа".

Малков Кирилл: /* Информационный граф */

2021-12-12T20:30:58Z

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

← Предыдущая версия		Версия от 20:30, 12 декабря 2021
Строка 35:		Строка 35:
	=== Информационный граф ===		=== Информационный граф ===
	[[Файл:Diagram.png\|Информационный граф]]		[[Файл:Diagram.png\|Информационный граф]]
	<br><math>I-2uu*</math> - вычисление матрицы отражения;		<br><math>I-2uu^*</math> - вычисление матрицы отражения;
	<br><math>D, P, Q</math> - умножение матрицы отражения на матрицы D, P, Q;		<br><math>D, P, Q</math> - умножение матрицы отражения на матрицы D, P, Q;
	<br><math>TRANS</math> - транспонирование матрицы D;		<br><math>TRANS</math> - транспонирование матрицы D;

Малков Кирилл: /* Информационный граф */

2021-12-12T20:30:34Z

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

← Предыдущая версия		Версия от 20:30, 12 декабря 2021
Строка 35:		Строка 35:
	=== Информационный граф ===		=== Информационный граф ===
	[[Файл:Diagram.png\|Информационный граф]]		[[Файл:Diagram.png\|Информационный граф]]
	<math>I-2uu*</math> - вычисление матрицы отражения;		<br><math>I-2uu*</math> - вычисление матрицы отражения;
	<math>D, P, Q</math> - умножение матрицы отражения на матрицы D, P, Q;		<br><math>D, P, Q</math> - умножение матрицы отражения на матрицы D, P, Q;
	<math>TRANS</math> - транспонирование матрицы D;		<br><math>TRANS</math> - транспонирование матрицы D;

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
	При параллельном вычислении двухдиагональной матрицы методом отражений требуется последовательно выполнить следующие ярусы:		При параллельном вычислении двухдиагональной матрицы методом отражений требуется последовательно выполнить следующие ярусы:

Малков Кирилл в 20:28, 12 декабря 2021

2021-12-12T20:28:53Z

Внесённые изменения

Малков Кирилл: /* Возможные способы и особенности параллельной реализации алгоритма */

2021-12-08T22:11:24Z

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

← Предыдущая версия		Версия от 22:11, 8 декабря 2021
Строка 53:		Строка 53:
	=== Локальность данных и вычислений ===		=== Локальность данных и вычислений ===
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	Алгоритм бидиагонализации матрицы довольно последователен: на каждом шаге считается матрица отражения, и распараллелить прямым образом алгоритм нельзя, поскольку каждый раз матрица отражения строится к новой матрице. Однако можно разбить Матрицу <math> D<\math> на блоки, и каждый процесс будет занят умножением матрицы отражения на соответствующий блок.		Алгоритм бидиагонализации матрицы довольно последователен: на каждом шаге считается матрица отражения, и распараллелить прямым образом алгоритм нельзя, поскольку каждый раз матрица отражения строится к новой матрице. Однако можно разбить Матрицу <math> D</math> на блоки, и каждый процесс будет занят умножением матрицы отражения на соответствующий блок.

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

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

2021-12-08T22:10:43Z

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

← Предыдущая версия		Версия от 22:10, 8 декабря 2021
Строка 42:		Строка 42:

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===
	На вход подается матрица A и ее размер n. Выходные данные -- матрицы P, Q, D, такие что <math>A = ~~P D Q~~ <\math>		На вход подается матрица <math>A</math> и ее размер <math>n</math>. Выходные данные -- матрицы <math>P, Q, D,</math> такие что <math>A = PDQ </math>

	=== Свойства алгоритма ===		=== Свойства алгоритма ===
	Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов является линейным.		Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов является линейным.

Малков Кирилл: /* Вычислительное ядро алгоритма */

2021-12-08T22:09:03Z

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

← Предыдущая версия		Версия от 22:09, 8 декабря 2021
Строка 15:		Строка 15:

	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===
	Вычислительное ядро алгоритма составляет нахождение на каждом этапе матрицы отражения(всего <math>~~2 * n~~ - 2</math>.		Вычислительное ядро алгоритма составляет нахождение на каждом этапе матрицы отражения(всего <math>2n - 2</math>).

	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===
	Операции скалярного произведения, умножения матрицы на вектор		Операции скалярного произведения, умножения матрицы на вектор

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

2021-12-08T22:07:57Z

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

← Предыдущая версия		Версия от 22:07, 8 декабря 2021
Строка 12:		Строка 12:
	<br><math>u_i = \frac{[0, 0, ..., 0, d_{i+1} - \|\|d_{i+1}\|\|_2, d_{i+2}, ..., d_n]}{\|\|[0, 0, ..., 0, d_{i+1} - \|\|d_{i+1}\|\|_2, d_{i+2}, ..., d_n]\|\|_2}, Q_i = (I - 2 * u_{i} * u_{i}^) Q_{i-1}, P_i = P_{i-1}.</math>		<br><math>u_i = \frac{[0, 0, ..., 0, d_{i+1} - \|\|d_{i+1}\|\|_2, d_{i+2}, ..., d_n]}{\|\|[0, 0, ..., 0, d_{i+1} - \|\|d_{i+1}\|\|_2, d_{i+2}, ..., d_n]\|\|_2}, Q_i = (I - 2 * u_{i} * u_{i}^) Q_{i-1}, P_i = P_{i-1}.</math>
	<br>Если <math>i</math> нечетное, то <math>D_i = (I - 2 * u_{i-1} * u_{i-1}^) D_{i-1},</math>		<br>Если <math>i</math> нечетное, то <math>D_i = (I - 2 * u_{i-1} * u_{i-1}^) D_{i-1},</math>
	<br<math>u_i = \frac{[0, 0, ..., 0, d_i - \|\|d_i\|\|_2, d_{i+1}, ..., d_n]}{\|\|[0, 0, ..., 0, d_i - \|\|d_i\|\|_2, d_{i+1}, ..., d_n]\|\|_2}, Q_i = Q_{i-1}, P_i = P_{i-1} * (I - 2 * u_{i} * u_{i}^*).</math>		<br><math>u_i = \frac{[0, 0, ..., 0, d_i - \|\|d_i\|\|_2, d_{i+1}, ..., d_n]}{\|\|[0, 0, ..., 0, d_i - \|\|d_i\|\|_2, d_{i+1}, ..., d_n]\|\|_2}, Q_i = Q_{i-1}, P_i = P_{i-1} * (I - 2 * u_{i} * u_{i}^*).</math>

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

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

2021-12-08T22:07:30Z

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

← Предыдущая версия		Версия от 22:07, 8 декабря 2021
Строка 5:		Строка 5:
	где <math>P</math> и <math>Q</math> - произведения конечного числа матриц отражения(или вращения).		где <math>P</math> и <math>Q</math> - произведения конечного числа матриц отражения(или вращения).
	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===
	Пусть дана матрица A размера <math>n \times n</math>. Вычисляется бидиагональная матрица D размера <math>n \times n</math>, такая что <math>A = PDQ</math> для некоторых матриц </math>P и Q, являющихся произведением некоторого числа матриц отражения.Сначала мы умножаем A слева на матрицу отражения, аннулирующую все поддиагональные элементы первого столбца. Затем умножаем результат справа на матрицу отражения, аннулирующую элементы первой строки в позициях с 3-й по n-ю. Далее умножением слева аннулируем все поддиагональные элементы второго столбца, затем умножением справа аннулируем получаем нули во второй строке в позициях с 4-й по n-ю и т.д. После каждого умножения на матрицу отражения все ранее полученные нули остаются.		Пусть дана матрица <math>A</math> размера <math>n \times n</math>. Вычисляется бидиагональная матрица <math>D</math> размера <math>n \times n</math>, такая что <math>A = PDQ</math> для некоторых матриц <math>P</math> и <math>Q</math>, являющихся произведением некоторого числа матриц отражения.Сначала мы умножаем A слева на матрицу отражения, аннулирующую все поддиагональные элементы первого столбца. Затем умножаем результат справа на матрицу отражения, аннулирующую элементы первой строки в позициях с 3-й по n-ю. Далее умножением слева аннулируем все поддиагональные элементы второго столбца, затем умножением справа аннулируем получаем нули во второй строке в позициях с 4-й по n-ю и т.д. После каждого умножения на матрицу отражения все ранее полученные нули остаются.
	Формулы метода:		Формулы метода:
	Пусть <math>A = [a_1, a_2, ..., a_n]</math>		Пусть <math>A = [a_1, a_2, ..., a_n],</math>
	<math>D_1 = A, P_1 = I, Q_1 = I.</math>		<math>D_1 = A, P_1 = I, Q_1 = I.</math>
	<math>~~Если~~ i четное, то D_i = D_{i-1} * (I - 2 * u_{i-1} * u_{i-1}^*)</math>		<br>Если <math>i</math> четное, то <math>D_i = D_{i-1} * (I - 2 * u_{i-1} * u_{i-1}^*)</math>
	<math>u_i = \frac{[0, 0, ..., 0, d_{i+1} - \|\|d_{i+1}\|\|_2, d_{i+2}, ..., d_n]}{\|\|[0, 0, ..., 0, d_{i+1} - \|\|d_{i+1}\|\|_2, d_{i+2}, ..., d_n]\|\|_2}, Q_i = (I - 2 * u_{i} * u_{i}^) Q_{i-1}, P_i = P_{i-1}.</math>		<br><math>u_i = \frac{[0, 0, ..., 0, d_{i+1} - \|\|d_{i+1}\|\|_2, d_{i+2}, ..., d_n]}{\|\|[0, 0, ..., 0, d_{i+1} - \|\|d_{i+1}\|\|_2, d_{i+2}, ..., d_n]\|\|_2}, Q_i = (I - 2 * u_{i} * u_{i}^) Q_{i-1}, P_i = P_{i-1}.</math>
	<math>~~Если~~ i нечетное, то D_i = (I - 2 * u_{i-1} * u_{i-1}^) D_{i-1},</math>		<br>Если <math>i</math> нечетное, то <math>D_i = (I - 2 * u_{i-1} * u_{i-1}^) D_{i-1},</math>
	<math>u_i = \frac{[0, 0, ..., 0, d_i - \|\|d_i\|\|_2, d_{i+1}, ..., d_n]}{\|\|[0, 0, ..., 0, d_i - \|\|d_i\|\|_2, d_{i+1}, ..., d_n]\|\|_2}, Q_i = Q_{i-1}, P_i = P_{i-1} * (I - 2 * u_{i} * u_{i}^*).</math>		<br<math>u_i = \frac{[0, 0, ..., 0, d_i - \|\|d_i\|\|_2, d_{i+1}, ..., d_n]}{\|\|[0, 0, ..., 0, d_i - \|\|d_i\|\|_2, d_{i+1}, ..., d_n]\|\|_2}, Q_i = Q_{i-1}, P_i = P_{i-1} * (I - 2 * u_{i} * u_{i}^*).</math>

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