Символическое разложение Холецкого

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

Алгоритм

Позволять $A=(a_{ij})\in \mathbb {K} ^{n\times n}$быть разреженной симметричной положительно определенной матрицей с элементами из поля $\mathbb {K}$, который мы хотим факторизовать как $A=LL^{T}\,$.

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

• Позволять ${\mathcal {A}}_{i}$ и ${\mathcal {L}}_{j}$ быть наборами, представляющими ненулевые шаблоны столбцов i и j (только ниже диагонали и включая диагональные элементы) матриц A и L соответственно.
• Брать $\min {\mathcal {L}}_{j}$ означает наименьший элемент ${\mathcal {L}}_{j}$.
• Используйте родительскую функцию $\pi (i)\,\!$ определить дерево исключения внутри матрицы.

Следующий алгоритм дает эффективный символическая факторизация A :

${\begin{aligned}&\pi (i):=0~{\mbox{for all}}~i\\&{\mbox{For}}~i:=1~{\mbox{to}}~n\\&\qquad {\mathcal {L}}_{i}:={\mathcal {A}}_{i}\\&\qquad {\mbox{For all}}~j~{\mbox{such that}}~\pi (j)=i\\&\qquad \qquad {\mathcal {L}}_{i}:=({\mathcal {L}}_{i}\cup {\mathcal {L}}_{j})\setminus \{j\}\\&\qquad \pi (i):=\min({\mathcal {L}}_{i}\setminus \{i\})\end{aligned}}$