A Study of Reordering Algorithms for Sparse Matrices in the Interior Point Methods Performance

• Grant number: 10/00010-8
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: October 01, 2010
• End date: October 31, 2011
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Aurelio Ribeiro Leite de Oliveira
• Grantee: Daniele Costa Silva
• Host Institution: Faculdade de Engenharia Elétrica e de Computação (FEEC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

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.

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

SILVA, Daniele Costa. Influence of reordering on the performance of interior-point methods for linear programming. 2015. Doctoral Thesis - Universidade Estadual de Campinas (UNICAMP). Faculdade de Engenharia Elétrica e de Computação Campinas, SP.