Dissertação (mestrado)–Universidade de Brasília, Universidade UnB de Planaltina, Programa de Pós-Graduação em Ciência de Materiais, 2015. / Submitted by Raquel Viana (raquelviana@bce.unb.br) on 2016-06-01T21:17:59Z No. of bitstreams: 1 2015_WilsonDomingosSidineiAlvesMiranda.pdf: 850688 bytes, checksum: ebf1c7ea3222d989fe0dd442d10edd33 (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2016-06-01T21:18:27Z (GMT) No. of bitstreams: 1 2015_WilsonDomingosSidineiAlvesMiranda.pdf: 850688 bytes, checksum: ebf1c7ea3222d989fe0dd442d10edd33 (MD5) / Made available in DSpace on 2016-06-01T21:18:28Z (GMT). No. of bitstreams: 1 2015_WilsonDomingosSidineiAlvesMiranda.pdf: 850688 bytes, checksum: ebf1c7ea3222d989fe0dd442d10edd33 (MD5) / 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. _______________________________________________________________________________________________ ABSTRACT / One of the main problems in computational linear algebra is the eigenvalue problem Au = lu, where A is usually a matrix of big order. The most effective way to solve this problem is to reduce the matrix A to tridiagonal form and use the method of bisection or QR algorithm to find some or all of the eigenvalues. This work presents a parallel implementation using a combination of methods bisection, secant and Newton-Raphson for solving the eigenvalues problem for Hermitian matrices. Implementation is focused on graphics processing units (GPUs) aimed at use in computers with graphics cards with CUDA architecture. To prove the efficiency and applicability of the implementation, we compare the time spent between the algorithms using the GPU, the CPU and DSTEBZ and DSTEVR routines from LAPACK library. The problem was divided into three phases, tridiagonalization, isolation and extraction, the last two calculated on the GPU. The tridiagonalization by LAPACK’s DSYTRD, calculated on the CPU, proved more efficient than the DSYRDB in CUDA. The use of the method zeroinNR on the extraction phase in CUDA was about two times faster than the bisection method in CUDA. So the hybrid method is more efficient for our case.

Dissertação (mestrado)–Universidade de Brasília, Universidade UnB de Planaltina, Programa de Pós-Graduação em Ciência de Materiais, 2015. / Submitted by Fernanda Percia França (fernandafranca@bce.unb.br) on 2015-12-15T17:59:17Z No. of bitstreams: 1 2015_LindomarJoséRocha.pdf: 1300687 bytes, checksum: f028dc5aba5d9f92f1b2ee949e3e3a3d (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2016-02-29T22:14:44Z (GMT) No. of bitstreams: 1 2015_LindomarJoséRocha.pdf: 1300687 bytes, checksum: f028dc5aba5d9f92f1b2ee949e3e3a3d (MD5) / Made available in DSpace on 2016-02-29T22:14:44Z (GMT). No. of bitstreams: 1 2015_LindomarJoséRocha.pdf: 1300687 bytes, checksum: f028dc5aba5d9f92f1b2ee949e3e3a3d (MD5) / Diversos ramos do conhecimento humano fazem uso de autovalores e autovetores, dentre eles têm-se Física, Engenharia, Economia, etc. A determinação desses autovalores e autovetores pode ser feita utilizando diversas rotinas computacionais, porém umas mais rápidas que outras nesse senário de ganho de velocidade aparece a opção de se usar a computação paralela de forma mais especifica a CUDA da Nvidia é uma opção que oferece um ganho de velocidade significativo, nesse modelo as rotinas são executadas na GPU onde se tem diversos núcleos de processamento. Dada a tamanha importância dos autovalores e autovetores o objetivo desse trabalho é determinar rotinas que possam efetuar o cálculos dos mesmos com matrizes tridiagonais simétricas reais de maneira mais rápida e segura, através de computação paralela com uso da CUDA. Objetivo esse alcançado através da combinação de alguns métodos numéricos para a obtenção dos autovalores e um alteração no método da iteração inversa utilizado na determinação dos autovetores. Temos feito uso de rotinas LAPACK para comparar com as nossas rotinas desenvolvidas em CUDA. De acordo com os resultados, a rotina desenvolvida em CUDA tem a vantagem clara de velocidade quer na precisão simples ou dupla, quando comparado com o estado da arte das rotinas de CPU a partir da biblioteca LAPACK. ______________________________________________________________________________________________ ABSTRACT / Severa branches of human knowledge make use of eigenvalues and eigenvectors, among them we have physics, engineering, economics, etc. The determination of these eigenvalues and eigenvectors can be using various computational routines, som faster than others in this speed increase scenario appears the option to use the parallel computing more specifically the Nvidia’s CUDA is an option that provides a gain of significant speed, this model the routines are performed on the GPU which has several processing cores. Given the great importance of the eigenvalues and eigenvectors the objective of this study is to determine routines that can perform the same calculations with real symmetric tridiagonal matrices more quickly and safely, through parallel computing with use of CUDA. Objective that achieved by some combination of numerical methods to obtain the eigenvalues and a change in the method of inverse iteration used to determine of the eigenvectors, which was used LAPACK routines to compare with routine developed in CUDA. According to the results of the routine developed in CUDA has marked superiority with single or double precision, in the question speed regarding the routines of LAPACK.

[pt] A identificação algorítmica de matrizes de Jacobi a partir de variáveis espectrais é um tema tradicional de análise numérica. Uma nova representação, as coordenadas bidiagonais, naturalmente exigiu que fosse considerado um novo algoritmo. O algoritmo é apresentado e confrontado com as técnicas habituais. / [en] Algorithms relating Jacobi matrices and spectral variables are standard objects in numerical analysis. The recent discovery of bidiagonal coordinates led to the search of an appropriate algorithm for these new variables. The new algorithm is presented and compared with previous techniques.