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 basados ​​en particiones gráficas . 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 representen filas y columnas del sistema de ecuaciones lineales, y un borde represente una entrada distinta de cero en la matriz dispersa que representa el sistema.
• Divida 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 quitar 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) se limita como máximo al cuadrado del tamaño del separador en cada nivel del recursivo. dividir. En particular, para gráficos planos (que surgen frecuentemente en la solución de sistemas lineales dispersos derivados de mallas bidimensionales del método de elementos finitos ), la matriz resultante tiene O ( n  log  n ) no ceros, debido al teorema del separador plano que garantiza separadores de tamaño O ( √ n ). ^[2] Para gráficos arbitrarios hay una disección anidada que garantiza el relleno dentro de un${\displaystyle O(\min\{{\sqrt {d}}\log ^{4}n,m^{1/4}\log ^{3.5}n\})}$factor de óptimo, donde d es el grado máximo y m es el número de no ceros. ^[3]

Ver 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 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), "Reducir el relleno mediante disección anidada: ordenamientos de eliminación comprobablemente buenos", teoría de grafos y cálculo de matrices dispersas , Springer New York, págs. 31-55, doi : 10.1007 / 978-1-4613- 8369-7_2 , ISBN 978-1-4613-8371-0.