Full text
| |
| Author(s): |
Luciana Yoshie Tsuchiya
Total Authors: 1
|
| Document type: | Doctoral Thesis |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Matemática, Estatística e Computação Científica |
| Defense date: | 2017-03-02 |
| Examining board members: |
Aurelio Ribeiro Leite de Oliveira;
Kelly Cristina Poldi;
Carla Taviane Lucke da Silva Ghidini;
Roberto Quirino do Nascimento;
Douglas Soares Gonçalves
|
| Advisor: | Aurelio Ribeiro Leite de Oliveira |
| 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 (AU) | |
| FAPESP's process: | 13/02089-9 - On the convergence of interior point methods combined with continued iteration and simple algorithms |
| Grantee: | Luciana Yoshie Tsuchiya |
| Support Opportunities: | Scholarships in Brazil - Doctorate |