
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 Lincohn Gonzaga de | - |
| Autor(es): dc.contributor | Francisco, Alexandre Santos | - |
| Autor(es): dc.contributor | Moreira, Mayron César de Oliveira | - |
| Autor(es): dc.creator | Chagas, Guilherme Oliveira | - |
| Data de aceite: dc.date.accessioned | 2026-02-09T12:22:24Z | - |
| Data de disponibilização: dc.date.available | 2026-02-09T12:22:24Z | - |
| Data de envio: dc.date.issued | 2015-08-27 | - |
| Data de envio: dc.date.issued | 2015-08-27 | - |
| Data de envio: dc.date.issued | 2015-08-27 | - |
| Data de envio: dc.date.issued | 2015-07-17 | - |
| Fonte completa do material: dc.identifier | https://repositorio.ufla.br/handle/1/10289 | - |
| Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/1159972 | - |
| Descrição: dc.description | Computational cost of a linear system solver can be reduced by matrix bandwidth reduction. Bandwidth reduction consists of carrying out permutations of lines and columns so that they allow coefficients to remain near the main diagonal. By a systematic review, eight heuristics were identified with the best benefits, i.e., bandwidth reduction per computational cost, and then were implemented. In addition, the GPS heuristic, one of the most known heuristic in this problem, was implemented. Furthermore, two new heuristics are proposed in this work. Computational simulations were performed with these 11 heuristics in 113 instances of the Harwell-Boeing Sparse Matrix Collection and with three sets of instances with linear systems obtained from discretizations of the heat conduction and the Laplace equations by finite volumes. These linear systems were solved using the preconditioned Conjugate Gradient Method. According to the results presented here, the best heuristic in the simulations performed with the Harwell-Boeing Sparse Matrix Collection was the Variable neighborhood search for bandwidth reduction. However, this heuristic is not indicated to reduce the computational cost of preconditioned Conjugate Gradient Method in large-scale sparse linear systems. In particular, the better results in reducing the computational cost of solving linear systems were obtained by low-cost heuristics. Then, low-cost heuristics can be considered the best option to reduce the computational cost of the preconditioned Conjugate Gradient Method. | - |
| Descrição: dc.description | Fundação de Amparo à Pesquisa do Estado de Minas Gerais (FAPEMIG) | - |
| Descrição: dc.description | Pode-se obter redução no custo computacional na resolução de sistemas de equações lineares com a redução da largura de banda das matrizes de coeficientes. O problema da redução de largura de banda de matrizes consiste em realizar permutações de linhas e colunas de uma matriz, deixando-a com uma estrutura compacta e com coeficientes não nulos próximos à diagonal principal. Identificou-se, na literatura, oito heurísticas que apresentaram os melhores benefícios (i.e. redução de largura de banda) por custos computacionais e essas heurísticas foram implementadas. Também, foi implementada a heurística GPS, que é uma das heurísticas mais clássicas nesse problema. Ainda, duas novas heurísticas são propostas neste trabalho. Simulações computacionais foram realizadas com essas 11 heurísticas em 113 instâncias de matrizes da base Harwell-Boeing e em três conjuntos de instâncias de sistemas de equações lineares oriundos de discretizações da equação da condução do calor e da equação de Laplace pelo método dos volumes finitos. Ainda, esses sistemas de equações lineares foram resolvidos pelo método dos gradientes conjugados precondicionado. Com os testes nas instâncias da base Harwell-Boeing, identificou-se que a heurística VNS-Band é a melhor heurística para a redução de largura de banda. Porém, essa heurística não é a mais adequada para a redução do custo computacional do método dos gradientes conjugados precondicionado em instâncias muito grandes. Especificamente, melhores resultados na redução do custo computacional da resolução de sistemas de equações lineares foram obtidos por heurísticas que não reduzem muito a largura de banda, mas que têm baixo custo computacional. Então, pode-se considerar que essas heurísticas são mais indicadas para se reduzir o custo computacional do método dos gradientes conjugados precondicionado na resolução de sistemas de equações lineares. | - |
| Formato: dc.format | application/pdf | - |
| Idioma: dc.language | pt_BR | - |
| Publicador: dc.publisher | Programa de Pós-Graduação em 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 | Heuristics | - |
| Palavras-chave: dc.subject | Método dos gradientes conjugados precondicionado | - |
| Palavras-chave: dc.subject | Matrizes esparsas | - |
| Palavras-chave: dc.subject | Bandwidth reduction | - |
| Palavras-chave: dc.subject | Preconditioned conjugate gradient method | - |
| Palavras-chave: dc.subject | Sparce matrices | - |
| Palavras-chave: dc.subject | Ciência da Computação | - |
| Título: dc.title | Uma avaliação de heurísticas para redução de largura de banda de matrizes | - |
| Título: dc.title | An evaluation of heuristics for matrix bandwidth reduction | - |
| 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: