Coarsening invariance and bucket-sorted independent sets for algebraic multigrid

David M. Alber, Luke N. Olson

Research output: Contribution to journalArticlepeer-review


Independent set-based coarse-grid selection algorithms for algebraic multigrid are defined by their policies for weight initialization, independent set selection, and weight update. In this paper, we develop theory demonstrating that algorithms employing the same policies produce identical coarse grids, regardless of the implementation. The coarse-grid invariance motivates a new coarse-grid selection algorithm, called Bucket-Sorted Independent Sets (BSIS), that is more efficient than an existing algorithm (CLJP-c) using the same policies. Experimental results highlighting the efficiency of two versions of the new algorithm are presented, followed by a discussion of BSIS in a parallel setting..

Original languageEnglish (US)
Pages (from-to)367-385
Number of pages19
JournalElectronic Transactions on Numerical Analysis
StatePublished - 2010


  • Algebraic multigrid
  • Coarse-grid selection
  • Parallel

ASJC Scopus subject areas

  • Analysis


Dive into the research topics of 'Coarsening invariance and bucket-sorted independent sets for algebraic multigrid'. Together they form a unique fingerprint.

Cite this