Experimentos numéricos com um sistema linear alternativo para o pré-condicionador separador aplicado a métodos de pontos interiores

Resumo

Em trabalhos anteriores, uma abordagem hı́brida de pré-condicionamento dos sistemas lineares oriundos da aplicação da proposta de Mehrotra, para resolver problemas de programação linear, foi desenvolvida e aprimorada. Foram considerados o pré-condicionador da Fatoração Controlada de Cholesky, com preenchimento adaptativo em função da memória disponı́vel no computador, e o pré-condicionador separador, especializado para as iterações finais dos métodos de pontos interiores. Um dos blocos da matriz pré-condicionada, que é diagonal por blocos, foi reduzido a um sistema definido positivo de dimensão igual à di-
ferença entre o número de colunas e linhas da matriz de restrições. Desenvolvemos duas abordagens para resolver o sistema resultante usando o método de Gradientes Conjugados pré-condicionado. Comparamos as três abordagens e aferimos o desempenho das versões utilizando quatro métricas. Os resultados apontam que as versões desenvolvidas neste trabalho têm melhor comportamento computacional e desempenho superior.