Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/322360
Type: TESE DIGITAL
Title: Fatorações incompletas de Cholesky na solução direta de sistemas lineares oriundos de métodos de pontos interiores
Title Alternative: Incomplete Cholesky factorizations for the direct solution of linear systems arising from interior point methods
Author: Tsuchiya, Luciana Yoshie, 1977-
Advisor: Oliveira, Aurelio Ribeiro Leite de, 1962-
Abstract: 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

Abstract: One of the most commonly used approaches to solve the normal equation systems arising in primal-dual interior point methods is the direct solution by using the Cholesky factorization of the matrix system. The major disadvantage of this approach is the fill-in, which can make its use impracticable, due to time and memory limitations. In this work, we propose a method that directly solves an approximated system of normal equation keeping the fill-in under control. In our proposal, in the normal equation system direct solution, we replace the Cholesky factorization by an incomplete Cholesky factorization. The idea is to compute approximate solutions in the early iterations by linear systems whose matrices are incomplete Cholesky factors as sparses as possible and in the final iterations, to compute matrices close or equal to the complete Cholesky factorization so that the method convergence is kept. Computational experiments show that the proposed approach significantly reduces the linear systems solution time in the interior points methods in early iterations, leading to a reduction in the total processing time for many of the tested problems
Subject: Programação linear
Fatoração de Cholesky incompleta
Métodos de pontos interiores
Editor: [s.n.]
Date Issue: 2017
Appears in Collections:IMECC - Dissertação e Tese

Files in This Item:
File SizeFormat 
Tsuchiya_LucianaYoshie_D.pdf936.91 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.