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.