Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/306759
Type: DISSERTAÇÃO
Degree Level: Mestrado
Title: Solução de sistemas lineares de grande porte usando variantes do método dos gradientes conjugados
Title Alternative: Large scale linear systems solutions using variants of the conjugate gradient method
Author: Coelho, Alessandro Fonseca Esteves
Advisor: Oliveira, Aurelio Ribeiro Leite de, 1962-
Abstract: Resumo: Um método frequentemente utilizado para a solução de problemas de programação linear é o método de pontos interiores. Nestes métodos precisamos resolver sistemas lineares para calcular a direção de Newton a cada iteração. A solução desses sistemas consiste no passo de maior esforço computacional nos métodos de pontos interiores. A fatoração de Cholesky é a opção mais utilizada para resolver estes sistemas. Contudo, quando trabalhamos com problemas de grande porte, esta fatoração pode ser densa e torna-se inviável trabalhar com esses métodos. Nestes casos, uma boa opção consiste no uso de métodos iterativos precondicionados. Estudos anteriores utilizam o método dos gradientes conjugados precondicionado para obter uma solução destes sistemas. Particularmente, os sistemas originados dos métodos de pontos interiores, são, naturalmente, sistemas de equações normais. Porém, a versão padrão do método dos gradientes conjugados, não considera a estrutura de equações normais do sistema. Neste trabalho propomos a utilização de duas versões do método de gradientes conjugados precondicionado que consideram a estrutura de equações normais destes sistemas. Estas versões serão comparadas com a versão de gradientes conjugados precondicionada que não considera a estrutura de equações normais do sistema. Resultados numéricos com problemas de grande porte mostram que uma dessas versões é competitiva em relação à versão padrão

Abstract: An often used method for solving linear programming problems is the interior point method. In these methods we need to solve linear systems to compute the Newton search direction at each iteration. The solution of these systems is the procedure of most computational effort in interior point methods. The Cholesky factorization is the most often used method to solve these systems. However, when dealing with large scale problems, this factorization can be dense and it become impossible to apply such methods. In such cases, a good option is the use of preconditioned iterative methods. Previous studies have used the preconditioned conjugate gradient method to find the solution of these systems. Particularly, the systems arising from interior point methods are, naturally, systems of normal equations type. Nevertheless, the standard version of the conjugate gradient method, does not take into account the normal equations system structure. This study proposes the use of two versions of preconditioned conjugate gradient method considering the normal equations structure of these systems. These versions are compared with the preconditioned conjugate gradient version that does not consider that structure. Numerical results with large scale problems show that one of these versions is competitive with the standard one
Subject: Programação linear
Métodos de pontos interiores
Métodos de gradiente conjugado
Language: Português
Editor: [s.n.]
Citation: COELHO, Alessandro Fonseca Esteves. Solução de sistemas lineares de grande porte usando variantes do método dos gradientes conjugados. 2011. 53 f. Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica, Campinas, SP. Disponível em: <http://www.repositorio.unicamp.br/handle/REPOSIP/306759>. Acesso em: 18 ago. 2018.
Date Issue: 2011
Appears in Collections:IMECC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Coelho_AlessandroFonsecaEsteves_M.pdf2.6 MBAdobe PDFView/Open


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