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

Sanderson Gonzaga de Oliveira, Júnior Assis Barreto Bernardes

Resumo


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.


Palavras-chave


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

Texto completo:

PDF


DOI: https://doi.org/10.5540/03.2017.005.01.0465

Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 


Normas para publicação | Contato