Fatorações incompletas de Cholesky na solução direta de sistemas lineares oriundos de métodos de pontos interiores

Autor(es)

Luciana Yoshie Tsuchiya

• Tipo de documento: Tese de Doutorado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Matemática, Estatística e Computação Científica
• Data de defesa: 2017-03-02

Membros da banca

Aurelio Ribeiro Leite de Oliveira; Kelly Cristina Poldi; Carla Taviane Lucke da Silva Ghidini; Roberto Quirino do Nascimento; Douglas Soares Gonçalves

• Orientador: Aurelio Ribeiro Leite de Oliveira

Resumo

Uma das abordagens utilizadas para resolver o sistema linear que surge a cada iteração dos métodos de pontos interiores do tipo primal-dual é reduzi-lo a um sistema linear equivalente simétrico definido positivo, conhecido como sistema de equações normais, e aplicar a fatoração de Cholesky na matriz do sistema. A desvantagem desta abordagem é o preenchimento gerado durante a fatoração, o que pode tornar seu uso inviável por limitação de tempo e memória computacional. Neste trabalho, propomos um método que resolve de forma direta, sistemas lineares que se aproximam do sistema de equações normais e que exerce um certo controle sobre o preenchimento. Nossa proposta é na resolução direta deste sistema, substituir a fatoração de Cholesky por uma fatoração incompleta de Cholesky. A ideia é calcular, nas iterações iniciais, soluções aproximadas por meio de sistemas lineares cujas matrizes são fatores incompletos de Cholesky o mais esparsos possíveis. E nas iterações finais, calcular matrizes próximas ou iguais a fatoração de Cholesky completa, de forma que a convergência do método não seja afetada. Experimentos computacionais mostram que a abordagem proposta reduz de forma significativa o tempo de solução dos sistemas lineares nas iterações iniciais dos métodos de pontos interiores, levando a uma redução no tempo total de processamento de grande parte dos problemas testados (AU)

• Processo FAPESP: 13/02089-9 - Estudo da convergência dos métodos de pontos interiores combinados com iteração continuada e algoritmos simples
• Beneficiário: Luciana Yoshie Tsuchiya
• Modalidade de apoio: Bolsas no Brasil - Doutorado