GPGPU-based Algebraic Multigrid Method

Kosuke Takahashi, Akihiro Fujii, and Teruo Tanaka


Parallel Programming, Parallel Data Structures, GPGPU


This study describes the implementation of the algebraic multigrid (AMG) method on graphics processing units (GPUs), which is one of the fastest linear solvers for problems with a large sparse matrix. A smoother is an important component of an AMG solver that mainly determines the solver’s robustness and performance. Although several types of smoothers implemented on CPUs have been studied, the best method to implement smoothers on GPUs, which require abundant fine-grain parallelism, in terms of performance still needs to be developed. Thus, this study evaluates the efficiency of four representative smoothers such as the Jacobi, the IDR Jacobi, the multicolor Gauss–Seidel method, and the modified multicolor Gauss–Seidel methods, in which unknowns are colored with a smaller number of colors by eliminating weak dependencies. In addition, this paper shows a well-suited implementation of the multicolor Gauss–Seidel method on GPU that requires padding and reordering of the matrices on the basis of color. In our numerical tests, the Jacobi smoother works well for isotropic Poisson problems. On the other hand, Gauss–Seidel smoothers work better for anisotropic problems. The resulting GPU-based AMG solver is up to four times faster than a parallel AMG solver on dual quad-core CPUs.

Important Links:

Go Back