Um algoritmo pseudo-periférico genérico para a heurı́stica de Snay

Authors

  • Sanderson Gonzaga de Oliveira
  • Júnior Assis Barreto Bernardes

DOI:

https://doi.org/10.5540/03.2017.005.01.0465

Keywords:

Redução de profile, Vértices pseudo-periféricos, Renumeração, Reordenação, Matrizes esparsas.

Abstract

A resolução de sistemas de equações lineares na forma Ax = b é fundamental em muitas simulações numéricas na ciência e na engenharia. A redução do profile de A pode reduzir o custo de armazenamento e de resolução desses sistemas. Neste trabalho, propõe-se um algoritmo genérico para encontrar vértices pseudo-periféricos para a heurı́stica de Snay. Em testes em oito instâncias da base de matrizes esparsas Harwell-Boeing, verificou-se que o número de vértices pseudo-periféricos selecionados pela heurı́stica de Snay pode ser adequado para instâncias pequenas, mas é insuficiente para se obter bons resultados em instâncias que não são pequenas. Com os testes, mostra-se que é recomendável selecionar até 16% de vértices pseudo-periféricos em relação ao tamanho da instância.

Downloads

Download data is not yet available.

Published

2017-04-14

Issue

Section

Trabalhos Completos - Otimização