En el análisis numérico, el algoritmo de grado mínimo es un algoritmo que se utiliza para permutar las filas y columnas de una matriz dispersa simétrica antes de aplicar la descomposición de Cholesky , para reducir el número de no ceros en el factor de Cholesky. Esto da como resultado requisitos de almacenamiento reducidos y significa que el factor Cholesky se puede aplicar con menos operaciones aritméticas. (A veces también puede pertenecer a un factor de Cholesky incompleto utilizado como preacondicionador, por ejemplo, en el algoritmo de gradiente conjugado preacondicionado).
Los algoritmos de grado mínimo se utilizan a menudo en el método de elementos finitos donde el reordenamiento de los nodos se puede llevar a cabo dependiendo solo de la topología de la malla, en lugar de los coeficientes en la ecuación diferencial parcial, lo que resulta en ahorros de eficiencia cuando se usa la misma malla para una variedad de valores de coeficientes.
Dado un sistema lineal
donde A es unmatriz cuadrada dispersa simétrica real. El factor de Cholesky L típicamente sufrirá 'de relleno en', es decir tienen más no-ceros que el triángulo superior de A . Buscamos una matriz de permutación P , de modo que la matriz, que también es simétrico, tiene el menor relleno posible en su factor Cholesky. Resolvemos el sistema reordenado
El problema de encontrar el mejor orden es un problema NP-completo y, por lo tanto, es intratable, por lo que se utilizan métodos heurísticos. El algoritmo de grado mínimo se deriva de un método propuesto por primera vez por Markowitz en 1959 para problemas de programación lineal no simétrica , que se describe vagamente a continuación. En cada paso de la eliminación gaussiana, se realizan permutaciones de fila y columna para minimizar el número de no ceros fuera de la diagonal en la fila y columna de pivote. Tinney y Walker describieron una versión simétrica del método de Markowitz en 1967 y Rose luego derivó una versión teórica de grafos del algoritmo donde la factorización solo se simula, y esto se denominó algoritmo de grado mínimo. El gráfico al que se hace referencia es el gráfico con n vértices, con los vértices i y j conectados por una arista cuandoy el grado es el grado de los vértices. Un aspecto crucial de tales algoritmos es una estrategia de desempate cuando existe la opción de renumerar que resulta en el mismo grado.
Se implementó una versión del algoritmo de grado mínimo en la función de MATLAB symmmd (donde MMD significa grado mínimo múltiple), pero ahora ha sido reemplazado por una función simétrica aproximada de grado mínimo múltiple symamd , que es más rápida. Esto es confirmado por el análisis teórico, que muestra que para gráficos en n vértices y m aristas, MMD tiene un límite superior ajustado de en su tiempo de ejecución, mientras que para AMD un límite estrecho de sostiene.
Referencias
- Markowitz, HM (1957). "La forma de eliminación de la inversa y su aplicación a la programación lineal" . Ciencias de la gestión . 3 (3): 255–269. doi : 10.1287 / mnsc.3.3.255 . JSTOR 2627454 .
- George, Alan; Liu, Joseph (1989). "La evolución del algoritmo de ordenación de grados mínimos". Revisión SIAM . 31 (1): 1–19. doi : 10.1137 / 1031001 . JSTOR 2030845 .
- Tinney, WF; Walker, JW (1967). "Solución directa de ecuaciones de redes dispersas por factorización triangular ordenada de manera óptima". Proc. IEEE . 55 (11): 1801–1809. doi : 10.1109 / PROC.1967.6011 .
- Rose, DJ (1972). "Un estudio de teoría gráfica de la solución numérica de sistemas definidos positivos dispersos de ecuaciones lineales". En Read, RC (ed.). Teoría de grafos y computación . Nueva York: Academic Press. págs. 183–217. ISBN 0-12-583850-6.
- Heggernes, P .; Eisenstat, SC; Kumfert, G .; Pothen, A. (diciembre de 2001), La complejidad computacional del algoritmo de grado mínimo (PDF) (Informe técnico), Instituto de Aplicaciones Informáticas en Ciencias e Ingeniería