Introdução a Computação Paralela

Projeto Final

Parte A

Implementar uma versão em paralelo do algoritmo de multiplicação de uma matriz A (densa) por um vetor y.

Parte B

Utilizando o algoritmo anterior, implementar uma versão em paralelo do algoritmo do método da potência que obtém o maior autovalor em módulo de uma matriz A.

The method is described by the iteration

 p       =  A*b_k
 b_{k+1} =  p/||p||_2

onde o autovalor é aproximado por

 lambda  =  b_k^T * A * b_k
            ---------------
               b_k^T * b_k

• http://en.wikipedia.org/wiki/Power_iteration

Parte C

Implementar o algoritmo gradiente conjugado em paralelo para a resolução de sistemas.

• Painless introduction to CG, http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf
• C. T. Kelley, Iterative Methods for Linear and Nonlinear Equations, http://www.siam.org/books/textbooks/fr16_book.pdf
• Dicas para implementação do CG, http://www.cs.usfca.edu/~peter/cs625/prog2.pdf

Parte D1

Utilizar o algoritmo CG para a solução de um problema de elementos finitos em paralelo.

Parte D2

Resolver a equação de Poisson em 2D utilizando diferenças finitas e condição de Dirichlet em todas as faces (note que o sistema obtido é simétrico).

• http://www.cs.berkeley.edu/~demmel/cs267/lecture17/lecture17.html

Referências

• Introduction to Parallel Computing, Grama, Karypis, Kumar, Gupta
• Parallel Programming: for Multicore and Cluster Systems, Thomas Rauber, Gudula Rünger