QR-алгоритм, используемый в SCALAPACK - История изменений

ASA в 06:13, 9 июля 2022

2022-07-09T06:13:25Z

ASA в 06:09, 9 июля 2022

2022-07-09T06:09:01Z

← Предыдущая версия		Версия от 06:09, 9 июля 2022
Строка 90:		Строка 90:
	== Свойства алгоритма ==		== Свойства алгоритма ==

	= Программная реализация алгоритма =		== Программная реализация алгоритма ==
			=== Особенности реализации последовательного алгоритма ===
			=== Возможные способы и особенности параллельной реализации алгоритма ===
			=== Результаты прогонов ===
			=== Выводы для классов архитектур ===
			== Литература ==

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

AntonChupin в 11:37, 7 апреля 2021

2021-04-07T11:37:34Z

← Предыдущая версия		Версия от 11:37, 7 апреля 2021
Строка 96:		Строка 96:

	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]
			[[Категория:Алгоритмы для матриц]]
			[[Категория:ScaLaPACK]]

	[[en:QR algorithm as implemented in SCALAPACK]]		[[en:QR algorithm as implemented in SCALAPACK]]

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

2018-03-14T12:51:20Z

← Предыдущая версия		Версия от 12:51, 14 марта 2018
Строка 94:		Строка 94:
	= Литература =		= Литература =
	<references />		<references />

			[[Категория:Статьи в работе]]

			[[en:QR algorithm as implemented in SCALAPACK]]

Frolov в 10:00, 13 декабря 2017

2017-12-13T10:00:08Z

← Предыдущая версия		Версия от 10:00, 13 декабря 2017
Строка 1:		Строка 1:
	{{level-a}}		{{level-a}}

	'''QR-алгоритм, используемый в SCALAPACK''' - алгоритм, использующий все проверенные на настоящее время приёмы ускорения [[QR-алгоритм\|QR-алгоритма]] для несимметричных вещественных матриц. Включён своими частями в разные подпрограммы пакета SCALAPACK<ref name="SCALAEig">http://www.netlib.org/scalapack/slug/node63.html#SECTION04335100000000000000</ref>. Состоит из двух основных частей: [[Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме\|ортогонально подобного приведения матрицы к хессенберговому виду]] и [[QR-алгоритм для хессенберговой матрицы, используемый в SCALAPACK\|QR-итераций со сдвигами для хессенберговой матрицы]].		'''QR-алгоритм, используемый в SCALAPACK''' - алгоритм, использующий все проверенные на настоящее время приёмы ускорения [[QR-алгоритм\|QR-алгоритма]] для несимметричных ''вещественных'' матриц<ref>Алгоритм для неэрмитовых комплексных матриц в SCALAPACK отсутствует, есть только их приведение к хессенберговой форме</ref>. Включён своими частями в разные подпрограммы пакета SCALAPACK<ref name="SCALAEig">http://www.netlib.org/scalapack/slug/node63.html#SECTION04335100000000000000</ref>. Состоит из двух основных частей: [[Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме\|ортогонально подобного приведения матрицы к хессенберговому виду]] и [[QR-алгоритм для хессенберговой матрицы, используемый в SCALAPACK\|QR-итераций со сдвигами для хессенберговой матрицы]].

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

Frolov: /* Обнуление поддиагональных элементов (дефляция) */

2017-12-12T15:17:39Z

Обнуление поддиагональных элементов (дефляция)

