ILUM: A multi-elimination ILU preconditioner for general sparse matrices

Research output: Contribution to journalArticlepeer-review

99 Scopus citations


Standard preconditioning techniques based on incomplete LU (ILU) factorizations offer a limited degree of parallelism, in general. A few of the alternatives advocated so far consist of either using some form of polynomial preconditioning or applying the usual ILU factorization to a matrix obtained from a multicolor ordering. In this paper we present an incomplete factorization technique based on independent set orderings and multicoloring. We note that in order to improve robustness, it is necessary to allow the preconditioner to have an arbitrarily high accuracy, as is done with ILUs based on threshold techniques. The ILUM factorization described in this paper is in this category. It can be viewed as a multifrontal version of a Gaussian elimination procedure with threshold dropping which has a high degree of potential parallelism. The emphasis is on methods that deal specifically with general unstructured sparse matrices such as those arising from finite element methods on unstructured meshes.

Original languageEnglish (US)
Pages (from-to)830-847
Number of pages18
JournalSIAM Journal on Scientific Computing
Issue number4
StatePublished - Jul 1996


  • Graph coloring
  • Incomplete LU factorizations
  • Independent set orderings
  • Multicoloring
  • Preconditioned Krylov subspace methods
  • Sparse linear systems
  • Threshold dropping strategies


Dive into the research topics of 'ILUM: A multi-elimination ILU preconditioner for general sparse matrices'. Together they form a unique fingerprint.

Cite this