Метод Холецкого (нахождение симметричного треугольного разложения): различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Konshin (обсуждение | вклад) |
Konshin (обсуждение | вклад) |
||
| Строка 17: | Строка 17: | ||
== Разложение Холецкого, точечный вещественный вариант для разреженной симметричной положительно-определённой матрицы == | == Разложение Холецкого, точечный вещественный вариант для разреженной симметричной положительно-определённой матрицы == | ||
| − | Если исходная матрица <math>A</math> представлена в разреженном виде, то для экономии памяти, а также арифметических операций, необходимо учитывать ее разреженность. В этом разделе необходимо рассмотреть три следующие | + | Если исходная матрица <math>A</math> представлена в разреженном виде, то для экономии памяти, а также арифметических операций, необходимо учитывать ее разреженность. |
| + | |||
| + | === Основные отличия от случая плотной матрицы === | ||
| + | |||
| + | В этом разделе необходимо рассмотреть три следующие виды разреженности: | ||
1. ленточная матрица - матрица,ненулевые элементы которой сосредоточены внутри ленты шириной <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>, а арифметичекие затраты соcтавят приблизительно <math>d^2n</math>. | 1. ленточная матрица - матрица,ненулевые элементы которой сосредоточены внутри ленты шириной <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>, а арифметичекие затраты соcтавят приблизительно <math>d^2n</math>. | ||
| Строка 26: | Строка 30: | ||
3. матрица общей структуры разреженности. Верхней границей заполнения треугольного множителя <math>L</math>, конечно же, будет значение "профиля" матрицы, но учет особенностей структуры ненулевых элементов внутри профиля иногда может дать дополнительный эффект в повышении эффективности вычислений. | 3. матрица общей структуры разреженности. Верхней границей заполнения треугольного множителя <math>L</math>, конечно же, будет значение "профиля" матрицы, но учет особенностей структуры ненулевых элементов внутри профиля иногда может дать дополнительный эффект в повышении эффективности вычислений. | ||
| − | + | Для рассмотрения общего случая разреженности необходимо выбрать формат хранения разреженных данных. Таковым может быть, например, формат построчного сжатия данных ("compressed sparse row" или CSR формат). В первом вещественном массиве, подряд (обычно в порядке возрастания номером столбцов) хранятся ненулевые элементы матрицы, во втором, в том же порядке хранятся номера столбцов, в третьем, отдельно сохраняется начало каждой строки. Если общее количество ненулевых элементов в матрице равно nnz ("number of nonzeros"), то пямять для хранения разреженных данных такой матрицы в формате CSR при использовании двойной точности составит <math>3\,{\rm nnz}+n+1</math>. Оценку количества орифметических операций в общем случае невозможно, т.к. помимо количества ненулевых элементов в исходной матрице оно существенно зависит от структуры ее разреженности. | |
| + | |||
| + | Для реализации разложения Холецкого в этом случае понадобятся несколько операций с разреженными строками: | ||
| + | |||
| + | а) копирование из одной разреженной строки в другую (или во временный "плотный" вектор); | ||
| + | |||
| + | б) выполнение операции исключения для одного из элементов строки; | ||
| + | |||
| + | в) вставление в строку нового ненулевого элемента ("fill-in"); | ||
| + | |||
| + | г) сжатие данных с копированием из временного плотного вектора в сжатый разреженный. | ||
=== Переупорядочивания для уменьшения количества новых ненулевых элементов === | === Переупорядочивания для уменьшения количества новых ненулевых элементов === | ||
| + | |||
| + | Структура треугольного множителя <math>L</math>, а также объем памяти им занимаемый, зависят от упорядочивания строк и столбцов исходной матрицы <math>A</math>, в котором проводится разложение. Существуют алгоритмы, минимизирующие заполнение матрицы <math>L</math>. | ||
| + | |||
| + | *) В первую очередь это алгоритм RCM (reversed Cuthill–McKee), который предназначен для уменьшения профиля матрицы. Одновременно с уменьшением профиля происходит и уменьшение заполнения треугольного множителя <math>L</math>. Это очень широко применяемый, быстрый, но не самый эффективный алгоритм. Русского аналога название этого алгоритма не имеет. | ||
| + | |||
| + | *) Алгоритм вложенных сечений (Nested Dissection, ND) - служит именно для минимизации заполнения множителя <math>L</math>. В некоторых частных случаях доказана его ассимптотическая оптимальность. | ||
| + | |||
| + | В общем случае, проблема поиска перестановки минимизирующей заполнение множителя <math>L</math> является NP-полной задачей. | ||
== Разложение Холецкого, блочный вещественный вариант для разреженной симметричной положительно-определённой матрицы == | == Разложение Холецкого, блочный вещественный вариант для разреженной симметричной положительно-определённой матрицы == | ||
Версия 15:30, 18 марта 2015
Содержание
- 1 Разложение Холецкого (метод квадратного корня), базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
- 2 Разложение Холецкого, блочный вещественный вариант для плотной симметричной положительно-определённой матрицы
- 3 Разложение Холецкого, точечный вещественный вариант для разреженной симметричной положительно-определённой матрицы
- 4 Разложение Холецкого, блочный вещественный вариант для разреженной симметричной положительно-определённой матрицы
- 5 Разложение Холецкого для эрмитовой матрицы
- 6 Использование разложения Холецкого в итерационных методах
- 6.1 Ограничивание заполнения в разложении Холецкого
- 6.2 Неполное разложение Холецкого по позициям IC([math]k[/math])
- 6.3 Приближенное разложение Холецкого по значениям IC([math]\tau[/math])
- 6.4 Приближенное разложение Холецкого второго порядка IC([math]\tau_1,\tau_2[/math])
- 6.5 Комбинация разложений Холецкого IC([math]k,\tau[/math]) и IC([math]\tau,m[/math])
- 7 Использование разложения Холецкого в параллельных итерационных алгоритмах
- 7.1 Переупорядочивания для выделения блочности
- 7.2 Разложение в независимых блоках
- 7.3 Разложение в сепараторах
- 7.4 Иерархические и вложенные алгоритмы
- 7.5 Блочный метод Якоби (без перекрытия блоков, Block Jacobi - BJ)
- 7.6 Адитивный метод Шварца (Additive Schwarz - AS)
- 7.7 Блочный метод неполного обратного разложения Холецкого (BIIC)
- 8 Решение линейной системы с треугольной матрицей
- 8.1 Решение системы с плотной верхнетреугольной матрицей
- 8.2 Решение системы с плотной нижнетреугольной матрицей
- 8.3 Решение системы с разреженной верхнетреугольной матрицей
- 8.4 Решение системы с разреженной нижнетреугольной матрицей
- 8.5 Решение системы с комплексной треугольной матрицей
- 8.6 Решение систем с блочноокаймленными треугольными матрицами
1 Разложение Холецкого (метод квадратного корня), базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
Разложение Холецкого (метод квадратного корня), базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы.
2 Разложение Холецкого, блочный вещественный вариант для плотной симметричной положительно-определённой матрицы
Можно также рассмотреть блочный вариант разложения Холецкого. Предположим, что [math]n=MN[/math], тогда исходную матрицу [math]A[/math] размера [math]n\times n[/math] можно представить как блочную матрицу размера [math]N\times N[/math] с блоками размера [math]M\times M[/math]. Все формулы, используемые для получения точечного разложения Холецкого, для блочной матрицы [math]А[/math] останутся практически без изменений. Вместо явного обращения диагональных блоков, эффективнее будет хранить их в факторизованном виде [math]D_{ii}=L_{ii}L^T_{ii}[/math], а вместо точечной операции деления использовать операции решения треугольных систем. Общее количество арифметических операций при этом останется практически неизменным, но зато существенно возрастет локальность вычислений. Размер блока [math]M[/math] выбирают таким образом, чтобы все блоки, участвующие в операции исключения, помещались в кэш первого или второго уровня. В этом случае подкачки данных в память будут минимальными.
Аналогичный прием понадобится также и для эффективной реализации параллельной версии разложения Холецкого, что позволит минимизировать как общее количество обменов, так и количество пересылаемой между процессорами информации. Полезным побочным эффектом использования блочной версии разложения Холецкого может стать повышение скалярной эффективности алгоритма за счет явного использования размера блока [math]M[/math] во внутренних циклах (прием "разворачивания цикла" или "loop unrolling").
3 Разложение Холецкого, точечный вещественный вариант для разреженной симметричной положительно-определённой матрицы
Если исходная матрица [math]A[/math] представлена в разреженном виде, то для экономии памяти, а также арифметических операций, необходимо учитывать ее разреженность.
3.1 Основные отличия от случая плотной матрицы
В этом разделе необходимо рассмотреть три следующие виды разреженности:
1. ленточная матрица - матрица,ненулевые элементы которой сосредоточены внутри ленты шириной [math]2d+1[/math], т.е. когда [math]a_{ij}=0[/math], если [math]|i-j|\gt d[/math]. В этом случае, при проведении разложения Холдецкого новые ненулевые элементы (если внутри ленты имеются нулевые элементы) могут образовываться только внутри этой же ленты. Количество ненулевых элементов в исходной матрице [math]A[/math], а также в нижнетреугольном множителе [math]L[/math] будет около [math](d+1)n[/math], а арифметичекие затраты соcтавят приблизительно [math]d^2n[/math]. Случай, когда матрица состоит всего из нескольких диагоналей (например, при конечно-разностной аппроксимации уравнений в частных производных на регулярной сетке) здесь отдельно не рассматривается, т.к. заполнение в нижнетреугольном множителе [math]L[/math] все-равно будет определяться исключительно наличием самой внешней (дальней) диагонали.
2. профильная матрица - в более общем случае, заполнение в каждой строке треугольного множителе [math]L[/math] будет определяться позицией первого ненулевого элемента. Сумма по всем строкам растояний от первого ненулевого элемента строки до главной диагонали и сотавляет "профиль" матрицы и определяет количество ненулевых элементов в нижнетреугольном множителе [math]L[/math].
3. матрица общей структуры разреженности. Верхней границей заполнения треугольного множителя [math]L[/math], конечно же, будет значение "профиля" матрицы, но учет особенностей структуры ненулевых элементов внутри профиля иногда может дать дополнительный эффект в повышении эффективности вычислений.
Для рассмотрения общего случая разреженности необходимо выбрать формат хранения разреженных данных. Таковым может быть, например, формат построчного сжатия данных ("compressed sparse row" или CSR формат). В первом вещественном массиве, подряд (обычно в порядке возрастания номером столбцов) хранятся ненулевые элементы матрицы, во втором, в том же порядке хранятся номера столбцов, в третьем, отдельно сохраняется начало каждой строки. Если общее количество ненулевых элементов в матрице равно nnz ("number of nonzeros"), то пямять для хранения разреженных данных такой матрицы в формате CSR при использовании двойной точности составит [math]3\,{\rm nnz}+n+1[/math]. Оценку количества орифметических операций в общем случае невозможно, т.к. помимо количества ненулевых элементов в исходной матрице оно существенно зависит от структуры ее разреженности.
Для реализации разложения Холецкого в этом случае понадобятся несколько операций с разреженными строками:
а) копирование из одной разреженной строки в другую (или во временный "плотный" вектор);
б) выполнение операции исключения для одного из элементов строки;
в) вставление в строку нового ненулевого элемента ("fill-in");
г) сжатие данных с копированием из временного плотного вектора в сжатый разреженный.
3.2 Переупорядочивания для уменьшения количества новых ненулевых элементов
Структура треугольного множителя [math]L[/math], а также объем памяти им занимаемый, зависят от упорядочивания строк и столбцов исходной матрицы [math]A[/math], в котором проводится разложение. Существуют алгоритмы, минимизирующие заполнение матрицы [math]L[/math].
- ) В первую очередь это алгоритм RCM (reversed Cuthill–McKee), который предназначен для уменьшения профиля матрицы. Одновременно с уменьшением профиля происходит и уменьшение заполнения треугольного множителя [math]L[/math]. Это очень широко применяемый, быстрый, но не самый эффективный алгоритм. Русского аналога название этого алгоритма не имеет.
- ) Алгоритм вложенных сечений (Nested Dissection, ND) - служит именно для минимизации заполнения множителя [math]L[/math]. В некоторых частных случаях доказана его ассимптотическая оптимальность.
В общем случае, проблема поиска перестановки минимизирующей заполнение множителя [math]L[/math] является NP-полной задачей.
4 Разложение Холецкого, блочный вещественный вариант для разреженной симметричной положительно-определённой матрицы
(плотные блоки небольшого размера, равного количеству неизвестных функций на узел, или выбираемому искуственно)
5 Разложение Холецкого для эрмитовой матрицы
Эрмитовой (или комплексно-самосопряженной) матрицей называют такую квадратную комплексную матрицу [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^Н[/math].
5.1 Точечный вариант
Как естественное обобщение разложения Холецкого для точечной симметричной положительно-определеной матрицы может быть рассмотрено разложение Холецкого для эрмитовой матрицы. Все формулы для вычисления разложения остаются прежними, только теперь вместо операций над вещественными числами выполняются аналогичные комплексные операции.
В отличие от вещественного варианта, для выполнении комплексных операций потребуется считывать из памяти вдвое больше данных и производить над ними примерно вчетверо больше арифметических операций, что должно не только несколько улучшыть локальность вычислений, но и повысить их эффективность.
5.2 Блочный вариант
Реализация блочного варианта разложения Холецкого для эрмитовых матриц будет аналогична рассмотрему выше блочному варианту для вещественных матриц.
