tc
5 pág.

tc


DisciplinaAlgoritmos Numéricos34 materiais780 seguidores
Pré-visualização2 páginas
Universidade Federal do Esp´\u131rito Santo
Departamento de Informa´tica
Algoritmos Nume´ricos 2011/2
Profa. Claudine Badue
Trabalho Computacional
Me´todos Iterativos para Resoluc¸a\u2dco de Sistemas Lineares
Utilizando Armazenamento Tradicional e Otimizado
Objetivo
Implementar e avaliar o desempenho de me´todos iterativos para resoluc¸a\u2dco de sistemas lineares esparsos
de grande porte utilizando armazenamento tradicional e otimizado.
Descric¸a\u2dco
Frequentemente, os processos de soluc¸a\u2dco de problemas das mais diversas a´reas do conhecimento recaem
na necessidade de resolver sistemas lineares. Na maioria das vezes, esses sistemas sa\u2dco esparsos e de
grande porte. O esquema de armazenamento otimizado e´ crucial na eficie\u2c6ncia do me´todo nume´rico
considerado, tanto em economia de memo´ria quanto em operac¸o\u2dces 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\u2dco de sistemas lineares esparsos
de grande porte, considerando:
\u2022 o esquema de armazenamento tradicional, ou denso, que armazena a matriz em uma estrutura
bidimensional;
\u2022 o esquema de armazenamento otimizado por linha, ou Compress Sparse Row (CSR), que ar-
mazena somente os coeficientes na\u2dco nulos de uma matriz esparsa em um vetor ordenado por
linha. Ale´m desse vetor, e´ necessa´rio armazenar informac¸o\u2dces adicionais sobre a localizac¸a\u2dco 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.
\u2022 Implemente, para cada esquema de armazenamento, uma func¸a\u2dco para calcular a soluc¸a\u2dco do
sistema pelo me´todo iterativo de Gauss-Seidel, tendo como para\u2c6metros de entrada:
\u2013 a matriz esparsa A,
\u2013 o vetor dos termos independentes b,
\u2013 a tolera\u2c6ncia Toler, e
\u2013 o nu´mero ma´ximo de iterac¸o\u2dces IterMax.
\u2022 Implemente, para cada esquema de armazenamento, uma func¸a\u2dco para calcular a soluc¸a\u2dco do
sistema pelo me´todo iterativo SOR, tendo como para\u2c6metros de entrada:
\u2013 a matriz esparsa A,
\u2013 o vetor dos termos independentes b,
\u2013 a tolera\u2c6ncia Toler,
\u2013 o nu´mero ma´ximo de iterac¸o\u2dces IterMax, e
1
\u2013 o para\u2c6metro Omega. Observe que se Omega = 1, tem-se o me´todo de Gauss-Seidel.
Utilize as equac¸o\u2dces de iterac¸o\u2dces dos me´todos de Gauss-Seidel e SOR, ao inve´s das matrizes de
iterac¸a\u2dco. A condic¸a\u2dco inicial pode ser dada por x0i = bi/aii, para i = 1, ..., n.
Validac¸a\u2dco
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\u2dco/Conjunto A´rea de Aplicac¸a\u2dco n nnz
BCSSTK03 Harwell-Boeing/BCSSTRUC1 Engenharia Estrutural 112 376
HOR131 Harwell-Boeing/NNCENG Conservac¸a\u2dco de Energia 434 4710
GR3030 Harwell-Boeing/LAPLACE Discretizac¸a\u2dco do Laplaciano 900 4322
ORSIRR1 Harwell-Boeing/OILGEN Simulac¸a\u2dco 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\u2dco e do
conjunto associados a` matriz; a terceira coluna, a a´rea de aplicac¸a\u2dco da matriz; a quarta coluna, a ordem
da matriz; e a quinta coluna, o nu´mero de coeficientes na\u2dco nulos da matriz. Todas as informac¸o\u2dces
sobre as matrizes podem ser obtidas navegando no reposito´rio Matrix Market atrave´s das colec¸o\u2dces e
conjuntos referenciados na Tabela 1.
As matrizes sa\u2dco 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\u2dco nulos da matriz (376); a terceira linha armazena
a linha (1), a coluna (1), e o valor (\u2248 2.9697 × 108) do primeiro coeficiente na\u2dco nulo da matriz; a
quarta linha armazena a linha (4), a coluna (1), e o valor (\u2248 4.5073× 109) do segundo coeficiente na\u2dco
nulo da matriz; e assim por diante. Observe que os coeficientes na\u2dco nulos esta\u2dco listados por coluna.
Entretanto, o esquema de armazenamento CSR armazena os coeficientes na\u2dco nulos por linha. Por
questa\u2dco 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\u2dco; seu valor exato e´ x = (1 1 1 ... 1)t;
b = Atx \u21d2 bi =
\u2211n
i=1 aji.
Dado o arquivo do tipo mtx como para\u2c6metro de entrada, as func¸o\u2dces densa.m e csr.m le\u2c6em 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\u2dces densa.m e csr.m esta\u2dco dispon´\u131veis
em http://www.inf.ufes.br/\u223cclaudine/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:
\u2022 Encontre, de forma emp´\u131rica, o para\u2c6metro Omega o´timo do me´todo SOR com Toler = 10\u22126;
\u2022 Fac¸a um estudo comparativo com relac¸a\u2dco ao nu´mero de iterac¸o\u2dces e tempo de execuc¸a\u2dco para os
me´todos iterativos de Gauss-Seidel e SOR (usando o para\u2c6metro Omega o´timo) com Toler =
10\u22126, e os esquemas de armazenamento denso e CSR.
Observac¸o\u2dces:
\u2022 Os experimentos nume´ricos descritos acima sa\u2dco obrigato´rios. E´ bom lembrar que outros experi-
mentos podem ser incorporados ao relato´rio com o objetivo de enriquecer seu trabalho.
\u2022 Se existirem experimentos na\u2dco convergentes, explique no relato´rio as poss´\u131veis causas e reporte
os resultados com IterMax = 100.
\u2022 O Octave tem uma forma simples de medir tempo de execuc¸a\u2dco usando os comandos tic e toc.
Relato´rio
O relato´rio devera´ conter as seguintes sesso\u2dces:
\u2022 Introduc¸a\u2dco: onde o grupo devera´ apresentar a estrutura do trabalho e os objetivos;
\u2022 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;
\u2022 Implementac¸a\u2dco: onde sera\u2dco apresentados a estrutura do co´digo e partes significativas do co´digo
comentado;
\u2022 Experimentos Nume´ricos: onde sera\u2dco apresentados os experimentos nume´ricos realizados pelo
grupo, tanto as entradas para os programas quanto os resultados obtidos em tabelas e/ou gra´ficos.
\u2022 Conclusa\u2dco: onde sera\u2dco discutidos os resultados obtidos.
Instruc¸o\u2dces para Entrega
\u2022 Este trabalho devera´ ser desenvolvido em grupos de duas (e somente duas) pessoas. Na\u2dco sera\u2dco
aceitos grupos de tre\u2c6s ou uma u´nica pessoa. Se houver um nu´mero \u131´mpar de alunos, sera´ aceito
um u´nico grupo com uma u´nica pessoa.
4
\u2022 O relato´rio devera´ ser entregue impresso em aula ate´ a data limite de entrega.
\u2022 O co´digo e o relato´rio (em pdf) devera\u2dco ser enviados por e-mail ate´ a`s 23:59 horas da data limite
de entrega, adotando-se os seguintes procedimentos:
\u2013 Agrupe, em um arquivo do tipo zip, denominado tc.zip, todos os arquivos do co´digo e o
arquivo (em pdf) do