An Experimental Analysis of Three Pseudo-peripheral Vertex Finders in conjunction with the Reverse Cuthill-McKee Method for Bandwidth Reduction

AUTOR(ES)
FONTE

TEMA (São Carlos)

DATA DE PUBLICAÇÃO

13/12/2019

RESUMO

RESUMO. A necessidade de se determinar vértices pseudoperiféricos surge de diversas abordagens por teoria dos grafos de ordenação de linhas e colunas de sistemas de equações lineares compostos de matrizes esparsas. Neste trabalho, são mostrados resultados de dois algoritmos para encontrar vértices pseudoperiféricos: George-Liu e Kaveh-Bondarabady. Os resultados desses algoritmos são comparados com os resultados de uma variação do algoritmo de Kaveh-Bondarabady. Por meio de análise experimental, concluiu-se que o algoritmo de George-Liu retornou melhores resultados que os outros dois algoritmos, principalmente ao se considerar os tempos de execução dos algoritmos.Abstract. The need to determine pseudoperipheral vertices arises from several graph-theoretical approaches for ordering sparse matrix equations. The results of two algorithms for finding such vertices, namely, the George-Liu and Kaveh-Bondarabady algorithms, are evaluated in this work along with a variant of the Kaveh-Bondarabady algorithm. The results suggest that the well-know George-Liu algorithm dominates the other two pseudoperipheral vertex finders mainly when considering the computational times of the algorithms.

Documentos Relacionados