Greedy coarsening strategies for nonsymmetric problems

Scott Maclachlan, Yousef Saad

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


The solution of large-scale linear systems in computational science and engineering requires efficient solvers and preconditioners. Often, the most effective such techniques are those based on multilevel splittings of the problem. In this paper, we consider the problem of partitioning both symmetric and nonsymmetric matrices based solely on algebraic criteria. A new algorithm is proposed that combines attractive features of two previous techniques proposed by the authors. It offers rigorous guarantees of certain properties of the partitioning, yet is naturally compatible with the threshold based dropping known to be effective for incomplete factorizations. Numerical results show that the new partitioning scheme leads to improved results for a variety of problems. The effects of further matrix reordering within the fine-sca. le block are also considered.

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


  • Algebraic multigrid (AMG)
  • Matrix partitioning
  • Multilevel ILU
  • Nonsymmetric matrices
  • Preconditioning


Dive into the research topics of 'Greedy coarsening strategies for nonsymmetric problems'. Together they form a unique fingerprint.

Cite this