
Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
| Metadados | Descrição | Idioma |
|---|---|---|
| Autor(es): dc.contributor | Oliveira, Sanderson L. Gonzaga de | - |
| Autor(es): dc.contributor | Brandão, Diego Nunes | - |
| Autor(es): dc.contributor | Resende, Antônio Maria Pereira de | - |
| Autor(es): dc.creator | Carvalho, Cláudio Vinícius de | - |
| Data de aceite: dc.date.accessioned | 2026-02-09T11:14:47Z | - |
| Data de disponibilização: dc.date.available | 2026-02-09T11:14:47Z | - |
| Data de envio: dc.date.issued | 2018-05-16 | - |
| Data de envio: dc.date.issued | 2018-05-16 | - |
| Data de envio: dc.date.issued | 2018-04-16 | - |
| Data de envio: dc.date.issued | 2018-03-19 | - |
| Fonte completa do material: dc.identifier | https://repositorio.ufla.br/handle/1/29261 | - |
| Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/1136753 | - |
| Descrição: dc.description | Systems of linear equations that involve large sparse matrices arising from the discretization of partial differential equations are commonplace in computational simulations from many scientific fields. Iterative methods such as the preconditioned Generalized Minimal Residual method (GMRES) are the most suitable for solving such systems. When these methods are used, one can achieve computational cost reductions by applying bandwidth and profile reduction techniques on the related matrices. The purpose of these techniques is to group the coefficients of the matrix near to the main diagonal by applying a sequence of permutations of its rows and columns. In this work, the performance of heuristic methods for bandwidth and profile reductions was evaluated when used alongside the preconditioned GMRES method for solving linear systems. Furthermore, we propose a heuristic method for bandwidth and profile reductions based on the metaheuristic Iterated Local Search. In the tests carried in 172 instances from the SuiteSparse Matrix Collection, the proposed algorithm showed good results, especially in reducing the bandwidth of symmetric matrices and reducing the profile of unsymmetric matrices. However, due to its high execution times, it was not considered conducive to reduce the execution time of the preconditioned GMRES. Thirteen heuristic methods were evaluated in the experiments with the preconditioned GMRES. Six preconditioners based on incomplete factorization (ILUT, ILUC, ILU(k), VBILUT and VBILUK) and on multigrid methods (ARMS) were used, in 20 large instances. In line with previous works, heuristic methods with low computational cost obtained the best results in reducing the computational cost of solving linear systems in the simulations conducted, even though the bandwidth and profile reductions they provide are not the best overall. More, it was observed that for certain instances no heuristic was able to help in reducing the computational cost of solving linear systems with preconditioned GMRES. | - |
| Descrição: dc.description | Sistemas de equações lineares envolvendo matrizes esparsas de grande porte surgem, geralmente, 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 reduzir o custo computacional do GMRES pré-condicionado. Treze 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 20 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. | - |
| Formato: dc.format | application/pdf | - |
| Idioma: dc.language | pt_BR | - |
| Publicador: dc.publisher | Universidade Federal de Lavras | - |
| Publicador: dc.publisher | Ciência da Computação | - |
| Publicador: dc.publisher | UFLA | - |
| Publicador: dc.publisher | brasil | - |
| Publicador: dc.publisher | Departamento de Ciência da Computação | - |
| Direitos: dc.rights | acesso aberto | - |
| Palavras-chave: dc.subject | Generalized Minimal Residual (GMRES) | - |
| Palavras-chave: dc.subject | Pré-condicionadores | - |
| Palavras-chave: dc.subject | Renumerações de vértices | - |
| Palavras-chave: dc.subject | Heurísticas | - |
| Palavras-chave: dc.subject | Preconditioning | - |
| Palavras-chave: dc.subject | Vertices renumbering | - |
| Palavras-chave: dc.subject | Heuristics | - |
| Palavras-chave: dc.subject | Iterated Local Search | - |
| Palavras-chave: dc.subject | Computação - Matemática | - |
| Palavras-chave: dc.subject | Computer - Mathematics | - |
| Palavras-chave: dc.subject | Matemática da Computação | - |
| Título: dc.title | 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 | - |
| Tipo de arquivo: dc.type | dissertação | - |
| Aparece nas coleções: | Repositório Institucional da Universidade Federal de Lavras (RIUFLA) | |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: