Disección anidada

En el análisis numérico , la disección anidada es una heurística de divide y vencerás para la solución de sistemas simétricos dispersos de ecuaciones lineales basadas en la partición de grafos . La disección anidada fue introducida por George (1973); el nombre fue sugerido por Garrett Birkhoff . ^[1]

La disección anidada consta de los siguientes pasos:

• Forme un gráfico no dirigido en el que los vértices representan filas y columnas del sistema de ecuaciones lineales, y una arista representa una entrada distinta de cero en la matriz dispersa que representa el sistema.
• Particionar recursivamente el gráfico en subgráficos utilizando separadores , pequeños subconjuntos de vértices cuya eliminación permite dividir el gráfico en subgráficos con como máximo una fracción constante del número de vértices.
• Realizar la descomposición de Cholesky (una variante de la eliminación gaussiana para matrices simétricas), ordenando la eliminación de las variables por la estructura recursiva de la partición: se elimina primero cada uno de los dos subgrafos formados al eliminar el separador, y luego se eliminan los vértices del separador.

Como consecuencia de este algoritmo, el relleno (el conjunto de entradas de matriz distintas de cero creadas en la descomposición de Cholesky que no forman parte de la estructura de la matriz de entrada) está limitado como máximo al cuadrado del tamaño del separador en cada nivel de la partición recursiva. En particular, para los grafos planares (que surgen con frecuencia en la solución de sistemas lineales dispersos derivados de mallas de métodos de elementos finitos bidimensionales ) la matriz resultante tiene O( n  log  n ) distintos de cero, debido a que el teorema del separador planar garantiza separadores de tamaño O( √ n ). ^[2] Para grafos arbitrarios existe una disección anidada que garantiza el relleno dentro de un factor de óptimo, donde d es el grado máximo y m es el número de distintos de cero. ^[3] ${\displaystyle O(\min\{{\sqrt {d}}\log ^{4}n,m^{1/4}\log ^{3.5}n\})}$

Véase también

• El rango de ciclo de un gráfico, o una matriz booleana simétrica, mide el tiempo paralelo mínimo necesario para realizar la descomposición de Cholesky.
• Separador de vértices

Notas

1. George (1973).
2. Lipton, Rose y Tarjan (1979); Gilbert y Tarjan (1986).
3. Agrawal, Klein y Ravi (1993).

Referencias

• George, J. Alan (1973), "Disección anidada de una malla regular de elementos finitos", SIAM Journal on Numerical Analysis , 10 (2): 345–363, doi :10.1137/0710032, JSTOR  2156361.
• Gilbert, John R. (1988), "Un cierto orden de disección anidado es casi óptimo", Information Processing Letters , 26 (6): 325–328, doi :10.1016/0020-0190(88)90191-3, hdl : 1813/6607.
• Gilbert, John R.; Tarjan, Robert E. (1986), "El análisis de un algoritmo de disección anidado", Numerische Mathematik , 50 (4): 377–404, doi :10.1007/BF01396660.
• Lipton, Richard J. ; Rose, Donald J. ; Tarjan, Robert E. (1979), "Disección anidada generalizada", SIAM Journal on Numerical Analysis , 16 (2): 346–358, doi :10.1137/0716027, JSTOR  2156840.
• Agrawal, Ajit; Klein, Philip; Ravi, R. (1993), "Reducción del relleno mediante disección anidada: ordenamientos de eliminación demostrablemente buenos", Graph Theory and Sparse Matrix Computation , Springer Nueva York, págs. 31–55, doi :10.1007/978-1-4613-8369-7_2, ISBN 978-1-4613-8371-0.