O Uso da LexBFS como Alternativa de Reordenamento de Matrizes

Resumen

O reordenamento de matrizes pode ser utilizado como estratégia de redução de custo computacional na resolução de sistemas lineares, em especial, os de grande porte e esparsos. Ao permutar linhas e colunas de uma matriz de coeficientes espera-se diminuir o preenchimento e tempo de processamento na resolução de sistemas lineares por métodos diretos; e melhorar a qualidade de precondicionadores baseados em fatorações incompletas, o que é benéfico na solução por métodos iterativos. Resultados neste sentido podem ser verificados em diversos trabalhos desde a década de 60. Atualmente os estudos sobre os impactos de reordenamento de matrizes na resolução de sistemas lineares se dividem basicamente em duas frentes. Uma em que são propostas melhorias às heurı́sticas de reordenamento mais clássicas e outra em que são sugeridas novas alternativas de reordenamento. Nesta última, o desafio é melhorar a qualidade da solução dos sistemas com um tempo de processamento que seja equiparável as heurı́sticas mais clássicas. Neste contexto, encontra-se o trabalho desenvolvido em [1], que dentre outras técnicas, faz uso da busca em largura lexicográfica (LexBFS) [2], para reordenação de matrizes de sistemas lineares oriundos de métodos de pontos interiores para programação linear. A LexBFS não apresentou bons resultados em termos de tempo computacional em comparação as heurı́sticas Cuthill McKee reverso (RCM) e mı́nimo grau, contudo observou-se, para a maioria dos casos, que após o reordenamento com a LexBFS a estrutura das matrizes é semelhante a aquela obtida após o reordenamento com a RCM, porém de forma espelhada. O que sugere que com as devidas alterações pode gerar resultados tão satisfatórios ou melhores que uma heurı́stica de reordenamento clássica e largamente utilizada como a RCM.