Implementación Eficiente de un Solver Multigrid Algebraico 

Jorge A. Castellanos D. 1 , José L. Ramírez 1 , Germán A. Larrazábal S. 1
1Centro Multidisciplinario de Visualización y Cómputo Científico (CeMViCC), Facultad de Ciencias y Tecnología (FACYT), Universidad de Carabobo, Carabobo, Venezuela
Autor de Correspondencia: jcasteld@uc.edu.ve, jbarrios@uc.edu.ve, glarraza@uc.edu.ve

Ver Arhivo PDF

Resumen

En este trabajo se presenta una implementación eficiente del Método Multinivel Algebraico (AMG) para la resolución de grandes sistemas de ecuaciones lineales esparcidos. Los métodos multinivel (MG), en particular AMG, muestran una complejidad lineal con respecto al número de operaciones de punto flotante (FLOP) y el tamaño del problema. En la práctica, el problema consiste en determinar cuando es preferible emplear AMG en lugar de otro método. Por este motivo, este trabajo se enfoca en resolver este problema. Se empleó un conjunto de sistemas lineales provenientes de la discretización de un operador 3D escalar elíptico mediante diferencias finitas. Con el objetivo de evaluar la implementación presentada se generó un conjunto de 8 sistemas lineales. El orden máximode las matrices asociadas a los sistemas lineales generados, fue de 2.744.000. Los resultados experimentales muestran un buen comportamiento de la implementación, donde se obtuvo un comportamiento lineal del Método Multinivel Algebraico (AMG).


Palabras claves:

An Efficient Implementation Of An Algebraic Multigrid Solver

Jorge A. Castellanos D. 1 , José L. Ramírez 1 , Germán A. Larrazábal S. 1
1Centro Multidisciplinario de Visualización y Cómputo Científico (CeMViCC), Facultad de Ciencias y Tecnología (FACYT), Universidad de Carabobo, Carabobo, Venezuela
Autor de Correspondencia: jcasteld@uc.edu.ve, jbarrios@uc.edu.ve, glarraza@uc.edu.ve

Ver Arhivo PDF

Abstract

In this work, we present an efficient implementation of an algebraic multigrid method (AMG) to solve large sparse systems of linear equations. The multigrid methods (MG), in particular the AMG’s, exhibit a theoretical linear complexity with respect to the number of floating point operations (FLOP) and the problem size. In practice, the problem is to determine when it is preferable to use an AMG instead of some other solver. For this reason, in this work the main focus is to solve this problem. We use a set of linear systems arising from a 3D scalar elliptic operator discretized by finite difference method. In order to evaluate the implementation, a set of 8 linear systems is generated. The maximum order of the matrices associated to these linear systems is 2,744,000. The experimental results show the good performance of the AMG’s implementation. This performance is observed in the linear behavior of the AMG in our test problems.


Keywords: