Análise da Influência de Algoritmos de Reordenação de Matrizes Esparsas no Desempenho dos Métodos de Pontos Interiores

• Processo: 10/00010-8
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de outubro de 2010
• Data de Término da vigência: 31 de outubro de 2011
• Área de conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Aurelio Ribeiro Leite de Oliveira
• Beneficiário: Daniele Costa Silva
• Instituição Sede: Faculdade de Engenharia Elétrica e de Computação (FEEC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Métodos de pontos interiores Programação linear
• Palavra(s)-Chave do Pesquisador: Decomposição de Cholesky | Heurísticas de Reordenamento | Métodos de Pontos Interiores | Sistemas Lineares de Grande Porte | Programação Linear

Resumo

Este trabalho consiste em analisar a influência das heurísticas de reordenamento de matrizes esparsas no desempenho do método dos gradientes conjugados precondicionado pela fatoração controlada de Cholesky. Este método tem se mostrado muito eficiente na solução de sistemas lineares de grande porte com matrizes simétricas e definida positiva. Em particular este precondicionador será utilizada nas matrizes oriundas dos métodos de pontos interiores para programação linear. Este precondicionador já tem sido utilizado neste contexto mas sem o reordenamento. Espera-se que o reordenamento possabenefícios como a aceleração da convergência do método e a redução da quantidade de armazenamento utilizado uma vez que a eficiência da fatoração controlada de Cholesky depende da quantidade de elementos não nulos por coluna. Serão estudados heurísticas mais simples como a contagem de colunas e o método de Cuthill-McKee reverso, além de métodos mais sofisticados como o mínimo grau aproximado.

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

SILVA, Daniele Costa. Influência do reordenamento de matrizes no desempenho de métodos de pontos interiores para programação linear. 2015. Tese de Doutorado - Universidade Estadual de Campinas (UNICAMP). Faculdade de Engenharia Elétrica e de Computação Campinas, SP.