A Novel Approach to Find Pseudo–peripheral Vertices for Snay’s Heuristic

AUTOR(ES)

OLIVEIRA, S.L. GONZAGA DE, BERNARDES, J.A.B.

FONTE

TEMA (São Carlos)

DATA DE PUBLICAÇÃO

2018-01

RESUMO

RESUMO A solução de sistemas de equações lineares, representados por Ax = b, é fundamental em diversas aplicações científicas e em engenharia. Ao se reduzir o profile da matriz A, pode-se reduzir a ocupação de espac¸o e o tempo de processamento da resolução de tais sistemas de equações lineares. Neste trabalho, propomos um algoritmo generalizado para encontrar vértices pseudoperiféricos para o algoritmo heurístico de Snay. Baseados em experimentos realizados em 36 instâncias contidas nas bases de matrizes Harwell-Boeing e SuiteSparse, verificou-se que o n´umero de vértices pseudoperiféricos selecionados pelo algoritmo de Snay pode ser adequado para instâncias pequenas, mas é insuficiente para obter resultados razo´aveis em instâncias que não são pequenas. Neste artigo, recomendamos a seleção de até 26% (0,3%) de vértices pseudoperiféricos em relação ao tamanho da instância, quando o algoritmo heurístico de Snay é aplicado em instâncias menores que 3.000 (maiores que 20.000) vértices.

ASSUNTO(S)

redução de profile matrizes esparsas algoritmos de reordenação de vértices

Documentos Relacionados

• An Experimental Analysis of Three Pseudo-peripheral Vertex Finders in conjunction with the Reverse Cuthill-McKee Method for Bandwidth Reduction
• Heuristic approach to deriving models for gene finding.
• The Neuroid revisited: A heuristic approach to model neural spike trains
• Heuristic approach to the critical dynamics of the Ising model
• A more cultured approach to peripheral chemotransduction.