Метод Холецкого (нахождение симметричного треугольного разложения) - История изменений

AntonChupin в 13:29, 8 июля 2016

2016-07-08T13:29:12Z

← Предыдущая версия		Версия от 13:29, 8 июля 2016
Строка 365:		Строка 365:

	[[Категория:Законченные статьи]]		[[Категория:Законченные статьи]]
			[[Категория:Разложения матриц]]

ASA в 11:40, 10 февраля 2016

2016-02-10T11:40:06Z

← Предыдущая версия		Версия от 11:40, 10 февраля 2016
Строка 1:		Строка 1:
			{{level-m}}
	Основные авторы описания: [[Участник:Konshin\|И.Н.Коньшин]]		Основные авторы описания: [[Участник:Konshin\|И.Н.Коньшин]]

Frolov: /* Разложение Холецкого для эрмитовой матрицы */

2015-12-08T15:11:42Z

Разложение Холецкого для эрмитовой матрицы

← Предыдущая версия		Версия от 15:11, 8 декабря 2015
Строка 128:		Строка 128:

	Эрмитовой (или комплексно-самосопряженной) матрицей называют такую квадратную комплексную матрицу <math>A</math>, для элементов которой выполняется соотношение		Эрмитовой (или комплексно-самосопряженной) матрицей называют такую квадратную комплексную матрицу <math>A</math>, для элементов которой выполняется соотношение
	<math>a_{ij}=\overline{a_{ji}}</math> (здесь, если <math>z=a+{\rm i\,}b\,</math> и <math>{\rm i}^2=-1</math>, то <math>\overline z=a-{\rm i\,}b\,</math>). В матричном виде это можно записать как <math>A=\overline{A^T}</math> или <math>A=A^*~~=A^Н~~</math>.		<math>a_{ij}=\overline{a_{ji}}</math> (здесь, если <math>z=a+{\rm i\,}b\,</math> и <math>{\rm i}^2=-1</math>, то <math>\overline z=a-{\rm i\,}b\,</math>). В матричном виде это можно записать как <math>A=\overline{A^T}</math> или <math>A = A^*</math>.

	=== Точечный вариант ===		=== Точечный вариант ===

ASA в 06:39, 22 июня 2015

2015-06-22T06:39:29Z

← Предыдущая версия		Версия от 06:39, 22 июня 2015
Строка 363:		Строка 363:
	[[en:Cholesky method]]		[[en:Cholesky method]]

	[[Категория:~~Статьи в работе~~]]		[[Категория:Законченные статьи]]

Konshin: /* Основные отличия от случая плотной матрицы */

2015-04-16T23:13:45Z

Основные отличия от случая плотной матрицы

← Предыдущая версия		Версия от 23:13, 16 апреля 2015
Строка 58:		Строка 58:
	В этом разделе необходимо рассмотреть матрицы, характеризующиеся способом хранения ненулевых элементов, и имеющие следующие виды разреженности.		В этом разделе необходимо рассмотреть матрицы, характеризующиеся способом хранения ненулевых элементов, и имеющие следующие виды разреженности.

	* ''Лента'' - матрица, ненулевые элементы которой сосредоточены внутри ленты шириной <math>2d+1</math>, т.е. когда <math>a_{ij}=0</math> при <math>\|i-j\| > d</math>. В этом случае, при проведении разложения Холецкого новые ненулевые элементы могут образовываться только внутри этой же ленты. Количество ненулевых элементов в исходной матрице <math>A</math>, а также в нижнетреугольном множителе <math>L</math> будет около <math>(d+1)n</math>, а арифметические затраты составят приблизительно <math>d^2n</math>.		* ''Лента'' - матрица, ненулевые элементы которой сосредоточены внутри ленты шириной <math>2d+1</math>, т.е. когда <math>a_{ij}=0</math> при <math>\|i-j\| > d</math>. В этом случае, при проведении разложения Холецкого новые ненулевые элементы могут образовываться только внутри этой же ленты (поскольку нет выбора ведущих элементов в силу положительной определенности матрицы <math>A</math>). Количество ненулевых элементов в исходной матрице <math>A</math>, а также в нижнетреугольном множителе <math>L</math> будет около <math>(d+1)n</math>, а арифметические затраты составят приблизительно <math>d^2n</math>.

	* ''Профиль'' - в более общем случае, заполнение в каждой строке треугольного множителе <math>L</math> будет определяться позицией первого ненулевого элемента. Сумма по всем строкам расстояний от первого ненулевого элемента строки до главной диагонали и составляет "профиль" матрицы и определяет верхнюю границу количества ненулевых элементов в нижнетреугольном множителе <math>L</math>.		* ''Профиль'' - в более общем случае, заполнение в каждой строке треугольного множителе <math>L</math> будет определяться позицией первого ненулевого элемента. Сумма по всем строкам расстояний от первого ненулевого элемента строки до главной диагонали и составляет "профиль" матрицы и определяет верхнюю границу количества ненулевых элементов в нижнетреугольном множителе <math>L</math>.

