O impacto do reordenamento de matrizes esparsas nos métodos iterativos não estacionários precondicionados
Nenhuma Miniatura disponível
Data
2011-07-13
Autores
Ghidetti, Kamila Ribeiro
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal do Espírito Santo
Resumo
This work analyzes the influence of matrices reordering algorithms on solving linear systems using non-stationary iterative methods GMRES and Conjugate Gradient, both with and without preconditioning. The algorithms referenced most often in the literature for the reordering of matrices are Reverse Cuthill-McKee (RCM), Gibbs-Poole-Stockmeyer (GPS), Nested Dissection (ND) and Spectral (ES). We analyze these algorithms and propose some modifications comparing their solution qualities (minimizing bandwidth and minimizing envelope) and CPU times. Moreover, the linear systems associated with sparse matrices are solved via preconditioned Krylov-type iterative methods considering the incomplete LU factorization preconditioners. For the computational tests, we consider a set of structurally symmetric matrices that can come from various fields of knowledge. We conclude that the reordering of matrices, in most cases, reduces the number of iterations in the iterative methods, but the reducing of the CPU time depends on the size and conditioning of the matrix.
Descrição
Palavras-chave
Minimizing bandwidth and reduced envelope , Matrices reordering , Algorithms on graphs , Combinatorial optimization , Minimização de largura de banda e Redução de envelope , Ordenação de matrizes , Algoritmos em grafos , Otimização combinatória
Citação
GHIDETTI, Kamila Ribeiro. O impacto do reordenamento de matrizes esparsas nos métodos iterativos não estacionários precondicionados. 2011. 61 f. Dissertação (Mestrado em Informática) - Universidade Federal do Espírito Santo, Centro Tecnológico, Vitória, 2011.