← Предыдущая версия		Версия от 15:17, 12 декабря 2017
Строка 69:		Строка 69:
	Чтобы не выполнять итерации в комплексной арифметике, выполняют т.н. неявный двойной сдвиг, давно описанный в литературе<ref name="VOLA" /><ref name = "Dem" />. При этом используются двусторонние подобные операции Хаусхолдера (отражения) 3го порядка. На первом шаге итерации формируют у хессенберговой формы выступ размера 2х2, а на последующих шагах с их же помощью выступ вытесняют вправо вниз.		Чтобы не выполнять итерации в комплексной арифметике, выполняют т.н. неявный двойной сдвиг, давно описанный в литературе<ref name="VOLA" /><ref name = "Dem" />. При этом используются двусторонние подобные операции Хаусхолдера (отражения) 3го порядка. На первом шаге итерации формируют у хессенберговой формы выступ размера 2х2, а на последующих шагах с их же помощью выступ вытесняют вправо вниз.

	==== Обнуление поддиагональных элементов (дефляция) ====		==== Обнуление поддиагональных элементов (дефляция) и распараллеливание по блокам ====

	После того, как под диагональю какой-либо элемент становится менее порогового значения, его можно считать равным нулю. Это даёт возможность применить разделение диагональных блоков матрицы, соседствующих с ним, и раздельное вычисление их собственных чисел. Этот приём называется '''дефляцией'''.		После того, как под диагональю какой-либо элемент становится менее порогового значения, его можно считать равным нулю. Это даёт возможность применить разделение диагональных блоков матрицы, соседствующих с ним, и раздельное вычисление их собственных чисел. Этот приём называется '''дефляцией'''.
			Благодаря обнулению поддиагональных элементов далее нахождение собственных чисел разделённых этими нулями хессенберговых блоков, расположенных на диагонали блочно-треугольной формы, можно производить раздельно. Если в библиотеке LAPACK, предшествующей библиотеке SCALAPACK, на каждой из итераций обрабатывался текущий диагональный блок максимальных размеров, то в алгоритме, используемом в SCALAPACK, все блоки размера больше, чем 3, обрабатываются на очередной итерации параллельно, что позволило ускорить процесс.

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

Frolov: /* Математическое описание */

2017-12-12T15:10:10Z

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

@@ Строка 21: / Строка 21: @@
 Существуют доказательства<ref name="VOLA" /> сходимости получающихся матриц к клеточной правой треугольной матрице с диагональными клетками, размеры которых зависят от размеров канонических ящиков Жордана исходной матрицы. Таким образом, проблема собственных значений матрицы сводится к проблемам собственных значений матриц меньшего размера.
 === Приёмы ускорения сходимости, используемые в алгоритме ===
@@ Строка 45: / Строка 63: @@
 <math>A_{k+1} = R_kQ_k+\nu_kE=Q_{k}^{T}Q_kR_kQ_k+\nu_kE=Q_{k}^{T}(A_k-\nu_kE)Q_k+\nu_kE=Q_{k}^{T}A_kQ_k-Q_{k}^{T}(\nu_kE)Q_k+\nu_kE=Q_{k}^{T}A_kQ_k-\nu_kE+\nu_kE=Q_{k}^{T}A_kQ_k</math>.
