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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Строка 23: Строка 23:
В этом разделе необходимо рассмотреть три следующие виды разреженности:
В этом разделе необходимо рассмотреть три следующие виды разреженности:


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>.
Случай, когда матрица состоит всего из нескольких диагоналей (например, при конечно-разностной аппроксимации уравнений в частных производных на регулярной сетке) здесь отдельно не рассматривается, т.к. заполнение в нижнетреугольном множителе <math>L</math> все-равно будет определяться исключительно наличием самой внешней (дальней) диагонали.
Случай, когда матрица состоит всего из нескольких диагоналей (например, при конечно-разностной аппроксимации уравнений в частных производных на регулярной сетке) здесь отдельно не рассматривается, т.к. заполнение в нижнетреугольном множителе <math>L</math> все-равно будет определяться исключительно наличием самой внешней (дальней) диагонали.


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


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


Для рассмотрения общего случая разреженности необходимо выбрать формат хранения разреженных данных. Таковым может быть, например, формат построчного сжатия данных ("compressed sparse row" или CSR формат). В первом вещественном массиве, подряд (обычно в порядке возрастания номером столбцов) хранятся ненулевые элементы матрицы, во втором, в том же порядке хранятся номера столбцов, в третьем, отдельно сохраняется начало каждой строки. Если общее количество ненулевых элементов в матрице равно nnz ("number of nonzeros"), то пямять для хранения разреженных данных такой матрицы в формате CSR при использовании двойной точности составит <math>3\,{\rm nnz}+n+1</math>. Оценку количества орифметических операций в общем случае невозможно, т.к. помимо количества ненулевых элементов в исходной матрице оно существенно зависит от структуры ее разреженности.
Для рассмотрения общего случая разреженности необходимо выбрать формат хранения разреженных данных. Таковым может быть, например, формат построчного сжатия данных ("compressed sparse row" или CSR формат). В первом вещественном массиве, подряд (обычно в порядке возрастания номером столбцов) хранятся ненулевые элементы матрицы, во втором, в том же порядке хранятся номера столбцов, в третьем, отдельно сохраняется начало каждой строки. Если общее количество ненулевых элементов в матрице равно nnz ("number of nonzeros"), то пямять для хранения разреженных данных такой матрицы в формате CSR при использовании двойной точности составит <math>3\,{\rm nnz}+n+1</math>. Оценку количества орифметических операций в общем случае невозможно, т.к. помимо количества ненулевых элементов в исходной матрице оно существенно зависит от структуры ее разреженности.
Строка 34: Строка 34:
Для реализации разложения Холецкого в этом случае понадобятся несколько операций с разреженными строками:
Для реализации разложения Холецкого в этом случае понадобятся несколько операций с разреженными строками:


а) копирование из одной разреженной строки в другую (или во временный "плотный" вектор);
а) ''копирование'' из одной разреженной строки в другую (или во временный "плотный" вектор, ''распаковка'' данных);


б) выполнение операции исключения для одного из элементов строки;
б) выполнение ''операции исключения'' для одного из элементов строки;


в) вставление в строку нового ненулевого элемента ("fill-in");
в) ''вставление'' в строку нового ненулевого элемента ("fill-in");


г) сжатие данных с копированием из временного плотного вектора в сжатый разреженный.
г) ''сжатие'' данных с копированием из временного плотного вектора в сжатый разреженный (''упаковка'' данных).


=== Переупорядочивания для уменьшения количества новых ненулевых элементов ===
=== Переупорядочивания для уменьшения количества новых ненулевых элементов ===

Версия от 12:51, 18 марта 2015

Разложение Холецкого (метод квадратного корня), базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы

Разложение Холецкого (метод квадратного корня), базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы.

Разложение Холецкого, блочный вещественный вариант для плотной симметричной положительно-определённой матрицы

Можно также рассмотреть блочный вариант разложения Холецкого. Предположим, что [math]\displaystyle{ n=MN }[/math], тогда исходную матрицу [math]\displaystyle{ A }[/math] размера [math]\displaystyle{ n\times n }[/math] можно представить как блочную матрицу размера [math]\displaystyle{ N\times N }[/math] с блоками размера [math]\displaystyle{ M\times M }[/math]. Все формулы, используемые для получения точечного разложения Холецкого, для блочной матрицы [math]\displaystyle{ А }[/math] останутся практически без изменений. Вместо явного обращения диагональных блоков, эффективнее будет хранить их в факторизованном виде [math]\displaystyle{ D_{ii}=L_{ii}L^T_{ii} }[/math], а вместо точечной операции деления использовать операции решения треугольных систем. Общее количество арифметических операций при этом останется практически неизменным, но зато существенно возрастет локальность вычислений. Размер блока [math]\displaystyle{ M }[/math] выбирают таким образом, чтобы все блоки, участвующие в операции исключения, помещались в кэш первого или второго уровня. В этом случае подкачки данных в память будут минимальными.

Аналогичный прием понадобится также и для эффективной реализации параллельной версии разложения Холецкого, что позволит минимизировать как общее количество обменов, так и количество пересылаемой между процессорами информации. Полезным побочным эффектом использования блочной версии разложения Холецкого может стать повышение скалярной эффективности алгоритма за счет явного использования размера блока [math]\displaystyle{ M }[/math] во внутренних циклах (прием "разворачивания цикла" или "loop unrolling").

Разложение Холецкого, точечный вещественный вариант для разреженной симметричной положительно-определённой матрицы

