Uma base esparsa para o precondicionador Separador no método dos Pontos Interiores

Resumo

O precondicionador Separador (PS) foi desenvolvido especialmente para reduzir
o mal condicionamento dos sistemas lineares oriundos das últimas iterações dos métodos de Pontos Interiores (MPI). Ele precisa de uma base que é uma submatriz não singular da matriz de restrições do problema, esta base depende fortemente da iteração corrente do MPI pois induz uma ordenação das colunas da matriz de restrições que pode ser aproveitada para melhorar o desempenho deste precondicionador. Propõe-se um novo critério para a escolha da base amparado num resultado que mostra que o número de condição é uniformemente limitado por uma quantidade que independe da iteração do MPI. Por outro lado, uma base esparsa economiza memória no cálculo do PS, o que implica em menor tempo computacional usado para detectar colunas linearmente independentes. Assim, nesta abordagem procurou-se um PS com base esparsa sem deixar de lado o bom condicionamento. A implementação
desta nova abordagem mostrou resultados competitivos.