-Подбор параметра <math>\nu_k</math> в пакете SCALAPACK осуществляется в зависимости от элементов матрицы <math>A_k</math>. При алгоритме подбора параметров, известном, как ''правило Фрэнсиса''<ref name = "Dem"> Деммель Д. Вычислительная линейная алгебра. – 2001. - С.261-264. </ref>, в качестве сдвигов выбираются для каждого из диагональных блоков собственные значения их нижних правых клеток размером 2х2, и среднее количество итераций для большинства матриц получается порядка 2 на одно собственное значение. Существуют, однако, матрицы, для которых правило Фрэнсиса не даёт сходимости, поэтому если по истечении 10 итераций с обычными сдвигами не получилось сходимости, применяют так называемые "особые сдвиги".
+Подбор параметра <math>\nu_k</math> в пакете SCALAPACK осуществляется в зависимости от элементов матрицы <math>A_k</math>. При алгоритме подбора параметров, известном, как ''правило Фрэнсиса''<ref name = "Dem" />, в качестве сдвигов выбираются для каждого из диагональных блоков собственные значения их нижних правых клеток размером 2х2, и среднее количество итераций для большинства матриц получается порядка 2 на одно собственное значение. Существуют, однако, матрицы, для которых правило Фрэнсиса не даёт сходимости, поэтому если по истечении 10 итераций с обычными сдвигами не получилось сходимости, применяют так называемые "особые сдвиги".
-<math>A_N=
+==== Неявное выполнение сдвигов ====
-Поэтому выбор сдвигов в алгоритме учитывает, что конечные матрицы будут представленного вида. Чтобы не выполнять итерации в комплексной арифметике, выполняют т.н. неявный двойной сдвиг, давно описанный в литературе<ref name="VOLA" /><ref name = "Dem" />.
+Чтобы не выполнять итерации в комплексной арифметике, выполняют т.н. неявный двойной сдвиг, давно описанный в литературе<ref name="VOLA" /><ref name = "Dem" />. При этом используются двусторонние подобные операции Хаусхолдера (отражения) 3го порядка. На первом шаге итерации формируют у хессенберговой формы выступ размера 2х2, а на последующих шагах с их же помощью выступ вытесняют вправо вниз.
-==== Обнуление поддиагональных элементов ====
+==== Обнуление поддиагональных элементов (дефляция) ====
-После того, как под диагональю какой-либо элемент становится менее порогового значения, его можно считать равным нулю. Это даёт возможность применить разделение диагональных блоков матрицы, соседствующих с ним, и раздельное вычисление их собственных чисел.
+После того, как под диагональю какой-либо элемент становится менее порогового значения, его можно считать равным нулю. Это даёт возможность применить разделение диагональных блоков матрицы, соседствующих с ним, и раздельное вычисление их собственных чисел. Этот приём называется '''дефляцией'''.
 == Вычислительное ядро алгоритма ==

Frolov в 11:07, 12 октября 2017

2017-10-12T11:07:32Z

← Предыдущая версия		Версия от 11:07, 12 октября 2017
Строка 1:		Строка 1:
	{{level-a}}		{{level-a}}

	'''QR-алгоритм, используемый в SCALAPACK''' - алгоритм, использующий все проверенные на настоящее время приёмы ускорения [[QR-алгоритм\|QR-алгоритма]] для несимметричных вещественных матриц. Включён своими частями в разные подпрограммы пакета SCALAPACK<ref name="SCALAEig">http://www.netlib.org/scalapack/slug/node63.html#SECTION04335100000000000000</ref>. Состоит из двух основных частей: [[Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме\|ортогонально подобного приведения матрицы к хессенберговому виду]] и QR-итераций со сдвигами для хессенберговой матрицы.		'''QR-алгоритм, используемый в SCALAPACK''' - алгоритм, использующий все проверенные на настоящее время приёмы ускорения [[QR-алгоритм\|QR-алгоритма]] для несимметричных вещественных матриц. Включён своими частями в разные подпрограммы пакета SCALAPACK<ref name="SCALAEig">http://www.netlib.org/scalapack/slug/node63.html#SECTION04335100000000000000</ref>. Состоит из двух основных частей: [[Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме\|ортогонально подобного приведения матрицы к хессенберговому виду]] и [[QR-алгоритм для хессенберговой матрицы, используемый в SCALAPACK\|QR-итераций со сдвигами для хессенберговой матрицы]].

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

Frolov: /* Использование хессенберговой формы матрицы */

2017-10-12T10:25:57Z

Использование хессенберговой формы матрицы

