O impacto do reordenamento de matrizes esparsas nos métodos iterativos não estacionários precondicionados

Página do item simplificado
dc.contributor.advisor-co1Boeres, Maria Claudia Silva
dc.contributor.advisor1Catabriga, Lúcia
dc.contributor.authorGhidetti, Kamila Ribeiro
dc.contributor.referee1Rangel, Maria Cristina
dc.contributor.referee2Coutinho, Alvaro Luiz Gayoso de Azeredo
dc.date.accessioned2016-12-23T14:33:47Z
dc.date.available2012-02-13
dc.date.available2016-12-23T14:33:47Z
dc.date.issued2011-07-13
dc.description.abstractThis 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.eng
dc.description.resumoA análise da influência dos algoritmos de reordenamento de matrizes na resolução de sistemas lineares utilizando os m´mé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 m´mé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.
dc.description.sponsorshipCoordenação de Aperfeiçoamento de Pessoal de Nível Superior
dc.formatText
dc.identifier.citationGHIDETTI, 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.
dc.identifier.urihttp://repositorio.ufes.br/handle/10/6416
dc.languagepor
dc.publisherUniversidade Federal do Espírito Santo
dc.publisher.countryBR
dc.publisher.courseMestrado em Informática
dc.publisher.departmentCentro Tecnológico
dc.publisher.initialsUFES
dc.publisher.programPrograma de Pós-Graduação em Informática
dc.rightsopen access
dc.subjectMinimizing bandwidth and reduced envelopeeng
dc.subjectMatrices reorderingeng
dc.subjectAlgorithms on graphseng
dc.subjectCombinatorial optimizationeng
dc.subjectMinimização de largura de banda e Redução de envelopepor
dc.subjectOrdenação de matrizespor
dc.subjectAlgoritmos em grafospor
dc.subjectOtimização combinatóriapor
dc.subject.br-rjbnOtimização combinatória
dc.subject.br-rjbnMatrizes (Matemática)
dc.subject.br-rjbnMétodos iterativos (Matemática)
dc.subject.br-rjbnTeoria dos grafos
dc.subject.cnpqCiência da Computação
dc.subject.udc004
dc.titleO impacto do reordenamento de matrizes esparsas nos métodos iterativos não estacionários precondicionados
dc.typemasterThesis
frapo.hasFundingAgencyCoordenação de Aperfeiçoamento de Pessoal de Nível Superior
Arquivos
Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Kamila Ribeiro Ghidetti parte 1 p 1-60.pdf
Tamanho:
1.22 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Coleções
Mestrado em Informática