A greedy strategy for coarse-grid selection

S. Maclachlan, Yousef Saad

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


Efficient solution of the very large linear systems that arise in numerical modeling of real-world applications is often only possible through the use of multilevel techniques. While highly optimized algorithms may be developed using knowledge about the origins of the matrix problem to be considered, much recent interest has been in the development of purely algebraic approaches that may be applied in many situations, without problem-specific tuning. Here, we consider an algebraic approach to finding the fine/coarse partitions needed in multilevel approaches. The algorithm is motivated by recent theoretical analysis of the performance of two common multilevel algorithms, multilevel block factorization and algebraic multigrid. While no guarantee on the rate of coarsening is given, the splitting is shown to always yield an effective preconditioner in the two-level sense. Numerical performance of two-level and multilevel variants of this approach is demonstrated in combination with both algebraic multigrid and multilevel block factorizations, and the advantages of each of these two algorithmic settings are explored.

Original languageEnglish (US)
Pages (from-to)1825-1853
Number of pages29
JournalSIAM Journal on Scientific Computing
Issue number5
StatePublished - 2007


  • Algebraic multigrid (AMG)
  • Algebraic preconditioners
  • Iterative methods


Dive into the research topics of 'A greedy strategy for coarse-grid selection'. Together they form a unique fingerprint.

Cite this