Un algoritmo de ordenación aproximado de grado mínimo

Se presenta un algoritmo de ordenación aproximado de grado mínimo (AMD) para preordenar una matriz dispersa simétrica antes de la factorización numérica. Utilizamos técnicas basadas en el grafo cociente para la factorización de matrices que nos permiten obtener límites computacionalmente económicos para el grado mínimo. Demostramos que estos límites a menudo son iguales al grado real. El algoritmo resultante es típicamente mucho más rápido que los algoritmos de ordenación de grado mínimo anteriores y produce resultados que son comparables en calidad con los mejores ordenamientos de otros algoritmos de grado mínimo.