algoritmo de grado mínimo

En análisis numérico , el algoritmo de grado mínimo se utiliza para permutar las filas y columnas de una matriz dispersa simétrica antes de aplicar la descomposición de Cholesky , con el fin de reducir el número de elementos no nulos en el factor de Cholesky. Esto reduce los requisitos de almacenamiento y permite aplicar el factor de Cholesky con menos operaciones aritméticas. (En ocasiones, también puede referirse a un factor de Cholesky incompleto utilizado como precondicionador, por ejemplo, en el algoritmo de gradiente conjugado precondicionado).

Los algoritmos de grado mínimo se utilizan a menudo en el método de elementos finitos, donde la reordenación de los nodos se puede llevar a cabo dependiendo únicamente de la topología de la malla, en lugar de los coeficientes de la ecuación diferencial parcial, lo que resulta en un ahorro de eficiencia cuando se utiliza la misma malla para una variedad de valores de coeficientes.

Dado un sistema lineal

${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }$

donde A es un${\displaystyle n\times n}$matriz cuadrada dispersa simétrica real. El factor de Cholesky L normalmente sufrirá 'relleno', es decir, tendrá más elementos distintos de cero que el triángulo superior de A. Buscamos una matriz de permutación P , de modo que la matriz ${\displaystyle \mathbf {P} ^{T}\mathbf {A} \mathbf {P} }$, que también es simétrico, tiene el menor llenado posible en su factor de Cholesky. Resolvemos el sistema reordenado

${\displaystyle \left(\mathbf {P} ^{T}\mathbf {A} \mathbf {P} \right)\left(\mathbf {P} ^{T}\mathbf {x} \right)=\mathbf {P} ^{T}\mathbf {b} .}$

El problema de encontrar el mejor ordenamiento es un problema NP-completo y, por lo tanto, 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 de forma general de la siguiente manera. En cada paso de la eliminación gaussiana , se realizan permutaciones de filas y columnas para minimizar el número de elementos no nulos fuera de la diagonal en la fila y columna pivote. Tinney y Walker describieron una versión simétrica del método de Markowitz en 1967, y Rose derivó posteriormente una versión teórica de grafos del algoritmo donde la factorización solo se simula, y esta se denominó algoritmo de grado mínimo. El grafo al que se hace referencia es el grafo con n vértices, con los vértices i y j conectados por una arista cuando${\displaystyle a_{ij}\neq 0}$y el grado es el grado de los vértices. Un aspecto crucial de estos algoritmos es una estrategia de desempate cuando hay que elegir una renumeración que dé como resultado el mismo grado.

Se implementó una versión del algoritmo de grado mínimo en la función symmmd de MATLAB (donde MMD significa grado mínimo múltiple), pero ahora ha sido reemplazada por una función aproximada simétrica de grado mínimo múltiple , symamd , que es más rápida. Esto se confirma mediante un análisis teórico, que muestra que para grafos con n vértices y m aristas, MMD tiene una cota superior ajustada de${\displaystyle O(n^{2}m)}$en su tiempo de ejecución, mientras que para AMD un límite estricto de${\displaystyle O(nm)}$sostiene. Cummings, Fahrbach y Fatehpuria diseñaron un algoritmo de grado mínimo exacto con${\displaystyle O(nm)}$tiempo de ejecución, y demostró que no puede existir ningún algoritmo que se ejecute en tiempo${\displaystyle O(nm^{1-\varepsilon })}$, para cualquier${\displaystyle \varepsilon >0}$, asumiendo la hipótesis del tiempo exponencial fuerte .

• Cummings, Robert; Fahrbach, Matthew; Fatehpuria, Animesh (2021). «Un algoritmo rápido de grado mínimo y su correspondiente cota inferior». Actas del 32.º Simposio Anual ACM-SIAM sobre Algoritmos Discretos : 724–734 . arXiv : 1907.12119 . doi : 10.1137/1.9781611976465.45 . ISBN 978-1-61197-646-5. S2CID 198968052 . 
• George, Alan; Liu, Joseph (1989). "La evolución del algoritmo de ordenación de grado mínimo". SIAM Review . 31 (1): 1– 19. doi : 10.1137/1031001 . JSTOR 2030845 . OSTI 5686483 .  
• Heggernes, P .; Eisenstat, SC; Kumfert, G.; Pothen, A. (2001), La complejidad computacional del algoritmo de grado mínimo (PDF) (Informe técnico), Instituto de Aplicaciones Informáticas en Ciencia e Ingeniería
• Markowitz, HM (1957). «La forma de eliminación de la inversa y su aplicación a la programación lineal» . Management Science . 3 (3): 255– 269. doi : 10.1287/mnsc.3.3.255 . JSTOR 2627454. Archivado del original el 24 de septiembre de 2017. 
• Rose, DJ (1972). «Un estudio teórico de grafos sobre la solución numérica de sistemas dispersos definidos positivos de ecuaciones lineales». Graph Theory and Computing . Academic Press. pp. 183–217 . ISBN  0-12-583850-6.
• Tinney, WF; Walker, JW (1967). "Solución directa de ecuaciones de redes dispersas mediante factorización triangular óptimamente ordenada". Proc. IEEE . 55 (11): 1801– 1809. doi : 10.1109/PROC.1967.6011 .