Symboliczny rozkład Choleskiego

W matematycznym poddziedzinie analizy numerycznej symboliczny rozkład Cholesky'ego jest algorytmem używanym do określania niezerowego wzorca dla czynników $rzadkiej$ macierzy przy stosowaniu rozkładu lub wariantów Cholesky'ego .

Algorytm

Niech ${\ Displaystyle A = (a_ {ij}) \ in \ mathbb {K} ^ {n \ razy n}}$ będzie rzadką symetryczną dodatnio określoną macierzą z elementami z a pole , które chcemy rozłożyć na czynniki jako $ZA$$A = LL ^ {T} \,}$ .

Stwierdzono, że w celu wdrożenia wydajnego rozkładu na czynniki rzadkie konieczne jest określenie niezerowej struktury czynników przed wykonaniem jakiejkolwiek pracy numerycznej. Aby zapisać algorytm, używamy następującej notacji:

• Niech $mathcal {A}} _ {$ będą zbiorami reprezentującymi niezerowe wzorce kolumn i i j $}}$ ja {\ Displaystyle { i tylko poniżej przekątnej, z uwzględnieniem elementów diagonalnych) odpowiednio macierzy A i L.
• Weź ${\ Displaystyle \ min {\ mathcal {L}} _ {j}}$ na myśli najmniejszy element $\ Displaystyle {\ mathcal {L}} _ {j}}$ .
• Użyj funkcji nadrzędnej, $.$ w macierzy

Poniższy algorytm daje wydajną symboliczną faktoryzację A :

${\ Displaystyle {\ rozpocząć {wyrównane} & \ pi (i): = 0 ~ {\ mbox {dla wszystkich}} ~ i \\& {\ mbox {dla}} ~ i: = 1 ~ { \mbox{to}}~n\\&\qquad {\mathcal {L}}_{i}:={\mathcal {A}}_{i}\\&\qquad {\mbox{dla wszystkich}} ~j~{\mbox{taki, że}}~\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{wyrównane}}}$