Bucket Sorted Independent Set Coarse Grid Selection

David Alber

Siebel Center for Computer Science
University of Illinois at Urbana-Champaign
201 North Goodwin Avenue
Urbana, IL 61801


Abstract

The setup phase in algebraic multigrid is responsible for building the hierarchy of coarse grids, linear operators, and transfer operators needed by the solve phase. Several coarse grid selection algorithms have been developed, and of those, independent set-based methods are the most numerous. Each of these algorithms searches the vertex weights in a graph to select new C-points and often also traverses the graph to identify vertices whose weights are to be updated. In this talk, a new algorithm for conducting the search for coarse grid points is introduced. Using a bucket data structure to organize the vertices, the algorithm does not traverse the graph to identify new C-points. Experimental results are presented to demonstrate the performance of the new approach.