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

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

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

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

Можно также рассмотреть блочный вариант разложения Холецкого. Предположим, что [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], конечно же, будет значение "профиля" матрицы, но учет особенностей структуры ненулевых элементов внутри профиля иногда может дать дополнительный эффект в повышении эффективности вычислений.

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

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

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

Эрмитовой (или комплексно-самосопряженной) матрицей называют такую квадратную комплексную матрицу [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].

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

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

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

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

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