Orientador: Aurelio Ribeiro Leite de OliveiraTese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação CientíficaResumo: Nesta tese é proposta uma modificação no precondicionador Fatoração Controlada de Cholesky (FCC) com o objetivo de aprimorar as iterações iniciais do método primal-dual de Pontos Interiores. O precondicionador FCC, assim como todos os fatores de Cholesky incompletos, podem apresentar falhas na diagonal durante a fatoração. Quando isto acontece, uma correção da falha torna-se necessária. As correções propostas atualmente são muitas vezes insuficientes para continuar com a fatoração e, nesse caso, o processo de fatoração é reiniciado. Assim, o tempo de processamento usado para construir o precondicionador aumenta consideravelmente, pois pode existir até quinze tentativas de correção de falhas, particularmente em problemas de grande porte. Neste trabalho, propõe-se reduzir o número de reinícios na construção do precondicionador FCC modificando tanto o parâmetro de preenchimento, como o cálculo do parâmetro de correção das falhas que ocorrem na diagonal. Por um lado, o cálculo do novo parâmetro de preenchimento é baseado num quociente entre o número de elementos não nulos da matriz do sistema de equações normais e da matriz do problema de programação linear, o que permite classificar a matriz que deve ser fatorada de acordo com sua esparsidade. Esta classificação é feita de tal maneira que o número de elementos não nulos armazenados no precondicionador FCC seja menor ou igual ao número de elementos não nulos na Fatoração Incompleta de Cholesky. Por outro lado, utilizando ferramentas geométricas e algébricas, o cálculo do novo parâmetro de correção das falhas na diagonal é feito considerando a relação entre as entradas do precondicionador FCC obtido antes e depois da falha, isto permite evitar a falha na coluna corrente com apenas um reinício. Desta forma, a melhoria obtida usando estas novas modificações reduz o número de reinícios como sugerido pelos resultados de experimentos numéricos com problemas de programação de grande porte. Os experimentos realizados indicam que estas modificações são robustas e competitivasAbstract: In this thesis a modification is proposed in the preconditioner Cholesky Controlled Factor (FCC) in order to improve the initial iterations of the primal-dual method of interior points. The FCC preconditioner, as well as all incomplete Cholesky factors, May fail diagonally during factorization. When this happens, a fault correction becomes necessary. The proposed corrections are often insufficient to continue with the factorization and, in this case, the factorization process is restarted. Thus, the processing time used to construct the preconditioner increases considerably. There may be up to fifteen attempts to correct faults, particularly in large problems. We propose to reduce the number of restarts in the construction of the CCF preconditioner by modifying both the fill parameter and the calculation of the correction parameter of the faults that occur on the diagonal. On the one hand, the calculation of the new fill parameter is based on a quotient between the number of nonzero elements of the system matrix of normal equations matrix and the number of nonzero elements of the linear programming problem matrix, which allows to classify the matrix that must be factored according to with its sparsity. This classification is done in such a way that the number of nonzero elements stored in the CCF preconditioner is less than or equal to the number of nonzero elements in the Incomplete Cholesky Factorization. On the other hand, using geometric and algebraic tools, the computation of the new diagonal fault correction parameter is done considering the relation between the CCF preconditioner components obtained before and after the fault, this allows to avoid the fault of the current column with only one restart. In this way, the improvement obtained using these new modifications reduces the number of restarts as suggested by the results of numerical experiments with large programming problems. Experiments carried out indicate that these modifications are robust and competitiveMestradoMatematica AplicadaDoutor em Matemática Aplicada140365/2015-0CNPQCAPES