Melhoria do desempenho da Fatoração Controlada de Cholesky no precondicionamento de Sistemas Lineares oriundos dos Métodos de Pontos Interiores

Resumo

O método de pontos interiores para programação linear resolve em poucas iterações problemas de grande porte. No entanto, requer a cada iteração a resolução de dois sistemas lineares, os quais possuem a mesma matriz de coeficientes. Essa etapa se constitui no passo mais caro do método por aumentar consideravelmente o tempo de processamento e a necessidade de armazenamento de dados. Reduzir o tempo de solução dos sistemas lineares é, portanto, uma forma de melhorar o desempenho do método. De um modo geral, problemas de programação linear de grande porte possuem matrizes esparsas, e os sistemas lineares a serem resolvidos são simétricos positivos definidos. Assim métodos iterativos como o método dos gradientes conjugados precondicionado podem ser utilizados na resolução dos mesmos. Além disso, fatores de Cholesky incompletos podem ser utilizados como precondicionadores do problema. Por outro lado fatorações incompletas podem sofrer falhas na diagonal durante o processo de fatoração. Quando tais falhas ocorrem, é necessário efetuar uma correção, o que em geral ocasiona um aumento no tempo de precondicionamento quer seja devido a reconstrução do precondicionador, quer seja devido a perda de qualidade do mesmo. Neste trabalho propomos uma nova abordagem para a correção de falhas na diagonal ocorridas durante a fatoração controlada de Cholesky. Resultados computacionais mostraram que a técnica pode reduzir significativamente o tempo de resolução de problemas de programação linear via método de pontos interiores.