cedesc - 2010

CEDESC -­ 2010 AVALIAÇÃO DO CURSO DE FORTRAN Dada a seguinte matriz: Renato N. Elias ([email protected]) ⎛
⎜
A = ⎜
⎜
⎜⎝
1.
0.
5.
0.
0.
3.
0.
6.
2.
0.
0.
0.
0.
4.
0.
7.
⎞
⎟
⎟ ⎟
⎟⎠
originalmente armazenada no formato coordenado (COO): 1 1 1.
1 3 2.
2 2 3.
2 4 4.
3 1 5.
4 2 6.
4 4 7.
Quando armazenada no formato CSR (Compressed Sparse Row) a matriz A dá origem aos seguintes arranjos: AA(nnz) 1. 2. 3. 4. 5. 6. 7.
IA(nnz)
1
3
2
4
1
JA(n+1)
1
3
5
6
9
2
4
onde: nnz: número de elementos não-­‐nulos n = número de linhas AA: coeficientes da matriz IA: índice das colunas JA: indice das linhas. Note que: JA(i+1)-JA(i) = número de elementos não nulos da linha i Com base no exemplo descrito acima: 1. Desenvolva uma subrotina, em Fortran 90, capaz de converter uma matriz armazenada no formato COO (Coordinate) para o formato CSR (Compressed Sparse Row). Teste a rotina desenvolvida, em uma matriz qualquer armazenada em um arquivo, salvando o resultado da conversão em um outro arquivo qualquer. 2. Proponha uma forma de acesso aos coeficientes do arranjo AA, do formato CSR, com base nos indices de linha e coluna geralmente utilizados para se acessar coeficientes de uma matriz. 3. Dada uma fatoração LU , armazenada no formato CSR1, obtenha a solução do sistema LUx = b (lembrando que Ux = y e Ly = b ) OBSERVAÇÃO: Considere aspectos de eficiência e generalidade em seu algoritmo. REFERÊNCIA: Yousef Saad, Iterative methods for sparse linear systems, SIAM, 2a. edição Disponível gratuitamente no site do autor: http://www-­‐users.cs.umn.edu/~saad/books.html 1 Não é necessário calcular a fatoração. Basta utilizar uma fatoração qualquer, calculada por algum outro software ou, até mesmo, obtida em livros, internet, etc…