Factorización LU incompleta

En álgebra lineal numérica , una factorización LU incompleta (abreviada como ILU ) de una matriz es una aproximación dispersa de la factorización LU que se usa a menudo como precondicionador .

Consideremos un sistema lineal disperso.${\displaystyle Ax=b}$Estos problemas suelen resolverse calculando la factorización.${\displaystyle A=LU}$, con L inferior unitrangular y U superior triangular . Luego se resuelve${\displaystyle Ly=b}$,${\displaystyle Ux=y}$, lo cual se puede hacer de manera eficiente porque las matrices son triangulares.

Para una matriz dispersa típica, los factores LU pueden ser mucho menos dispersos que la matriz original , un fenómeno conocido como relleno . Los requisitos de memoria para usar un solucionador directo pueden convertirse entonces en un cuello de botella al resolver sistemas lineales. Este problema se puede mitigar utilizando reordenamientos de las incógnitas de la matriz que reduzcan el relleno, como el algoritmo de grado mínimo .

Una factorización incompleta busca en cambio matrices triangulares L y U tales que${\displaystyle A\approx LU}$en vez de${\displaystyle A=LU}$. Resolviendo para${\displaystyle LUx=b}$se puede hacer rápidamente pero no proporciona la solución exacta a${\displaystyle Ax=b}$. Por lo tanto, en su lugar utilizamos la matriz${\displaystyle M=LU}$como precondicionador en otro algoritmo de solución iterativo como el método del gradiente conjugado o GMRES .

Para una matriz dada${\displaystyle A\in \mathbb {R} ^{n\times n}}$uno define el gráfico${\displaystyle G(A)}$como

${\displaystyle G(A):=\left\lbrace (i,j)\in \mathbb {N} ^{2}:A_{ij}\neq 0\right\rbrace \,,}$

que se utiliza para definir las condiciones de un patrón de escasez${\displaystyle S}$necesidades para satisfacer

${\displaystyle S\subset \left\lbrace 1,\dots ,n\right\rbrace ^{2}\,,\quad \left\lbrace (i,i):1\leq i\leq n\right\rbrace \subset S\,,\quad G(A)\subset S\,.}$

Una descomposición de la forma${\displaystyle A=LU-R}$donde se cumplen las siguientes condiciones

• ${\displaystyle L\in \mathbb {R} ^{n\times n}}$es una matriz unitaria triangular inferior
• ${\displaystyle U\in \mathbb {R} ^{n\times n}}$es una matriz triangular superior
• ${\displaystyle L,U}$son cero fuera del patrón de dispersión:${\displaystyle L_{ij}=U_{ij}=0\quad \forall \;(i,j)\notin S}$
• ${\displaystyle R\in \mathbb {R} ^{n\times n}}$es cero dentro del patrón de dispersión:${\displaystyle R_{ij}=0\quad \forall \;(i,j)\in S}$

se denomina descomposición LU incompleta (con respecto al patrón de escasez)${\displaystyle S}$).

El patrón de dispersión de L y U suele elegirse para que sea el mismo que el de la matriz original A. Si la estructura de la matriz subyacente se puede referenciar mediante punteros en lugar de copiarla, la única memoria adicional necesaria es la de las entradas de L y U. Este precondicionador se denomina ILU(0).

En cuanto a la estabilidad de la ILU, Meijerink y van der Vorst demostraron el siguiente teorema. ^{[ 1 ]}

Dejar${\displaystyle A}$Sea una matriz M , la descomposición LU (completa) dada por${\displaystyle A={\hat {L}}{\hat {U}}}$y el ILU por${\displaystyle A=LU-R}$. Entonces

${\displaystyle |L_{ij}|\leq |{\hat {L}}_{ij}|\quad \forall \;i,j}$

se cumple. Por lo tanto, la ILU es al menos tan estable como la descomposición LU (completa).

Se puede obtener un precondicionador más preciso permitiendo cierto nivel de relleno adicional en la factorización. Una opción común es usar el patrón de dispersión de ^A₂ en lugar de A ; esta matriz es notablemente más densa que A , pero sigue siendo dispersa en general. Este precondicionador se llama ILU(1). Luego se puede generalizar este procedimiento; el precondicionador ILU(k) de una matriz A es la factorización LU incompleta con el patrón de dispersión de la matriz A ^k+1 .

Los precondicionadores ILU más precisos requieren más memoria, hasta el punto de que el tiempo de ejecución del algoritmo aumenta, aunque el número total de iteraciones disminuya. En consecuencia, existe una relación coste/precisión que los usuarios deben evaluar, generalmente caso por caso, dependiendo de la familia de sistemas lineales que se vayan a resolver.

Una aproximación a la factorización ILU puede realizarse como una iteración de punto fijo de forma altamente paralela. ^{[ 2 ]}

• Factorización de Cholesky incompleta

• Saad, Yousef (1996), Métodos iterativos para sistemas lineales dispersos (1.ª  ed.), Boston: PWS, ISBN 978-0-534-94776-7Véase la Sección 10.3 y siguientes.

• Factorización LU incompleta en la wiki de CFD