UMA AVALIAÇÃO DE IMPLEMENTAÇÕES VIA OPENMP E PTHREADS DE DUAS HEURÍSTICAS PARA REDUÇÕES DE LARGURA DE BANDA DE MATRIZES
Redução de largura de banda. Redução de profile. Reordenação. Busca em largura. Reverse Cuthill-McKee. KP-band. Heurísticas. Algoritmos paralelos. Pthreads. OpenMP. Método dos gradientes conjugados precondicionado. Matrizes Esparsas.
Neste trabalho, o objetivo foi propor dois algoritmos paralelos, em arquiteturas multicore, para
solucionar os problemas de reduções de largura de banda e de profile de matrizes esparsas. Para
isso, as linhas e colunas da matriz de coeficientes são permutadas, deixando-a com uma estrutura
compacta, de modo que os coeficientes não nulos estejam próximos à diagonal principal.
Os novos algoritmos paralelos foram comparados a algoritmos disponíveis na biblioteca HSL
e nos softwares Octave e Matlab. Nas simulações, esses algoritmos serão aplicados como um
pré-processamento na resolução de sistemas de equações lineares. Mais especificamente, os
sistemas de equações lineares serão resolvidos pelo método dos gradientes conjugados precondicionado
pela fatoração incompleta de Cholesky, em que a matriz de coeficientes é simétrica e
positiva definida. Uma localidade de memória adequada contribui para a eficiência do método
dos gradientes conjugados precondicionado, e essa característica pode ser obtida por reordenações
de linhas e colunas da matriz de coeficientes. As bibliotecas a serem utilizadas são
OpenMP e Pthreads. Espera-se mostrar a eficácia do(s) novo(s) método(s) e em qual biblioteca
e/ou ambiente de execução o(s) novo(s) algoritmo(s) será(ão) mais eficiente(s).