Aplicação de Grafos Cordais a Sistemas Lineares Esparsos

Apresentamos um método para tornar um grafo conexo em cordal, através da inserção de novas arestas no grafo. A principal motivação deste problema é resolver sistemas lineares esparsos de grande porte através do método de eliminação de Gauss. O método de eliminação de Gauss, quando aplicado a esses sistemas esparsos, provoca, em geral, preenchimento na matriz associada. Consideraremos o problema supondo a matriz quadrada, simétrica e definida positiva, e a representaremos por um grafo. Nosso objetivo é tornar esse grafo cordal com a inserção do menor número de arestas possível. Com relação à resolução do sistema linear através do método de eliminação de Gauss, isso é equivalente a encontrar uma ordem de pivoteamento na matriz que acarretará num menor preenchimento com elementos não-nulos. Apresentaremos um modelo de programação linear inteira mista para o problema do preenchimento mínimo em um grafo conexo para torná-lo cordal e por fim, apresentaremos alguns resultados numéricos obtidos através do software XPRESS-MP.