Fatorações incompletas de Cholesky na solução direta de sistemas lineares oriundos de métodos de pontos interiores
Incomplete Cholesky factorizations for the direct solution of linear systems arising from interior point methods
| dc.creator | Tsuchiya, Luciana Yoshie, 1977- | |
| dc.date | 2017 | |
| dc.date | 2017-03-02T00:00:00Z | |
| dc.date | 2017-07-03T17:25:03Z | |
| dc.date | 2017-07-03T17:25:03Z | |
| dc.date.accessioned | 2018-03-29T03:03:32Z | |
| dc.date.available | 2018-03-29T03:03:32Z | |
| dc.identifier | TSUCHIYA, Luciana Yoshie. Fatorações incompletas de Cholesky na solução direta de sistemas lineares oriundos de métodos de pontos interiores. 2017. 1 recurso online (107 p.). Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica, Campinas, SP. | |
| dc.identifier | http://repositorio.unicamp.br/jspui/handle/REPOSIP/322360 | |
| dc.identifier.uri | http://repositorioslatinoamericanos.uchile.cl/handle/2250/1325474 | |
| dc.description | Orientador: Aurelio Ribeiro Leite de Oliveira | |
| dc.description | Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica | |
| dc.description | 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 | |
| dc.description | 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 | |
| dc.description | Doutorado | |
| dc.description | Matematica Aplicada | |
| dc.description | Doutora em Matemática Aplicada | |
| dc.description | 2013/02089-9 | |
| dc.description | FAPESP | |
| dc.description | CAPES | |
| dc.format | 1 recurso online (107 p.) : il., digital, arquivo PDF. | |
| dc.format | application/pdf | |
| dc.publisher | [s.n.] | |
| dc.relation | Requisitos do sistema: Software para leitura de arquivo em PDF | |
| dc.subject | Programação linear | |
| dc.subject | Fatoração de Cholesky incompleta | |
| dc.subject | Métodos de pontos interiores | |
| dc.subject | Linear programming | |
| dc.subject | Interior-point methods | |
| dc.subject | Incompleta Cholesky factorization | |
| dc.title | Fatorações incompletas de Cholesky na solução direta de sistemas lineares oriundos de métodos de pontos interiores | |
| dc.title | Incomplete Cholesky factorizations for the direct solution of linear systems arising from interior point methods | |
| dc.type | Tesis |