Banca de DEFESA: CLAUDIO VINÍCIUS CARVALHO

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE: CLAUDIO VINÍCIUS CARVALHO
DATA: 19/03/2018
HORA: 09:30
LOCAL: Sala de Videoconferência - DCC
TÍTULO:

UMA REVISÃO DE HEURÍSTICAS PARA RENUMERAÇÃO DE VÉRTICES PARA REDUÇÃO DO CUSTO DE EXECUÇÃO DO MÉTODO GMRES PRÉ-CONDICIONADO

PALAVRAS-CHAVES:

Matrizes esparsas. Sistemas de equações lineares. GMRES. Redução de
largura de banda e de profile. Heurísticas e meta-heurísticas. Iterated Local Search.

PÁGINAS: 125
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
RESUMO:

Sistemas de equações lineares envolvendo matrizes esparsas de grande porte surgem da discretização
de equações diferenciais parciais, comuns em simulações computacionais de várias
áreas da ciência. Métodos iterativos, como o Generalized Minimal Residual (GMRES) précondicionado,
são os mais adequados para resolução desses sistemas. Quando se utiliza esses
métodos, pode-se obter redução de seu custo computacional ao se aplicar técnicas de redução
de largura de banda ou de profile nas matrizes envolvidas. Essas técnicas consistem em agrupar
os coeficientes não nulos da matriz o mais próximo possível da diagonal principal por meio de
permutações de suas linhas e colunas. Neste trabalho, avaliou-se o desempenho de métodos
heurísticos no estado da arte para redução de largura de banda ou de profile no contexto de
resolução de sistemas de equações lineares com o método GMRES pré-condicionado. Ainda,
uma heurística baseada na meta-heurística Iterated Local Search para os problemas de redução
de largura de banda e de profile de matrizes foi proposta. Nos testes realizados em 172
instâncias da base SuiteSparse Matrix Collection a heurística proposta apresentou bons resultados,
principalmente na redução de profile de matrizes assimétricas e de banda de matrizes
simétricas. Contudo, seu alto tempo de execução não a qualificou como heurística propícia para
reuzir o custo computacional do GMRES pré-condicionado. Doze métodos heurísticos foram
avaliados nos experimentos para redução do custo de execução do GMRES pré-condicionado.
Foram considerados seis pré-condicionadores, baseados em fatoração incompleta (ILUT, ILUC,
ILU(k), VBILUT e VBILUK) e em multigrid (ARMS) em 27 instâncias de grandes dimensões.
As simulações apontaram, em consonância com a literatura, que os melhores resultados na redução
do custo computacional de sistemas de equações lineares são obtidos por heurísticas com
baixo custo computacional, mesmo que não apresentem grandes reduções de largura de banda
ou profile. Ainda, constatou-se que, para certas instâncias, nenhuma heurística contribuiu para
a redução do custo de resolução dos sistemas com o GMRES pré-condicionado.

MEMBROS DA BANCA:
Externo ao Programa - 1255491 - ANTONIO MARIA PEREIRA DE RESENDE
Externo à Instituição - Diego Nunes Brandão - CEFET/RJ
Externo ao Programa - 1254668 - LUIZ HENRIQUE ANDRADE CORREIA
Externo à Instituição - Maurício Kischinhevsky - UFF
Presidente - 1720216 - SANDERSON LINCOHN GONZAGA DE OLIVEIRA