Buscar

 

RI UFLA (Universidade Federal de Lavras) >
DCC - Departamento de Ciência da Computação >
DCC - Programa de Pós-graduação >
DCC - Ciência da Computação - Mestrado (Dissertações) >

Por favor, utilize esse identificador para citar este item ou usar como link: http://repositorio.ufla.br/jspui/handle/1/10289

Título: Uma avaliação de heurísticas para redução de largura de banda de matrizes
Título Alternativo: An evaluation of heuristics for matrix bandwidth reduction
Autor(es): Chagas, Guilherme Oliveira
Orientador: Oliveira, Sanderson Lincohn Gonzaga de
Membro da banca: Francisco, Alexandre Santos
Membro da banca: Moreira, Mayron César de Oliveira
Assunto: Heuristics
Método dos gradientes conjugados precondicionado
Matrizes esparsas
Bandwidth reduction
Preconditioned conjugate gradient method
Sparce matrices
Data de Defesa: 17-Jul-2015
Data de publicação: 27-Ago-2015
Agência de Fomento: Fundação de Amparo à Pesquisa do Estado de Minas Gerais (FAPEMIG)
Referência: CHAGAS, G. O. Uma avaliação de heurísticas para redução de largura de banda de matrizes. 2015. 159 p. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Lavras, Lavras, 2015.
Resumo: 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.
Abstract: 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.
URI: http://repositorio.ufla.br/jspui/handle/1/10289
Idioma: por
Aparece nas coleções: DCC - Ciência da Computação - Mestrado (Dissertações)

Arquivos neste Item:

Arquivo Descrição TamanhoFormato
DISSERTACAO_Uma avaliação de heurísticas para redução de largura de banda de matrizes.pdf1,64 MBAdobe PDFVer/abrir

Itens protegidos por copyright, com todos os direitos reservados, Salvo indicação em contrário.


Mostrar estatísticas

 


DSpace Software Copyright © 2002-2007 MIT and Hewlett-Packard - Feedback