Algoritmo de grau mínimo - Minimum degree algorithm

Em análise numérica, o algoritmo de grau mínimo é um algoritmo usado para permutar as linhas e colunas de uma matriz esparsa simétrica antes de aplicar a decomposição de Cholesky , para reduzir o número de não zeros no fator de Cholesky. Isso resulta em requisitos de armazenamento reduzidos e significa que o fator Cholesky pode ser aplicado com menos operações aritméticas. (Às vezes, também pode pertencer a um fator de Cholesky incompleto usado como um pré-condicionador, por exemplo, no algoritmo de gradiente conjugado pré-condicionado.)

Algoritmos de grau mínimo são frequentemente usados ​​no método dos elementos finitos, onde o reordenamento dos nós pode ser realizado dependendo apenas da topologia da malha, ao invés dos coeficientes na equação diferencial parcial, resultando em economia de eficiência quando a mesma malha é usada para uma variedade de valores de coeficiente.

Dado um sistema linear

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

onde A é uma matriz quadrada esparsa simétrica real. O factor de Cholesky L vai tipicamente sofrem 'de enchimento em', isto é têm mais não-zero do que o triangulo superior de uma . Buscamos uma matriz de permutação P , de forma que a matriz , que também é simétrica, tenha o menor preenchimento possível em seu fator de Cholesky. Resolvemos o sistema reordenado ${\ displaystyle n \ times n}$ ${\ displaystyle \ mathbf {P} ^ {T} \ mathbf {A} \ mathbf {P}}$

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

O problema de encontrar a melhor ordenação é um problema NP-completo e, portanto, intratável; portanto, métodos heurísticos são usados. O algoritmo de grau mínimo é derivado de um método proposto pela primeira vez por Markowitz em 1959 para problemas de programação linear não simétrica , que é descrito vagamente como segue. Em cada etapa da eliminação gaussiana, as permutações de linha e coluna são realizadas de modo a minimizar o número de não-zeros fora da diagonal na linha e coluna do pivô. Uma versão simétrica do método de Markowitz foi descrita por Tinney e Walker em 1967 e Rose posteriormente derivou uma versão teórica de grafos do algoritmo onde a fatoração é apenas simulada, e isso foi denominado algoritmo de grau mínimo. O gráfico referido é o gráfico com n vértices, com os vértices i e j conectados por uma aresta quando , e o grau é o grau dos vértices. Um aspecto crucial de tais algoritmos é uma estratégia de desempate quando há uma opção de renumeração resultando no mesmo grau. ${\ displaystyle a_ {ij} \ neq 0}$

Uma versão do algoritmo grau mínimo foi implementado no MATLAB função symmmd (onde MMD significa grau mínimo múltipla), mas agora foi substituído por uma função de grau mínimo simétrica aproximada múltipla symamd , que é mais rápido. Isto é confirmado pela análise teórica, o que mostra que para um grafo em n vértices e m arestas, tem um MMD apertado limite superior de no seu tempo de funcionamento, ao passo que a AMD para um apertado ligado de reserva. ${\ displaystyle O (n ^ {2} m)}$${\ displaystyle O (nm)}$

Referências

• Markowitz, HM (1957). “A forma de eliminação do inverso e sua aplicação à programação linear” . Ciência da Administração . 3 (3): 255–269. doi : 10.1287 / mnsc.3.3.255 . JSTOR  2627454 .
• George, Alan; Liu, Joseph (1989). "A evolução do Algoritmo de Ordenação de Grau Mínimo". Revisão do SIAM . 31 (1): 1–19. doi : 10.1137 / 1031001 . JSTOR  2030845 .
• Tinney, WF; Walker, JW (1967). "Solução direta de equações de rede esparsas por fatoração triangular ordenada de maneira ótima". Proc. IEEE . 55 (11): 1801-1809. doi : 10.1109 / PROC.1967.6011 .
• Rose, DJ (1972). "Um estudo teórico-gráfico da solução numérica de sistemas definidos positivos esparsos de equações lineares". Em Read, RC (ed.). Teoria de grafos e computação . Nova York: Academic Press. pp. 183–217. ISBN 0-12-583850-6.
• Heggernes, P .; Eisenstat, SC; Kumfert, G .; Pothen, A. (dezembro de 2001), The Computational Complexity of the Minimum Degree Algorithm (PDF) (Relatório técnico), Instituto de Aplicações Computacionais em Ciência e Engenharia