Anais > Edições Anteriores > Anais do XI WCF 2015 > Impacto da ordenação de matrizes por nested dissection nos métodos de pontos interiores

Impacto da ordenação de matrizes por nested dissection nos métodos de pontos interiores

Autores: Wellington Barbosa Rodrigues, Marta Ines Velazco Fontova

Por muitos anos o método simplex foi o mais eficiente para solução de problemas de programação linear. Este método se movimenta pelos pontos extremos do politopo, definido pelas restrições do problema, até uma solução ótima. No pior caso, ele percorre todos os pontos extremos o que caracteriza um método de ordem não polinomial (Vanderbei, 2001).
Karmarkar (Karmarkar, 1984) propôs o primeiro método de pontos interiores de ordem polinomial. Esse método, como o próprio nome diz, trabalha exclusivamente nos pontos interiores da região factível do problema. O passo de maior custo computacional é a resolução de um ou mais sistemas lineares a cada iteração no cálculo das direções de busca (Vanderbei, 2001). Por meio da escolha de métodos eficientes para resolução dos sistemas lineares e da preparação das matrizes, tanto o tempo de solução quanto o consumo de requisitos computacionais podem ser reduzidos.
O uso de métodos de reordenação das matrizes envolvidas no processo da resolução dos sistemas lineares tem apresentado bons resultados em métodos diretos. Alguns dos métodos de reordenação mais utilizados são: mínimo grau (George & Liu, 1994), Cuthill-McKee (Carvalho et al., 2009) e Nested Dissection (George & Liu, 1994).
Para a solução de sistemas lineares oriundos de métodos de pontos interiores por métodos diretos é utilizada a fatoração de Cholesky. Este método, em problemas esparsos cria fatores com maior quantidade de elementos não nulos da matriz. Nesses casos, a reordenação da matriz do sistema proporciona menor preenchimento (George & Liu, 1994).
Em (Carmo, 2005) foi feito um estudo do impacto dos métodos de ordenação na solução de sistemas lineares pelo método do gradiente conjugado precondicionado, utilizando um precondicionador por fatoração controlada de Cholesky. Os resultados mostraram que o método de mínimo grau foi o método de ordenação com melhores resultados após a fatoração controlada de Cholesky; a matriz teve o menor preenchimento causando redução nas iterações do gradiente conjugado.
Este trabalho está organizado em seções. Na Seção 2 são apresentados os métodos de pontos interiores. A Seção 3 descreve os sistemas lineares oriundos de método de pontos interiores. Dois métodos de ordenação para matrizes esparsas serão mostrados na Seção 4. A Seção 5 descreve uma proposta de testes a serem realizados para comparativo entre os métodos de ordenação. Por fim, a Seção 6 apresenta as considerações finais e estudos futuros.

DOCUMENTO COMPLETO

• Impacto da ordenação de matrizes por nested dissection nos métodos de pontos interiores