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 distinto de cero para los factores de una matriz dispersa simétrica al aplicar la descomposición de Cholesky o sus variantes. ${\displaystyle L}$

Algoritmo

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

Para implementar una factorización dispersa eficiente, se ha descubierto que es necesario determinar la estructura distinta de cero de los factores antes de realizar cualquier trabajo numérico. Para escribir el algoritmo utilizamos la siguiente notación:

• Sean y sean conjuntos que representan los patrones distintos de cero de las columnas i y j (solo debajo de la diagonal, e incluidos los elementos diagonales) de las matrices A y L respectivamente. ${\displaystyle {\mathcal {A}}_{i}}$ ${\displaystyle {\mathcal {L}}_{j}}$
• Tómelo como el elemento más pequeño de . ${\displaystyle \min {\mathcal {L}}_{j}}$ ${\displaystyle {\mathcal {L}}_{j}}$
• Utilice una función principal para definir el árbol de eliminación dentro de la matriz. ${\displaystyle \pi (i)\,\!}$

El siguiente algoritmo proporciona una factorización simbólica eficiente de A  :

${\displaystyle {\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}}}$