tc

Prévia do material em texto

Universidade Federal do Esp´ırito Santo
Departamento de Informa´tica
Algoritmos Nume´ricos 2011/2
Profa. Claudine Badue
Trabalho Computacional
Me´todos Iterativos para Resoluc¸a˜o de Sistemas Lineares
Utilizando Armazenamento Tradicional e Otimizado
Objetivo
Implementar e avaliar o desempenho de me´todos iterativos para resoluc¸a˜o de sistemas lineares esparsos
de grande porte utilizando armazenamento tradicional e otimizado.
Descric¸a˜o
Frequentemente, os processos de soluc¸a˜o de problemas das mais diversas a´reas do conhecimento recaem
na necessidade de resolver sistemas lineares. Na maioria das vezes, esses sistemas sa˜o esparsos e de
grande porte. O esquema de armazenamento otimizado e´ crucial na eficieˆncia do me´todo nume´rico
considerado, tanto em economia de memo´ria quanto em operac¸o˜es de ponto flutuante, que impactam
diretamente o tempo de processamento.
O objetivo deste trabalho e´ implementar e avaliar o desempenho dos me´todos iterativos de Gauss-
Seidel e Successive Over-Relaxation (SOR) [Campos, 2007] na resoluc¸a˜o de sistemas lineares esparsos
de grande porte, considerando:
• o esquema de armazenamento tradicional, ou denso, que armazena a matriz em uma estrutura
bidimensional;
• o esquema de armazenamento otimizado por linha, ou Compress Sparse Row (CSR), que ar-
mazena somente os coeficientes na˜o nulos de uma matriz esparsa em um vetor ordenado por
linha. Ale´m desse vetor, e´ necessa´rio armazenar informac¸o˜es adicionais sobre a localizac¸a˜o dos
coeficientes nas linhas e colunas. Maiores detalhes sobre o esquema de armazenamento CSR
podem ser encontrados em Catabriga (2011) e Fernandes (2011).
Seja um sistema Ax = b com a matriz dos coeficientes A armazenada utilizando os esquemas denso
ou CSR.
• Implemente, para cada esquema de armazenamento, uma func¸a˜o para calcular a soluc¸a˜o do
sistema pelo me´todo iterativo de Gauss-Seidel, tendo como paraˆmetros de entrada:
– a matriz esparsa A,
– o vetor dos termos independentes b,
– a toleraˆncia Toler, e
– o nu´mero ma´ximo de iterac¸o˜es IterMax.
• Implemente, para cada esquema de armazenamento, uma func¸a˜o para calcular a soluc¸a˜o do
sistema pelo me´todo iterativo SOR, tendo como paraˆmetros de entrada:
– a matriz esparsa A,
– o vetor dos termos independentes b,
– a toleraˆncia Toler,
– o nu´mero ma´ximo de iterac¸o˜es IterMax, e
1
– o paraˆmetro Omega. Observe que se Omega = 1, tem-se o me´todo de Gauss-Seidel.
Utilize as equac¸o˜es de iterac¸o˜es dos me´todos de Gauss-Seidel e SOR, ao inve´s das matrizes de
iterac¸a˜o. A condic¸a˜o inicial pode ser dada por x0i = bi/aii, para i = 1, ..., n.
Validac¸a˜o
Para validar os algoritmos implementados, utilize o reposito´rio Matrix Market1, que disponibiliza uma
quantidade considera´vel de matrizes esparsas de grande porte oriundas das mais diversas a´reas para
apoio a estudos comparativos de algoritmos nume´ricos.
A Figura 1 apresenta 6 exemplos de matrizes esparsas depositadas no Matrix Market. A Tabela 1
apresenta algumas propriedades dessas matrizes.
Tabela 1: Algumas propriedades das matrizes do reposito´rio Matrix Market.
Matriz Colec¸a˜o/Conjunto A´rea de Aplicac¸a˜o n nnz
BCSSTK03 Harwell-Boeing/BCSSTRUC1 Engenharia Estrutural 112 376
HOR131 Harwell-Boeing/NNCENG Conservac¸a˜o de Energia 434 4710
GR3030 Harwell-Boeing/LAPLACE Discretizac¸a˜o do Laplaciano 900 4322
ORSIRR1 Harwell-Boeing/OILGEN Simulac¸a˜o de Reservato´rios 1030 6858
PLAT1919 Harwell-Boeing/PLATZ Modelo Oceanogra´fico 1919 17159
SHERMAN5 Harwell-Boeing/SHERMAN Recuperac¸ ao de Petro´leo 3312 20793
Na Tabela 1, a primeira coluna mostra o nome da matriz; a segunda coluna, o nome da colec¸a˜o e do
conjunto associados a` matriz; a terceira coluna, a a´rea de aplicac¸a˜o da matriz; a quarta coluna, a ordem
da matriz; e a quinta coluna, o nu´mero de coeficientes na˜o nulos da matriz. Todas as informac¸o˜es
sobre as matrizes podem ser obtidas navegando no reposito´rio Matrix Market atrave´s das colec¸o˜es e
conjuntos referenciados na Tabela 1.
As matrizes sa˜o disponibilizadas em arquivos do tipo mtx. A Figura 2 apresenta o arquivo do tipo
mtx da matriz BCSSTK03 (referenciada na segunda linha da Tabela 1), denominado bcsstk03.mtx.
No arquivo apresentado na Figura 2, a segunda linha armazena o nu´mero de linhas (112), o nu´mero
de colunas (112) e o nu´mero de coeficientes na˜o nulos da matriz (376); a terceira linha armazena
a linha (1), a coluna (1), e o valor (≈ 2.9697 × 108) do primeiro coeficiente na˜o nulo da matriz; a
quarta linha armazena a linha (4), a coluna (1), e o valor (≈ 4.5073× 109) do segundo coeficiente na˜o
nulo da matriz; e assim por diante. Observe que os coeficientes na˜o nulos esta˜o listados por coluna.
Entretanto, o esquema de armazenamento CSR armazena os coeficientes na˜o nulos por linha. Por
questa˜o de simplicidade, neste trabalho sera´ considerada a matriz transposta, At, como matriz dos
coeficientes do sistema
Atx = b (1)
onde
A e´ a matriz oriunda do arquivo do tipo mtx;
x e´ o vetor soluc¸a˜o; seu valor exato e´ x = (1 1 1 ... 1)t;
b = Atx ⇒ bi =
∑n
i=1 aji.
Dado o arquivo do tipo mtx como paraˆmetro de entrada, as func¸o˜es densa.m e csr.m leˆem o
arquivo, armazenam a matriz At atrave´s do respectivo esquema de armazenamento, e geram o vetor
dos termos independentes b tal que x = (1 1 1 ... 1)t. As func¸o˜es densa.m e csr.m esta˜o dispon´ıveis
em http://www.inf.ufes.br/∼claudine/courses/an11 2/#Trabalho Computacional.
1http://math.nist.gov/MatrixMarket
2
(a) BCSSTK03, n = 112, nnz = 376 (b) HOR131, n = 434, nnz = 4710
(c) GR3030, n = 900, nnz = 4322 (d) ORSIRR1, n = 1030, nnz = 6858
(e) PLAT1919, n = 1919, nnz = 17159 (f) SHERMAN5, n = 3312, nnz= 20793
Figura 1: Exemplos de matrizes do reposito´rio MatrixMarket.
3
Figura 2: Arquivo bcsstk03.mtx da matriz BCSSTK03 do reposito´rio Matrix Market.
Experimentos Nume´ricos
Para cada uma das 6 matrizes esparsas A listadas na Tabela 1:
• Encontre, de forma emp´ırica, o paraˆmetro Omega o´timo do me´todo SOR com Toler = 10−6;
• Fac¸a um estudo comparativo com relac¸a˜o ao nu´mero de iterac¸o˜es e tempo de execuc¸a˜o para os
me´todos iterativos de Gauss-Seidel e SOR (usando o paraˆmetro Omega o´timo) com Toler =
10−6, e os esquemas de armazenamento denso e CSR.
Observac¸o˜es:
• Os experimentos nume´ricos descritos acima sa˜o obrigato´rios. E´ bom lembrar que outros experi-
mentos podem ser incorporados ao relato´rio com o objetivo de enriquecer seu trabalho.
• Se existirem experimentos na˜o convergentes, explique no relato´rio as poss´ıveis causas e reporte
os resultados com IterMax = 100.
• O Octave tem uma forma simples de medir tempo de execuc¸a˜o usando os comandos tic e toc.
Relato´rio
O relato´rio devera´ conter as seguintes sesso˜es:
• Introduc¸a˜o: onde o grupo devera´ apresentar a estrutura do trabalho e os objetivos;
• Esquemas de Armazenamento Denso e CSR, e Me´todos Iterativos: onde o grupo descrevera´ os
esquemas de armazenamento denso e CSR, e os me´todos iterativos de Gauss-Seidel e SOR;
• Implementac¸a˜o: onde sera˜o apresentados a estrutura do co´digo e partes significativas do co´digo
comentado;
• Experimentos Nume´ricos: onde sera˜o apresentados os experimentos nume´ricos realizados pelo
grupo, tanto as entradas para os programas quanto os resultados obtidos em tabelas e/ou gra´ficos.
• Conclusa˜o: onde sera˜o discutidos os resultados obtidos.
Instruc¸o˜es para Entrega
• Este trabalho devera´ ser desenvolvido em grupos de duas (e somente duas) pessoas. Na˜o sera˜o
aceitos grupos de treˆs ou uma u´nica pessoa. Se houver um nu´mero ı´mpar de alunos, sera´ aceito
um u´nico grupo com uma u´nica pessoa.
4
• O relato´rio devera´ ser entregue impresso em aula ate´ a data limite de entrega.
• O co´digo e o relato´rio (em pdf) devera˜o ser enviados por e-mail ate´ a`s 23:59 horas da data limite
de entrega, adotando-se os seguintes procedimentos:
– Agrupe, em um arquivo do tipo zip, denominado tc.zip, todos os arquivos do co´digo e o
arquivo (em pdf) dorelato´rio.
– Envie em anexo o arquivo tc.zip para algoritmos.numericos.ufes@gmail.com. O assunto da
mensagem deve ser:
an20112:ee:tc:nome1:nome2
Substitua nome1 pelo nome completo do primeiro componente do grupo, e nome2 pelo nome
completo do segundo componente do grupo. Os nomes dos componentes do grupo devem
estar separados por espac¸os em branco. Por exemplo:
an20112:ee:tc:Claudine Badue:Sergio Paulo Tavares Goncalves
• A fo´rmula para desconto por atraso na entrega do trabalho e´:
2d−1
0, 32
%
onde d e´ o atraso em dias u´teis. Note que apo´s 5 dias u´teis, o trabalho na˜o podera´ ser mais
entregue.
• Se voceˆ enviar o seu trabalho mu´ltiplas vezes, apenas a u´ltima versa˜o enviada sera´ considerada,
inclusive para efeito de desconto por atraso.
Refereˆncias
F. F. Campos, filho. Algoritmos Nume´ricos. LTC, Segunda Edic¸a˜o, 2007.
Lu´cia Catabriga. Armazenamento de Matrizes Esparsas, 2011.
http://www.inf.ufes.br/∼claudine/courses/an11 2/transparencias/aula armazenamento.pdf.
Paulo Ce´sar Barbosa Fernandes. Armazenamento de Matrizes Esparsas, 2011.
http://www.inf.ufes.br/∼claudine/courses/an11 2/transparencias/MatrizesEsparsas.ppt.
5