Symbolisk Cholesky nedbrytning

I det matematiska underområdet för numerisk analys är den symboliska Cholesky-nedbrytningen en algoritm som används för att bestämma mönstret som inte är noll för $L$ -faktorerna i en symmetrisk gles matris när Cholesky-nedbrytningen eller varianterna tillämpas.

Algoritm

Låt $A=(a_{ij})\in \mathbb {K} ^{n\times n}$ vara en gles symmetrisk positiv bestämd matris med element från en fältet $\mathbb {K}$ , som vi vill faktorisera som $A=LL^{T}\,$ .

För att implementera en effektiv sparsam faktorisering har det visat sig vara nödvändigt att bestämma icke-nollstrukturen för faktorerna innan något numeriskt arbete utförs. För att skriva ner algoritmen använder vi följande notation:

• Låt ${\mathcal {A}}_{i}$ och ${\mathcal {L}}_{j}$ vara uppsättningar som representerar mönstren som inte är noll i kolumnerna i och j ( endast under diagonalen och inklusive diagonala element) för matriserna A respektive L.
• Ta $\min {\mathcal {L}}_{j}$ för att betyda det minsta elementet i ${\mathcal {L}}_{j}$ .
• Använd en överordnad funktion $\pi (i)\,\!$ för att definiera elimineringsträdet i matrisen.

Följande algoritm ger en effektiv symbolisk faktorisering av A :

${\begin{aligned}&\pi (i):=0~{\mbox{för alla}}~i\\&{\mbox{För }}~i:=1~{\mbox{to}}~n\\&\qquad {\mathcal {L}}_{i}:={\mathcal {A}}_{i}\\&\ qquad {\mbox{För alla}}~j~{\mbox{så att}}~\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}}$