Descomposición simbólica de Cholesky

En el subcampo matemático del análisis numérico, la descomposición simbólica de Cholesky es un algoritmo utilizado para determinar el patrón no nulo para la${\displaystyle L}$factores de una matriz dispersa simétrica al aplicar la descomposición de Cholesky o variantes. ^{[ 1 ] [ 2 ]}

Dejar ${\displaystyle A=(a_{ij})\in \mathbb {K} ^{n\times n}}$ Sea una matriz dispersa simétrica definida positiva con elementos de un campo.${\displaystyle \mathbb {K} }$, que deseamos factorizar como${\displaystyle A=LL^{T}\,}$.

Para implementar una factorización dispersa eficiente, se ha comprobado que es necesario determinar la estructura no nula de los factores antes de realizar cualquier cálculo numérico. Para escribir el algoritmo, utilizamos la siguiente notación:

• Dejar${\displaystyle {\mathcal {A}}_{i}}$y${\displaystyle {\mathcal {L}}_{j}}$sean conjuntos que representen los patrones no nulos de las columnas i y j (solo debajo de la diagonal, e incluyendo los elementos diagonales) de las matrices A y L respectivamente.
• Llevar${\displaystyle \min {\mathcal {L}}_{j}}$significar el elemento más pequeño de${\displaystyle {\mathcal {L}}_{j}}$.
• Utilice una función principal${\displaystyle \pi (i)\,\!}$para definir el árbol de eliminación dentro de la matriz.

El siguiente algoritmo proporciona una factorización simbólica eficiente de A  : ^{[ 3 ]}

${\displaystyle {\begin{aligned}&\pi (i):=0~{\mbox{para todo}}~i\\&{\mbox{Para}}~i:=1~{\mbox{hasta}}~n\\&\qquad {\mathcal {L}}_{i}:={\mathcal {A}}_{i}\\&\qquad {\mbox{Para todo}}~j~{\mbox{tal que}}~\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}}}$