O impacto do reordenamento de matrizes esparsas nos métodos iterativos não estacionários precondicionados
AUTOR(ES)
Kamila Ribeiro Ghidetti
FONTE
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia
DATA DE PUBLICAÇÃO
13/07/2011
RESUMO
A análise da influência dos algoritmos de reordenamento de matrizes na resolução de sistemas lineares utilizando os mmétodos iterativos não estacionários GMRES e Gradiente Conjugado, ambos com e sem precondicionamento, é o objeto de estudo desse trabalho. Os algoritmos mais referenciados na literatura para reordenamento de matrizes são Reverse Cuthill-McKee (RCM), Gibbs-Poole-Stockmeyer (GPS), Nested Dissection (ND) e Espectral (ES). Neste trabalho esses algoritmos foram analisados e algumas modificações foram propostas. Todos os algoritmos e suas versões modificadas foram implementados e comparados quanto a qualidade de solução (minimização de largura de banda e minimização de envelope) e tempo de execução. Além disso, os sistemas lineares associados as matrizes esparsas são resolvidos via mmétodos iterativos tipo Krylov precondicionados. Os precondicionadores analisados nesse estudo são baseados na fatoração LU incompleta. Para os testes computacionais é considerado um conjunto de matrizes estruturalmente simétricas oriundas das mais diversas áreas do conhecimento. Nossos estudos concluem que o reordenamento das matrizes, na maioria dos casos, reduz o numero de iterações dos métodos iterativos, entretanto a redução do tempo de processamento é dependente da dimensão e do condicionamento da matriz
ASSUNTO(S)
minimização de largura de banda e redução de envelope ordenação de matrizes algoritmos em grafos otimização combinatória minimizing bandwidth and reduced envelope matrices reordering algorithms on graphs combinatorial optimization ciencia da computacao
ACESSO AO ARTIGO
Documentos Relacionados
- Paralelizando o MOPAC usando CUDA e bibliotecas de Matrizes Esparsas
- Metodos iterativos e multigrid adaptaveis em malhas não estruturadas
- EstimaÃÃo e testes de processos estacionÃrios e nÃo estacionÃrios sazonais com longa dependÃncia
- Análise comparativa entre os métodos decomposição em valores singulares e análise de componentes principais envolvendo matrizes esparsas de grande porte
- Análise da influência de algoritmos de reordenação de matrizes esparsas no desempenho do método CCCG(n)