← Предыдущая версия		Версия от 10:25, 12 октября 2017
Строка 28:		Строка 28:
	==== Использование хессенберговой формы матрицы ====		==== Использование хессенберговой формы матрицы ====

	Хессенбергова (почти треугольная) форма матрицы интересна в приложении к QR-алгоритму тем, что в случае, если <math>A_0 = A</math> имеет эту форму, то имеют её и все матрицы <math>A_k</math>. Если теперь посмотреть на методы [[QR-разложения плотных неособенных матриц]], то видно, что выполнение разложения <math>A_k = Q_kR_k</math> в случае плотной неособенной <math>A_k</math>требует (в последовательном варианте) <math>O(n^3)</math> операций, как и последующий процесс вычисления <math>A_{k+1} = R_kQ_k</math>. В случае же, если матрицы хессенберговы, то как [[~~Методы QR-разложения плотных хессенберговых матриц~~\|QR-разложения плотных хессенберговых матриц]], так и вычисления <math>A_{k+1} = R_kQ_k</math> потребуют уже по <math>O(n^2)</math> операций. Это позволяет экономить довольно большие вычислительные ресурсы.		Хессенбергова (почти треугольная) форма матрицы интересна в приложении к QR-алгоритму тем, что в случае, если <math>A_0 = A</math> имеет эту форму, то имеют её и все матрицы <math>A_k</math>. Если теперь посмотреть на методы [[QR-разложения плотных неособенных матриц]], то видно, что выполнение разложения <math>A_k = Q_kR_k</math> в случае плотной неособенной <math>A_k</math>требует (в последовательном варианте) <math>O(n^3)</math> операций, как и последующий процесс вычисления <math>A_{k+1} = R_kQ_k</math>. В случае же, если матрицы хессенберговы, то как [[Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме\|QR-разложения плотных хессенберговых матриц]], так и вычисления <math>A_{k+1} = R_kQ_k</math> потребуют уже по <math>O(n^2)</math> операций. Это позволяет экономить довольно большие вычислительные ресурсы.

	Кроме этого, известно, что в случае, если хессенбергова матрица содержит на нижней кодиагонали только ненулевые элементы, то все кратные собственные значения будут соответствовать одному ящику Жордана<ref name="VOLA" />. Это означает, что каждое собственное значение с геометрической кратностью выше 1 даст после точного приведения матрицы к хессенбергову виду нули на нижней кодиагонали, что сразу даёт возможность параллельно работать с несколькими диагональными блоками.		Кроме этого, известно, что в случае, если хессенбергова матрица содержит на нижней кодиагонали только ненулевые элементы, то все кратные собственные значения будут соответствовать одному ящику Жордана<ref name="VOLA" />. Это означает, что каждое собственное значение с геометрической кратностью выше 1 даст после точного приведения матрицы к хессенбергову виду нули на нижней кодиагонали, что сразу даёт возможность параллельно работать с несколькими диагональными блоками.

Frolov: /* Использование хессенберговой формы матрицы */

2017-10-12T10:25:07Z

Использование хессенберговой формы матрицы

← Предыдущая версия		Версия от 10:25, 12 октября 2017
Строка 32:		Строка 32:
	Кроме этого, известно, что в случае, если хессенбергова матрица содержит на нижней кодиагонали только ненулевые элементы, то все кратные собственные значения будут соответствовать одному ящику Жордана<ref name="VOLA" />. Это означает, что каждое собственное значение с геометрической кратностью выше 1 даст после точного приведения матрицы к хессенбергову виду нули на нижней кодиагонали, что сразу даёт возможность параллельно работать с несколькими диагональными блоками.		Кроме этого, известно, что в случае, если хессенбергова матрица содержит на нижней кодиагонали только ненулевые элементы, то все кратные собственные значения будут соответствовать одному ящику Жордана<ref name="VOLA" />. Это означает, что каждое собственное значение с геометрической кратностью выше 1 даст после точного приведения матрицы к хессенбергову виду нули на нижней кодиагонали, что сразу даёт возможность параллельно работать с несколькими диагональными блоками.

	Поэтому начальное [[~~Подобные разложения на унитарные и хессенберговы~~ матрицы\|~~унитарно~~ подобное приведение матрицы к хессенбергову виду]] является органически необходимой стартовой частью алгоритма<ref name="SCALAEig" />, несмотря на то, что оно выделено в пакете SCALAPACK в отдельную подпрограмму.		Поэтому начальное [[Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме\|ортогонально подобное приведение матрицы к хессенбергову виду]] является органически необходимой стартовой частью алгоритма<ref name="SCALAEig" />, несмотря на то, что оно выделено в пакете SCALAPACK в отдельную подпрограмму.

	==== Сдвиги QR-алгоритма ====		==== Сдвиги QR-алгоритма ====