Portal de Periódicos da CAPES

O Uso da LexBFS como Alternativa de Reordenamento de Matrizes

2018; Volume: 6; Issue: 2 Linguagem: Português

2359-0793

Priscila Luri Sato, Daniele Costa Silva,

Operations Management Techniques

O reordenamento de matrizes pode ser utilizado como estrategia de reducao de custo computacional na resolucao 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 resolucao de sistemas lineares por metodos diretos; e melhorar a qualidade de precondicionadores baseados em fatoracoes incompletas, o que e benefico na solucao por metodos iterativos. Resultados neste sentido podem ser verificados em diversos trabalhos desde a decada de 60. Atualmente os estudos sobre os impactos de reordenamento de matrizes na resolucao de sistemas lineares se dividem basicamente em duas frentes. Uma em que sao propostas melhorias as heuristicas de reordenamento mais classicas e outra em que sao sugeridas novas alternativas de reordenamento. Nesta ultima, o desafio e melhorar a qualidade da solucao dos sistemas com um tempo de processamento que seja equiparavel as heuristicas mais classicas. Neste contexto, encontra-se o trabalho desenvolvido em [1], que dentre outras tecnicas, faz uso da busca em largura lexicografica (LexBFS) [2], para reordenacao de matrizes de sistemas lineares oriundos de metodos de pontos interiores para programacao linear. A LexBFS nao apresentou bons resultados em termos de tempo computacional em comparacao as heuristicas Cuthill McKee reverso (RCM) e minimo grau, contudo observou-se, para a maioria dos casos, que apos o reordenamento com a LexBFS a estrutura das matrizes e semelhante a aquela obtida apos o reordenamento com a RCM, porem de forma espelhada. O que sugere que com as devidas alteracoes pode gerar resultados tao satisfatorios ou melhores que uma heuristica de reordenamento classica e largamente utilizada como a RCM.