Algoritmo paralelo para determinação de autovalores de matrizes hermitianas

Abstract

Um dos principais problemas da álgebra linear computacional é o problema de autovalor, Au = lu, onde A é usualmente uma matriz de ordem grande. A maneira mais efetiva de resolver tal problema consiste em reduzir a matriz A para a forma tridiagonal e usar o método da bissecção ou algoritmo QR para encontrar alguns ou todos os autovalores. Este trabalho apresenta uma implementação em paralelo utilizando uma combinação dos métodos da bissecção, secante e Newton-Raphson para a solução de problemas de autovalores de matrizes hermitianas. A implementação é voltada para unidades de processamentos gráficos (GPUs) visando a utilização em computadores que possuam placas gráficas com arquitetura CUDA. Para comprovar a eficiência e aplicabilidade da implementação, comparamos o tempo gasto entre os algoritmos usando a GPU, a CPU e as rotinas DSTEBZ e DSTEVR da biblioteca LAPACK. O problema foi dividido em três fases, tridiagonalização, isolamento e extração, as duas últimas calculadas na GPU. A tridiagonalização via DSYTRD da LAPACK, calculada em CPU, mostrou-se mais eficiente do que a realizada em CUDA via DSYRDB. O uso do método zeroinNR na fase de extração em CUDA foi cerca de duas vezes mais rápido que o método da bissecção em CUDA. Então o método híbrido é o mais eficiente para o nosso caso.