Если исходная матрица [math]\displaystyle{ A }[/math] представлена в разреженном виде, то для экономии памяти, а также арифметических операций, необходимо учитывать ее разреженность.

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

В этом разделе необходимо рассмотреть три следующие виды разреженности:

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

2. профильная матрица - в более общем случае, заполнение в каждой строке треугольного множителе [math]\displaystyle{ L }[/math] будет определяться позицией первого ненулевого элемента. Сумма по всем строкам растояний от первого ненулевого элемента строки до главной диагонали и сотавляет "профиль" матрицы и определяет количество ненулевых элементов в нижнетреугольном множителе [math]\displaystyle{ L }[/math].

3. матрица общей структуры разреженности. Верхней границей заполнения треугольного множителя [math]\displaystyle{ L }[/math], конечно же, будет значение "профиля" матрицы, но учет особенностей структуры ненулевых элементов внутри профиля иногда может дать дополнительный эффект в повышении эффективности вычислений.

Для рассмотрения общего случая разреженности необходимо выбрать формат хранения разреженных данных. Таковым может быть, например, формат построчного сжатия данных ("compressed sparse row" или CSR формат). В первом вещественном массиве, подряд (обычно в порядке возрастания номером столбцов) хранятся ненулевые элементы матрицы, во втором, в том же порядке хранятся номера столбцов, в третьем, отдельно сохраняется начало каждой строки. Если общее количество ненулевых элементов в матрице равно nnz ("number of nonzeros"), то пямять для хранения разреженных данных такой матрицы в формате CSR при использовании двойной точности составит [math]\displaystyle{ 3\,{\rm nnz}+n+1 }[/math]. Оценку количества орифметических операций в общем случае невозможно, т.к. помимо количества ненулевых элементов в исходной матрице оно существенно зависит от структуры ее разреженности.

Для реализации разложения Холецкого в этом случае понадобятся несколько операций с разреженными строками:

а) копирование из одной разреженной строки в другую (или во временный "плотный" вектор, распаковка данных);

б) выполнение операции исключения для одного из элементов строки;

в) вставление в строку нового ненулевого элемента ("fill-in");

г) сжатие данных с копированием из временного плотного вектора в сжатый разреженный (упаковка данных).

Переупорядочивания для уменьшения количества новых ненулевых элементов

Структура треугольного множителя [math]\displaystyle{ L }[/math], а также объем памяти им занимаемый, зависят от упорядочивания строк и столбцов исходной матрицы [math]\displaystyle{ A }[/math], в котором проводится разложение. Существуют алгоритмы, минимизирующие заполнение матрицы [math]\displaystyle{ L }[/math].

  • ) В первую очередь это алгоритм RCM (reversed Cuthill–McKee), который предназначен для уменьшения профиля матрицы. Одновременно с уменьшением профиля происходит и уменьшение заполнения треугольного множителя [math]\displaystyle{ L }[/math]. Это очень широко применяемый, быстрый, но не самый эффективный алгоритм. Русского аналога название этого алгоритма не имеет.
  • ) Алгоритм вложенных сечений (Nested Dissection, ND) - служит именно для минимизации заполнения множителя [math]\displaystyle{ L }[/math]. В некоторых частных случаях доказана его ассимптотическая оптимальность.

В общем случае, проблема поиска перестановки минимизирующей заполнение множителя [math]\displaystyle{ L }[/math] является NP-полной задачей.

Разложение Холецкого, блочный вещественный вариант для разреженной симметричной положительно-определённой матрицы

(плотные блоки небольшого размера, равного количеству неизвестных функций на узел, или выбираемому искуственно)

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

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

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

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

В отличие от вещественного варианта, для выполнении комплексных операций потребуется считывать из памяти вдвое больше данных и производить над ними примерно вчетверо больше арифметических операций, что должно не только несколько улучшыть локальность вычислений, но и повысить их эффективность.

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

Реализация блочного варианта разложения Холецкого для эрмитовых матриц будет аналогична рассмотрему выше блочному варианту для вещественных матриц.

Использование разложения Холецкого в итерационных методах

Ограничивание заполнения в разложении Холецкого

Неполное разложение Холецкого по позициям IC([math]\displaystyle{ k }[/math])

Приближенное разложение Холецкого по значениям IC([math]\displaystyle{ \tau }[/math])

Приближенное разложение Холецкого второго порядка IC([math]\displaystyle{ \tau_1,\tau_2 }[/math])

Комбинация разложений Холецкого IC([math]\displaystyle{ k,\tau }[/math]) и IC([math]\displaystyle{ \tau,m }[/math])

Использование разложения Холецкого в параллельных итерационных алгоритмах

Переупорядочивания для выделения блочности

Метод минимальных сепараторов

Метод минимальной степени (Minimum Degree - MD)

Метод вложенных сечений (Nested Dissection - ND)

Разложение в независимых блоках

Разложение в сепараторах

Иерархические и вложенные алгоритмы

Блочный метод Якоби (без перекрытия блоков, Block Jacobi - BJ)

Адитивный метод Шварца (Additive Schwarz - AS)

Блочный метод неполного обратного разложения Холецкого (BIIC)

Решение линейной системы с треугольной матрицей

Решение системы с плотной верхнетреугольной матрицей

Решение системы с плотной нижнетреугольной матрицей

Решение системы с разреженной верхнетреугольной матрицей

Решение системы с разреженной нижнетреугольной матрицей

Решение системы с комплексной треугольной матрицей

Решение систем с блочноокаймленными треугольными матрицами

Источник — https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Метод_Холецкого_(нахождение_симметричного_треугольного_разложения)&oldid=1108