Reducción del ancho de banda de matrices en el algoritmo go-away para mallas regulares

Abstract

En este artículo se considera el algoritmo Go-Away para resolver sistemas lineales de ecuaciones con grafo en forma de malla. Este algoritmo fue diseñado originalmente para resolver problemas de aplicaciones de elementos finitos y diferencias finitas. Aquí se compara el modo habitual de reordenar los nodos de los bloques con el orden obtenido al aplicar al algoritmo Go-Away el reordenamiento de Cuthill-McKee. La reducción en el efecto fill-in es notable si se compara con los algoritmos de Disección Anidada, Disección Unidireccional o Grado Mínimo.

In this paper we consider the Go-Away algorithm to solve linear systems of equations with graph in grid form. This method is appropriate primarily for matrix problems arising in finite differences and finite elements applications. Here we compare the usual way of reordering the nodes with the order obtained by applying to the Go-Away algorithm the Cuthill-McKee reordering. The reduction in the fill-in effect is remarkable if we compare with Nested Dissection, One-Way or Minimum Degree algorithms.