Departamento de Ciência da Computação

Prof responsável: Sanderson

Aluno: Júnior Assis – Este endereço de email está sendo protegido de spambots. Você precisa do JavaScript ativado para vê-lo.

A resolução de sistemas de equações lineares é crucial para diversas simulações na ciência, principalmente nas modelagens realizadas na engenharia. Essa resolução, geralmente, é responsável por grande parte do custo computacional envolvido em tais simulações. Esse projeto tem como objetivo avaliar heurísticas para a redução de profile de matrizes para a redução do custo computacional de resolução de sistemas de equações lineares pelo método dos gradientes conjugados, que foi proposto no início da década de 1950. Reduzir o profile de uma matriz quadrada significa, em linhas gerais, deixar todos os elementos não nulos da matriz próximos à diagonal principal da matriz. Esse problema não é facilmente resolvido computacionalmente e, portanto, há uma série de heurísticas propostas para resolvê-lo de maneira eficiente, com soluções razoáveis que se aproximam da solução ótima. A metodologia adotada nesse projeto é identificar as heurísticas propostas na literatura para a redução de profile e analisar os seus resultados em comparação com outras heurísticas. Após a identificação das possíveis melhores heurísticas para a redução de profile, as mesmas serão implementadas em C++ e aplicadas para reduzir o profile de matrizes de coeficientes de sistemas de equações lineares de grande porte, que serão resolvidos pelo método dos gradientes conjugados pré-condicionado. Além disso, serão estudados e avaliados alguns pré-condicionadores para o método dos gradientes conjugados para se identificar aquele com a melhor contribuição para a redução do custo computacional do método dos gradientes conjugados. Ao final do projeto, espera-se encontrar a heurística proposta para a redução do profile que possui a maior contribuição para a redução do método dos gradientes conjugados pré-condicionado.