Участник:Sergey.protserov/Метод Якоби решения СЛАУ - История изменений

Sergey.protserov: /* Информационный граф */

2019-12-02T19:59:29Z

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

← Предыдущая версия		Версия от 19:59, 2 декабря 2019
Строка 80:		Строка 80:

	=== Информационный граф ===		=== Информационный граф ===
	Граф пятого шага алгоритма в случае матрицы порядка <math>2</math>. Здесь <math>B = D^{-1}A</math>, <math>c = D^{-1}f</math>. Квадратами обозначены данные (элементы матриц и векторов, стоящие в указанных в скобках позициях), кругами обозначены операции, ~~пунктирными линиями~~ обозначены перезаписи данных (переход от <math>y^{n}</math> к <math>y^{n+1}</math> в ходе итераций), ~~элементы данных~~ и ~~идущие от них стрелки нарисованы разными цветами~~ для ~~наглядности~~.		Граф пятого шага алгоритма в случае матрицы порядка <math>4</math>. Здесь <math>B = D^{-1}A</math>, <math>c = D^{-1}f</math>. Квадратами обозначены данные (элементы матриц и векторов, стоящие в указанных в скобках позициях), кругами обозначены операции, рыжими стрелками обозначены перезаписи данных (переход от <math>y^{n}</math> к <math>y^{n+1}</math> в ходе итераций), зелёным цветом обозначена операция умножения матрицы на вектор (см. её информационный граф в статье <ref name="AW_0">https://algowiki-project.org/ru/%D0%A3%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BB%D0%BE%D1%82%D0%BD%D0%BE%D0%B9_%D0%BD%D0%B5%D0%BE%D1%81%D0%BE%D0%B1%D0%B5%D0%BD%D0%BD%D0%BE%D0%B9_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D1%8B_%D0%BD%D0%B0_%D0%B2%D0%B5%D0%BA%D1%82%D0%BE%D1%80_(%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B2%D0%B5%D1%89%D0%B5%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B2%D0%B0%D1%80%D0%B8%D0%B0%D0%BD%D1%82)#.D0.98.D0.BD.D1.84.D0.BE.D1.80.D0.BC.D0.B0.D1.86.D0.B8.D0.BE.D0.BD.D0.BD.D1.8B.D0.B9_.D0.B3.D1.80.D0.B0.D1.84</ref>), её операнды и результат. Пунктиром обозначен временный вектор, введённый для удобства построения графа алгоритма (он может отсутствовать в реализации).
	[[File:S_P_Jacobi_Algo_graph.png]]		[[File:S_P_Jacobi_Algo_graph.png]]

Sergey.protserov: += имя автора

2019-12-01T12:56:18Z

+= имя автора

← Предыдущая версия		Версия от 12:56, 1 декабря 2019
Строка 1:		Строка 1:
			Автор статьи: Процеров Сергей Дмитриевич, 407 группа ВМК МГУ
	== Свойства и структура алгоритмов ==		== Свойства и структура алгоритмов ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

Sergey.protserov: += заголовки разделов

2019-12-01T12:42:38Z

+= заголовки разделов

← Предыдущая версия		Версия от 12:42, 1 декабря 2019
Строка 93:		Строка 93:
	Выходные данные:		Выходные данные:
	# Вещественный <math>m</math>-мерный вектор приближённого решения <math>y^{n_{max}}</math>		# Вещественный <math>m</math>-мерный вектор приближённого решения <math>y^{n_{max}}</math>

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

	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
			=== Особенности реализации последовательного алгоритма ===
			=== Локальность данных и вычислений ===
			=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	Зависимость времени работы алгоритма (100 итераций) в секундах от порядка входной матрицы и количества MPI-процессов:		Зависимость времени работы алгоритма (100 итераций) в секундах от порядка входной матрицы и количества MPI-процессов:
Строка 149:		Строка 154:

	Из приведённых данных видна хорошая слабая масштабируемость алгоритма, а так же тот факт, что увеличение числа процессов с 32 до 64 при входной матрице порядка 2500 уже не даёт значительного выигрыша во времени работы, т.е., что сильная масштабируемость с некоторого момента начинает падать. В исследуемой реализации не осуществляется распараллеливание шагов 2 и 4 алгоритма, т.к. ожидалось, что распределение выполнения <math>2m</math> операций по процессам не принесёт значительного выигрыша из-за издержек на пересылки множества малых порций данных, а эксперимент показал, что во всех рассмотренных случаях временные затраты на выполнение шагов 2 и 4 в совокупности не превышают <math>4 \cdot 10^{-4}</math> секунд.		Из приведённых данных видна хорошая слабая масштабируемость алгоритма, а так же тот факт, что увеличение числа процессов с 32 до 64 при входной матрице порядка 2500 уже не даёт значительного выигрыша во времени работы, т.е., что сильная масштабируемость с некоторого момента начинает падать. В исследуемой реализации не осуществляется распараллеливание шагов 2 и 4 алгоритма, т.к. ожидалось, что распределение выполнения <math>2m</math> операций по процессам не принесёт значительного выигрыша из-за издержек на пересылки множества малых порций данных, а эксперимент показал, что во всех рассмотренных случаях временные затраты на выполнение шагов 2 и 4 в совокупности не превышают <math>4 \cdot 10^{-4}</math> секунд.

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

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

Sergey.protserov: /* Информационный граф */

2019-11-29T18:47:26Z

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

← Предыдущая версия		Версия от 18:47, 29 ноября 2019
Строка 79:		Строка 79:

	=== Информационный граф ===		=== Информационный граф ===
	Граф пятого шага алгоритма в случае матрицы порядка <math>2</math>. Здесь <math>B = D^{-1}A</math>, <math>c = D^{-1}f</math>.		Граф пятого шага алгоритма в случае матрицы порядка <math>2</math>. Здесь <math>B = D^{-1}A</math>, <math>c = D^{-1}f</math>. Квадратами обозначены данные (элементы матриц и векторов, стоящие в указанных в скобках позициях), кругами обозначены операции, пунктирными линиями обозначены перезаписи данных (переход от <math>y^{n}</math> к <math>y^{n+1}</math> в ходе итераций), элементы данных и идущие от них стрелки нарисованы разными цветами для наглядности.
	[[File:S_P_Jacobi_Algo_graph.png]]		[[File:S_P_Jacobi_Algo_graph.png]]

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

2019-11-29T11:14:50Z

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

← Предыдущая версия		Версия от 11:14, 29 ноября 2019
Строка 151:		Строка 151:

	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===
	~~Авторам~~ статьи не известно о существовании хороших реализаций данного алгоритма.		Автору статьи не известно о существовании хороших реализаций данного алгоритма.

	== Литература ==		== Литература ==
	<references />		<references />

Sergey.protserov: fix algo graph

2019-11-29T11:06:31Z

fix algo graph

← Предыдущая версия		Версия от 11:06, 29 ноября 2019
Строка 79:		Строка 79:

	=== Информационный граф ===		=== Информационный граф ===
	Граф пятого шага алгоритма:		Граф пятого шага алгоритма в случае матрицы порядка <math>2</math>. Здесь <math>B = D^{-1}A</math>, <math>c = D^{-1}f</math>.
	[[File:S_P_Jacobi_Algo_graph.png]]		[[File:S_P_Jacobi_Algo_graph.png]]

	'''MM''' обозначает матричное умножение (конкретно — умножение матрицы на вектор), '''SUB''' — вычитание векторов, '''ADD''' — сложение векторов.

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

Sergey.protserov: minor fixes

2019-11-28T17:44:24Z

minor fixes

← Предыдущая версия		Версия от 17:44, 28 ноября 2019
Строка 29:		Строка 29:
	</math>, <math>\det A \ne 0</math>.		</math>, <math>\det A \ne 0</math>.

			Достаточным условием сходимости метода является свойство строгого диагонального преобладания у матрицы <math>A</math>. <ref name="BR">Bagnara, Roberto. (2001). A Unified Proof For The Convergence Of Jacobi And Gauss-Seidel Methods. SIAM Review. 37. 10.1137/1037008. </ref>

			=== Математическое описание алгоритма ===
	Каноническая форма одношагового стационарного итерационного метода имеет вид <ref name="MVAAVG">Абакумов М. В., Гулин А.В. Лекции по численным методам математической физики. - Москва: ИНФРА-М, 2013. - 61 с. </ref>:		Каноническая форма одношагового стационарного итерационного метода имеет вид <ref name="MVAAVG">Абакумов М. В., Гулин А.В. Лекции по численным методам математической физики. - Москва: ИНФРА-М, 2013. - 61 с. </ref>:
	<math>		<math>
Строка 38:		Строка 41:
	В методе Якоби <math>\tau = 1</math>, <math>B = D</math>, где <math>D</math> — диагональная матрица, элементы которой совпадают с элементами, стоящими на главной диагонали матрицы <math>A</math>.		В методе Якоби <math>\tau = 1</math>, <math>B = D</math>, где <math>D</math> — диагональная матрица, элементы которой совпадают с элементами, стоящими на главной диагонали матрицы <math>A</math>.

	Достаточным условием сходимости метода является свойство строгого диагонального преобладания у матрицы <math>A</math>. <ref name="BR">Bagnara, Roberto. (2001). A Unified Proof For The Convergence Of Jacobi And Gauss-Seidel Methods. SIAM Review. 37. 10.1137/1037008. </ref>		Выражение для <math>y^{n+1}</math> через <math>y^{n}</math>:

	~~=== Математическое описание алгоритма ===~~
	~~В обозначениях предыдущего пункта выражение~~ для <math>y^{n+1}</math> через <math>y^{n}</math>:
	<math>y^{n+1} = D^{-1}\left(D-A\right)y^{n} + D^{-1}f</math>.		<math>y^{n+1} = D^{-1}\left(D-A\right)y^{n} + D^{-1}f</math>.

Строка 58:		Строка 58:
	# вычисление <math>D^{-1}A</math>		# вычисление <math>D^{-1}A</math>
	# вычисление <math>D^{-1}f</math>		# вычисление <math>D^{-1}f</math>
	# вычисление <math>y^{n+1} = ~~\left(I~~ - D^{-1}~~A\right)y~~^{n} + D^{-1}f</math>		# вычисление <math>y^{n+1} = y^{n} - D^{-1}Ay^{n} + D^{-1}f</math>

	Макрооперации 1-3 выполняются единожды, и в силу того, что матрица <math>D</math> — диагональная, занимают лишь незначительную часть времени работы алгоритма.		Макрооперации 1-3 выполняются единожды, и в силу того, что матрица <math>D</math> — диагональная, занимают лишь незначительную часть времени работы алгоритма.
Строка 71:		Строка 71:
	# вычислить <math>D^{-1}A</math>		# вычислить <math>D^{-1}A</math>
	# вычислить <math>D^{-1}f</math>		# вычислить <math>D^{-1}f</math>
	# выполнять вычисления по формуле <math>y^{n+1} = ~~\left(I~~ - D^{-1}~~A\right)y~~^{n} + D^{-1}f~~</math>~~, ~~<math>~~n = 0,\,1,\,\dots,\,n_{max}</math>		# выполнять вычисления по формуле <math>y^{n+1} = y^{n} - D^{-1}Ay^{n} + D^{-1}f,\quad n = 0,\,1,\,\dots,\,n_{max}</math>

	При этом на <math>n</math>-ом шаге итераций необходимо хранить оба вектора <math>y^{n}</math>, <math>y^{n+1}</math>.		При этом на <math>n</math>-ом шаге итераций необходимо хранить оба вектора <math>y^{n}</math>, <math>y^{n+1}</math>.

Sergey.protserov: += 1.7

2019-11-28T17:26:46Z

+= 1.7

← Предыдущая версия		Версия от 17:26, 28 ноября 2019
Строка 77:		Строка 77:
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===
	Шаг 2 предыдущего пункта требует выполнения <math>m</math> операций деления вещественных чисел, шаг 3 (с учётом того, что матрица <math>D^{-1}</math> — диагональная) требует выполнения <math>m^{2}</math> операций умножения вещественных чисел, аналогично шаг 4 требует <math>m</math> операций умножения, а каждая итерация шага 5 требует <math>m^{2}</math> умножений и <math>m^{2} + 2m</math> сложений/вычитаний.		Шаг 2 предыдущего пункта требует выполнения <math>m</math> операций деления вещественных чисел, шаг 3 (с учётом того, что матрица <math>D^{-1}</math> — диагональная) требует выполнения <math>m^{2}</math> операций умножения вещественных чисел, аналогично шаг 4 требует <math>m</math> операций умножения, а каждая итерация шага 5 требует <math>m^{2}</math> умножений и <math>m^{2} + 2m</math> сложений/вычитаний.

			=== Информационный граф ===
			Граф пятого шага алгоритма:
			[[File:S_P_Jacobi_Algo_graph.png]]

			'''MM''' обозначает матричное умножение (конкретно — умножение матрицы на вектор), '''SUB''' — вычитание векторов, '''ADD''' — сложение векторов.

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
Строка 145:		Строка 151:

	Из приведённых данных видна хорошая слабая масштабируемость алгоритма, а так же тот факт, что увеличение числа процессов с 32 до 64 при входной матрице порядка 2500 уже не даёт значительного выигрыша во времени работы, т.е., что сильная масштабируемость с некоторого момента начинает падать. В исследуемой реализации не осуществляется распараллеливание шагов 2 и 4 алгоритма, т.к. ожидалось, что распределение выполнения <math>2m</math> операций по процессам не принесёт значительного выигрыша из-за издержек на пересылки множества малых порций данных, а эксперимент показал, что во всех рассмотренных случаях временные затраты на выполнение шагов 2 и 4 в совокупности не превышают <math>4 \cdot 10^{-4}</math> секунд.		Из приведённых данных видна хорошая слабая масштабируемость алгоритма, а так же тот факт, что увеличение числа процессов с 32 до 64 при входной матрице порядка 2500 уже не даёт значительного выигрыша во времени работы, т.е., что сильная масштабируемость с некоторого момента начинает падать. В исследуемой реализации не осуществляется распараллеливание шагов 2 и 4 алгоритма, т.к. ожидалось, что распределение выполнения <math>2m</math> операций по процессам не принесёт значительного выигрыша из-за издержек на пересылки множества малых порций данных, а эксперимент показал, что во всех рассмотренных случаях временные затраты на выполнение шагов 2 и 4 в совокупности не превышают <math>4 \cdot 10^{-4}</math> секунд.

	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===
	Авторам статьи не известно о существовании хороших реализаций данного алгоритма.		Авторам статьи не известно о существовании хороших реализаций данного алгоритма.

	== Литература ==		== Литература ==
	<references />		<references />

Sergey.protserov: += 2.4, 2.7

2019-11-28T14:48:09Z

+= 2.4, 2.7

@@ Строка 79: / Строка 79: @@
 === Ресурс параллелизма алгоритма ===
-Шаг 2 требует один ярус из <math>m</math> операций деления, шаг 3 требует BEGIN FIXME один ярус из <math>m^{2}</math> операций умножения, шаг 4 требует один ярус из <math>m</math> операций умножения, а каждая итерация шага 5 требует по <math>m</math> ярусов умножений и сложений (в каждом из ярусов — <math>m</math> операций) для выполнения умножения матрицы на вектор <ref name="AW">https://algowiki-project.org/ru/%D0%A3%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BB%D0%BE%D1%82%D0%BD%D0%BE%D0%B9_%D0%BD%D0%B5%D0%BE%D1%81%D0%BE%D0%B1%D0%B5%D0%BD%D0%BD%D0%BE%D0%B9_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D1%8B_%D0%BD%D0%B0_%D0%B2%D0%B5%D0%BA%D1%82%D0%BE%D1%80_(%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B2%D0%B5%D1%89%D0%B5%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B2%D0%B0%D1%80%D0%B8%D0%B0%D0%BD%D1%82)#.D0.A0.D0.B5.D1.81.D1.83.D1.80.D1.81_.D0.BF.D0.B0.D1.80.D0.B0.D0.BB.D0.BB.D0.B5.D0.BB.D0.B8.D0.B7.D0.BC.D0.B0_.D0.B0.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D0.B0</ref> и ещё два яруса по <math>m</math> сложений/вычитаний END FIXME, причём итерации выполняются последовательно.
+Шаг 2 требует один ярус из <math>m</math> операций деления, шаг 3 требует один ярус из <math>m^{2}</math> операций умножения, шаг 4 требует один ярус из <math>m</math> операций умножения, а каждая итерация шага 5 требует по <math>m</math> ярусов умножений и сложений (в каждом из ярусов — <math>m</math> операций) для выполнения умножения матрицы на вектор <ref name="AW">https://algowiki-project.org/ru/%D0%A3%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BB%D0%BE%D1%82%D0%BD%D0%BE%D0%B9_%D0%BD%D0%B5%D0%BE%D1%81%D0%BE%D0%B1%D0%B5%D0%BD%D0%BD%D0%BE%D0%B9_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D1%8B_%D0%BD%D0%B0_%D0%B2%D0%B5%D0%BA%D1%82%D0%BE%D1%80_(%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B2%D0%B5%D1%89%D0%B5%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B2%D0%B0%D1%80%D0%B8%D0%B0%D0%BD%D1%82)#.D0.A0.D0.B5.D1.81.D1.83.D1.80.D1.81_.D0.BF.D0.B0.D1.80.D0.B0.D0.BB.D0.BB.D0.B5.D0.BB.D0.B8.D0.B7.D0.BC.D0.B0_.D0.B0.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D0.B0</ref> и ещё два яруса по <math>m</math> сложений/вычитаний, причём итерации выполняются последовательно.
 === Входные и выходные данные алгоритма ===
@@ Строка 90: / Строка 90: @@
 # Вещественный <math>m</math>-мерный вектор приближённого решения <math>y^{n_{max}}</math>
 == Литература ==
 <references />

Sergey.protserov: fix

2019-11-28T10:10:19Z

fix

← Предыдущая версия		Версия от 10:10, 28 ноября 2019
Строка 76:		Строка 76:

	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===
	Шаг 2 предыдущего пункта требует выполнения <math>m</math> операций деления вещественных чисел, шаг 3 (с учётом того, что матрица <math>D^{-1}</math> — диагональная) требует выполнения <math>m^{2}</math> операций умножения вещественных чисел, аналогично шаг 4 требует <math>m</math> операций умножения, а каждая итерация шага 7 требует <math>m^{2}</math> умножений и <math>m^{2} + 2m</math> сложений/вычитаний.		Шаг 2 предыдущего пункта требует выполнения <math>m</math> операций деления вещественных чисел, шаг 3 (с учётом того, что матрица <math>D^{-1}</math> — диагональная) требует выполнения <math>m^{2}</math> операций умножения вещественных чисел, аналогично шаг 4 требует <math>m</math> операций умножения, а каждая итерация шага 5 требует <math>m^{2}</math> умножений и <math>m^{2} + 2m</math> сложений/вычитаний.

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
	Шаг 2 требует один ярус из <math>m</math> операций деления, шаг 3 требует BEGIN FIXME один ярус из <math>m^{2}</math> операций умножения, шаг 4 требует один ярус из <math>m</math> операций умножения, а каждая итерация шага 7 требует по <math>m</math> ярусов умножений и сложений (в каждом из ярусов — <math>m</math> операций) для выполнения умножения матрицы на вектор <ref name="AW">https://algowiki-project.org/ru/%D0%A3%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BB%D0%BE%D1%82%D0%BD%D0%BE%D0%B9_%D0%BD%D0%B5%D0%BE%D1%81%D0%BE%D0%B1%D0%B5%D0%BD%D0%BD%D0%BE%D0%B9_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D1%8B_%D0%BD%D0%B0_%D0%B2%D0%B5%D0%BA%D1%82%D0%BE%D1%80_(%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B2%D0%B5%D1%89%D0%B5%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B2%D0%B0%D1%80%D0%B8%D0%B0%D0%BD%D1%82)#.D0.A0.D0.B5.D1.81.D1.83.D1.80.D1.81_.D0.BF.D0.B0.D1.80.D0.B0.D0.BB.D0.BB.D0.B5.D0.BB.D0.B8.D0.B7.D0.BC.D0.B0_.D0.B0.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D0.B0</ref> и ещё два яруса по <math>m</math> сложений/вычитаний END FIXME, причём итерации выполняются последовательно.		Шаг 2 требует один ярус из <math>m</math> операций деления, шаг 3 требует BEGIN FIXME один ярус из <math>m^{2}</math> операций умножения, шаг 4 требует один ярус из <math>m</math> операций умножения, а каждая итерация шага 5 требует по <math>m</math> ярусов умножений и сложений (в каждом из ярусов — <math>m</math> операций) для выполнения умножения матрицы на вектор <ref name="AW">https://algowiki-project.org/ru/%D0%A3%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BB%D0%BE%D1%82%D0%BD%D0%BE%D0%B9_%D0%BD%D0%B5%D0%BE%D1%81%D0%BE%D0%B1%D0%B5%D0%BD%D0%BD%D0%BE%D0%B9_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D1%8B_%D0%BD%D0%B0_%D0%B2%D0%B5%D0%BA%D1%82%D0%BE%D1%80_(%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B2%D0%B5%D1%89%D0%B5%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B2%D0%B0%D1%80%D0%B8%D0%B0%D0%BD%D1%82)#.D0.A0.D0.B5.D1.81.D1.83.D1.80.D1.81_.D0.BF.D0.B0.D1.80.D0.B0.D0.BB.D0.BB.D0.B5.D0.BB.D0.B8.D0.B7.D0.BC.D0.B0_.D0.B0.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D0.B0</ref> и ещё два яруса по <math>m</math> сложений/вычитаний END FIXME, причём итерации выполняются последовательно.

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