Oleg Arushanyan: /* Точечный вариант */

2015-04-16T13:32:17Z

Точечный вариант

← Предыдущая версия		Версия от 13:32, 16 апреля 2015
Строка 143:		Строка 143:
	В отличие от		В отличие от
	[[Метод_Холецкого_(нахождение_симметричного_треугольного_разложения)#Разложение Холецкого (метод квадратного корня), базовый точечный вещественный вариант для плотной симметричной положительно определённой матрицы\|вещественного варианта]],		[[Метод_Холецкого_(нахождение_симметричного_треугольного_разложения)#Разложение Холецкого (метод квадратного корня), базовый точечный вещественный вариант для плотной симметричной положительно определённой матрицы\|вещественного варианта]],
	~~для~~ выполнении аналогичных комплексных операций потребуется считывать из памяти вдвое больше данных и производить над ними примерно вчетверо больше арифметических операций, что должно не только несколько улучшить локальность вычислений, но и повысить общую эффективность вычислений.		при выполнении аналогичных комплексных операций потребуется считывать из памяти вдвое больше данных и производить над ними примерно вчетверо больше арифметических операций, что должно не только несколько улучшить локальность вычислений, но и повысить общую эффективность вычислений.

	=== Блочный вариант ===		=== Блочный вариант ===

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

2015-04-15T22:52:07Z

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

← Предыдущая версия		Версия от 22:52, 15 апреля 2015
Строка 348:		Строка 348:
	* В [https://ru.wikipedia.org/wiki/SAS_Institute SAS] используется функция ROOT( matrix ), входящая в пакет SAS IML.		* В [https://ru.wikipedia.org/wiki/SAS_Institute SAS] используется функция ROOT( matrix ), входящая в пакет SAS IML.

	* В системах [https://ru.wikipedia.org/wiki/MATLAB MATLAB], [https://ru.wikipedia.org/wiki/GNU_Octave Octave], [https://ru.wikipedia.org/wiki/R_(~~%D1%8F%D0%B7%D1%8B%D0%BA_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F~~) R] разложение выполняется командой U = chol(A).		* В системах [https://ru.wikipedia.org/wiki/MATLAB MATLAB], [https://ru.wikipedia.org/wiki/GNU_Octave Octave], [https://ru.wikipedia.org/wiki/R_(язык_программирования) R] разложение выполняется командой U = chol(A).

	* В [https://ru.wikipedia.org/wiki/Maple Maple] и [https://ru.wikipedia.org/wiki/NumPy NumPy] существует процедура cholesky в модуле linalg.		* В [https://ru.wikipedia.org/wiki/Maple Maple] и [https://ru.wikipedia.org/wiki/NumPy NumPy] существует процедура cholesky в модуле linalg.
Строка 356:		Строка 356:
	* В [https://ru.wikipedia.org/wiki/GSL GSL] используется функция gsl_linalg_cholesky_decomp.		* В [https://ru.wikipedia.org/wiki/GSL GSL] используется функция gsl_linalg_cholesky_decomp.

	* В [http://www.alglib.net ALGLIB] имеются реализации как [http://www.alglib.net/matrixops/cholesky.php LLT] так и [http://www.alglib.net/matrixops/symmetric/ldlt.php LDLT] разложений для различных языков ~~програмирования~~: C#, C++, C++ (арифметика повышенной точности), FreePascal, Delphi, VB.NET, VBA, Python.		* В [http://www.alglib.net ALGLIB] имеются реализации как [http://www.alglib.net/matrixops/cholesky.php LLT] так и [http://www.alglib.net/matrixops/symmetric/ldlt.php LDLT] разложений для различных языков программирования: C#, C++, C++ (арифметика повышенной точности), FreePascal, Delphi, VB.NET, VBA, Python.

	* В [http://www.bluebit.gr/matrix-calculator/ Online Matrix Calculator] непосредственно в web-интерфейсе можно выполнить разложение Холецкого, выбрав раздел ''Cholesky Decomposition''.		* В [http://www.bluebit.gr/matrix-calculator/ Online Matrix Calculator] непосредственно в web-интерфейсе можно выполнить разложение Холецкого, выбрав раздел ''Cholesky Decomposition''.

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

2015-04-15T22:45:55Z

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

← Предыдущая версия		Версия от 22:45, 15 апреля 2015
Строка 344:		Строка 344:
	* В [http://netlib.org/lapack/ LAPACK] используется функция [http://www.netlib.org/lapack/double/dpotrf.f DPBTRF] (последовательная реализация для двойной точности).		* В [http://netlib.org/lapack/ LAPACK] используется функция [http://www.netlib.org/lapack/double/dpotrf.f DPBTRF] (последовательная реализация для двойной точности).

	* В [http://www.netlib.org/scalapack/ ScaLAPACK] используется функция [http://www.netlib.org/scalapack/double/pdpbtrf.f PDPBTRF] (~~паралельная~~ реализация для двойной точности).		* В [http://www.netlib.org/scalapack/ ScaLAPACK] используется функция [http://www.netlib.org/scalapack/double/pdpbtrf.f PDPBTRF] (параллельная реализация для двойной точности).

	* В [https://ru.wikipedia.org/wiki/SAS_Institute SAS] используется функция ROOT( matrix ), входящая в пакет SAS IML.		* В [https://ru.wikipedia.org/wiki/SAS_Institute SAS] используется функция ROOT( matrix ), входящая в пакет SAS IML.

Konshin: /* Аддитивный метод Шварца */

2015-04-15T22:42:31Z

Аддитивный метод Шварца

← Предыдущая версия		Версия от 22:42, 15 апреля 2015
Строка 273:		Строка 273:
	=== Аддитивный метод Шварца ===		=== Аддитивный метод Шварца ===

	Разложение гораздо более высокого качества по сравнению с ~~мотодом~~ Якоби можно получить применяя аддитивный метод Шварца (Additive Schwarz, AS). Иногда этот метод называют также методом Якоби с перекрытиями. Суть его заключается в расширении структуры каждого из блоков матрицы за счет добавления нескольких слоев близлежащих строк матрицы. Треугольное разложение строится для расширенной матрицы, таким образом на каждом из процессоров происходит решение расширенной подзадачи с привлечением данных от других процессоров.		Разложение гораздо более высокого качества по сравнению с методом Якоби можно получить применяя аддитивный метод Шварца (Additive Schwarz, AS). Иногда этот метод называют также методом Якоби с перекрытиями. Суть его заключается в расширении структуры каждого из блоков матрицы за счет добавления нескольких слоев близлежащих строк матрицы. Треугольное разложение строится для расширенной матрицы, таким образом на каждом из процессоров происходит решение расширенной подзадачи с привлечением данных от других процессоров.
	После нахождения решения подзадачи на каждом из процессоров обычно происходит отбрасывание не локальных компонент решения. Такой вариант метода называют аддитивный метод Шварца с ограничениями (Restricted Additive Schwarz, RAS).		После нахождения решения подзадачи на каждом из процессоров обычно происходит отбрасывание не локальных компонент решения. Такой вариант метода называют аддитивный метод Шварца с ограничениями (Restricted Additive Schwarz, RAS).

Konshin: /* Блочный метод Якоби */

2015-04-15T22:41:30Z

Блочный метод Якоби

← Предыдущая версия		Версия от 22:41, 15 апреля 2015
Строка 265:		Строка 265:
	Описанные выше подходы относились к типу "прямого" или "явного" разложения, когда при отбрасывании элементов разложения в расчет принимались только их абсолютные значения. Структурные свойства при этом являлись подчиненными и на отбрасывание элементов никак не влияли.		Описанные выше подходы относились к типу "прямого" или "явного" разложения, когда при отбрасывании элементов разложения в расчет принимались только их абсолютные значения. Структурные свойства при этом являлись подчиненными и на отбрасывание элементов никак не влияли.

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