Итерация алгоритма dqds - История изменений

ASA в 06:49, 8 июля 2022

2022-07-08T06:49:40Z

← Предыдущая версия		Версия от 06:49, 8 июля 2022
Строка 179:		Строка 179:

	Сам алгоритм dqds реализован в функции xBDSQR пакета LAPACK и используется при её вызове без расчёта сингулярных векторов.		Сам алгоритм dqds реализован в функции xBDSQR пакета LAPACK и используется при её вызове без расчёта сингулярных векторов.

			=== Результаты прогонов ===

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

ASA в 06:48, 8 июля 2022

2022-07-08T06:48:30Z

@@ Строка 173: / Строка 173: @@
 Как говорилось в [[#Схема реализации последовательного алгоритма|cхеме реализации последовательного алгоритма]], вычисляемые данные записываются сразу на место входных.
 === Возможные способы и особенности параллельной реализации алгоритма ===
@@ Строка 204: / Строка 178: @@
 Итерация dqds практически полностью последовательна. Единственная возможность - одновременное выполнение операции умножения (2.3) и операции (2.4) умножения и сложения, что дает небольшой выигрыш в производительности.
-=== Масштабируемость алгоритма и его реализации ===
+Сам алгоритм dqds реализован в функции xBDSQR пакета LAPACK и используется при её вызове без расчёта сингулярных векторов.
 === Выводы для классов архитектур ===
 Эффективное выполнение алгоритма возможно только на вычислительных устройствах с одним или двумя ядрами.
 == Литература ==

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

2022-04-28T11:48:18Z

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

← Предыдущая версия		Версия от 11:48, 28 апреля 2022
Строка 225:		Строка 225:
	[[file:DQDS eff.png\|thumb\|center\|700px\|Рисунок 9. Параллельная реализация алгоритма dqds. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]		[[file:DQDS eff.png\|thumb\|center\|700px\|Рисунок 9. Параллельная реализация алгоритма dqds. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]

	[~~http~~://~~git~~.~~algowiki-project~~.~~org~~/~~Teplov~~/Scalability/tree/master/DQDS/dqds.c Исследованная параллельная реализация на языке C]		[https://gitlab.srcc.msu.ru/alex-teplov/Scalability/tree/master/DQDS/dqds.c Исследованная параллельная реализация на языке C]

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

ASA в 12:19, 14 марта 2018

2018-03-14T12:19:58Z

← Предыдущая версия		Версия от 12:19, 14 марта 2018
Строка 240:		Строка 240:
	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]

	[[En:~~The~~ dqds algorithm ~~iteration~~]]		[[En:One step of the dqds algorithm]]

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

2017-10-29T06:44:26Z

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

← Предыдущая версия		Версия от 06:44, 29 октября 2017
Строка 158:		Строка 158:
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===

	Алгоритм на языке Matlab может быть ~~записать~~ так:		Алгоритм на языке Matlab может быть записан так:
	<source lang="matlab">		<source lang="matlab">

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

2017-10-28T13:53:05Z

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

← Предыдущая версия		Версия от 13:53, 28 октября 2017
Строка 95:		Строка 95:
	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===

	Алгоритм состоит из отдельного вычисления начального значения вспомогательной переменной <math>d,</math> ~~последующим~~ (n-1)-~~кратным выполнением~~ повторяющейся последовательности из 5 операций (+,/,,,-) для вычисления квадратов диагональных (<math>\widehat{q}_j</math>) и внедиагональных (<math>\widehat{e}_k</math>) элементов выходной матрицы и завершающего ~~вычислением~~ крайнего значения <math>\widehat{q}_n</math>.		Алгоритм состоит из отдельного вычисления начального значения вспомогательной переменной <math>d,</math> последующего (n-1)-кратного выполнения повторяющейся последовательности из 5 операций (+,/,,,-) для вычисления квадратов диагональных (<math>\widehat{q}_j</math>) и внедиагональных (<math>\widehat{e}_k</math>) элементов выходной матрицы и завершающего вычисления крайнего значения <math>\widehat{q}_n</math>.

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

Ikramov: /* Вспомогательные сведения */

2017-10-28T12:35:07Z

Вспомогательные сведения

← Предыдущая версия		Версия от 12:35, 28 октября 2017
Строка 40:		Строка 40:
	\widehat{b}^2_j = b^2_j\dot (a^2_{j+1}/a^2_j)		\widehat{b}^2_j = b^2_j\dot (a^2_{j+1}/a^2_j)
	</math>		</math>
	и вычислению <math>\widehat{a}^2_n = a^2_n-\widehat{b}^2_{n-1}-\delta.</math> Очевидно, что работу с извлечением ~~квадратов~~ выгодно вести лишь после окончания работы алгоритма, поэтому можно ввести замену <math>q_j=a^2_j,\; e_j=b^2,</math> что в итоге приводит к так называемому алгоритму qds.		и вычислению <math>\widehat{a}^2_n = a^2_n-\widehat{b}^2_{n-1}-\delta.</math> Очевидно, что работу с извлечением квадратных корней выгодно вести лишь после окончания работы алгоритма, поэтому можно ввести замену <math>q_j=a^2_j,\; e_j=b^2,</math> что в итоге приводит к так называемому алгоритму qds.
	Формулы алгоритма следующие:		Формулы алгоритма следующие:

Ikramov: /* Вспомогательные сведения */

2017-10-28T12:29:50Z

Вспомогательные сведения

← Предыдущая версия		Версия от 12:29, 28 октября 2017
Строка 55:		Строка 55:


	Здесь <math>q_j, \; j \in [1,n]</math> и <math>e_j, \; j \in [1,n-1]</math> - квадраты ~~элемнтов~~ главной и верхней побочной диагонали соответственно. Крышка означает выходные переменные, а		Здесь <math>q_j, \; j \in [1,n]</math> и <math>e_j, \; j \in [1,n-1]</math> - квадраты элементов главной и верхней побочной диагонали соответственно. Крышка означает выходные переменные, а

	<math>\delta</math> - сдвиг (параметр алгоритма).		<math>\delta</math> - сдвиг (параметр алгоритма).

Ikramov: /* Вспомогательные сведения */

2017-10-28T08:15:21Z

Вспомогательные сведения

← Предыдущая версия		Версия от 08:15, 28 октября 2017
Строка 27:		Строка 27:
	==== Вспомогательные сведения ====		==== Вспомогательные сведения ====
	Для понимания математических основ dqds-итерации полезно рассмотреть кратко её вывод, частично отражающий и историю возникновения алгоритма (подробности можно найти в <ref name="vla"/>).		Для понимания математических основ dqds-итерации полезно рассмотреть кратко её вывод, частично отражающий и историю возникновения алгоритма (подробности можно найти в <ref name="vla"/>).
	За основу dqds-алгоритма удобно взять так называемую LR-итерацию, предшествующую хорошо-известной QR-итерации. LR-алгоритм, начиная с входной положительно определенной матрицы <math>T_0>0,</math> строит сходящуюся последовательность подобных <math>T_0</math> матриц <math>T_i>0,</math> итерационно используя следующие три шага:		За основу dqds-алгоритма удобно взять так называемую LR-итерацию, предшествующую хорошо-известной QR-итерации. LR-алгоритм, начиная с входной симметричной и положительно определенной матрицы <math>T_0>0,</math> строит сходящуюся последовательность подобных <math>T_0</math> матриц <math>T_i>0,</math> итерационно используя следующие три шага:
	#Выбрать сдвиг <math>\tau_i</math> меньший младшего собственного значения <math>T_i.</math>		#Выбрать сдвиг <math>\tau_i</math> меньший младшего собственного значения <math>T_i.</math>
	#Вычислить разложение Холецкого <math>T_i-\tau^2_iI=B_i^TB_i,</math> где <math>B_i</math> - верхняя треугольная матрица с положительной диагональю.		#Вычислить разложение Холецкого <math>T_i-\tau^2_iI=B_i^TB_i,</math> где <math>B_i</math> - верхняя треугольная матрица с положительной диагональю.

Ikramov: /* Вспомогательные сведения */

2017-10-28T08:07:05Z

Вспомогательные сведения

← Предыдущая версия		Версия от 08:07, 28 октября 2017
Строка 27:		Строка 27:
	==== Вспомогательные сведения ====		==== Вспомогательные сведения ====
	Для понимания математических основ dqds-итерации полезно рассмотреть кратко её вывод, частично отражающий и историю возникновения алгоритма (подробности можно найти в <ref name="vla"/>).		Для понимания математических основ dqds-итерации полезно рассмотреть кратко её вывод, частично отражающий и историю возникновения алгоритма (подробности можно найти в <ref name="vla"/>).
	За основу dqds-алгоритма удобно взять так называемую LR-итерацию, предшествующую хорошо-известной QR-итерации. LR-алгоритм, начиная с входной матрицы <math>T_0>0,</math> строит сходящуюся последовательность подобных <math>T_0</math> матриц <math>T_i>0,</math> итерационно используя следующие три шага:		За основу dqds-алгоритма удобно взять так называемую LR-итерацию, предшествующую хорошо-известной QR-итерации. LR-алгоритм, начиная с входной положительно определенной матрицы <math>T_0>0,</math> строит сходящуюся последовательность подобных <math>T_0</math> матриц <math>T_i>0,</math> итерационно используя следующие три шага:
	#Выбрать сдвиг <math>\tau_i</math> меньший младшего собственного значения <math>T_i.</math>		#Выбрать сдвиг <math>\tau_i</math> меньший младшего собственного значения <math>T_i.</math>
	#Вычислить разложение Холецкого <math>T_i-\tau^2_iI=B_i^TB_i,</math> где <math>B_i</math> - верхняя треугольная матрица с положительной диагональю.		#Вычислить разложение Холецкого <math>T_i-\tau^2_iI=B_i^TB_i,</math> где <math>B_i</math> - верхняя треугольная матрица с положительной диагональю.