A parallel multistage ILU factorization based on a hierarchical graph decomposition

Pascal Hénon, Yousef Saad

Research output: Contribution to journalArticlepeer-review

38 Scopus citations


PHIDAL (parallel hierarchical interface decomposition algorithm) is a parallel incomplete factorization method which exploits a hierarchical interface decomposition of the adjacency graph of the coefficient matrix. The idea of the decomposition is similar to that of the well-known wirebasket techniques used in domain decomposition. However, the method is devised for general, irregularly structured, sparse linear systems. This paper describes a few algorithms for obtaining good quality hierarchical graph decompositions and discusses the parallel implementation of the factorization procedure. Numerical experiments are reported to illustrate the scalability of the algorithm and its effectiveness as a general purpose parallel linear system solver.

Original languageEnglish (US)
Pages (from-to)2266-2293
Number of pages28
JournalSIAM Journal on Scientific Computing
Issue number6
StatePublished - 2006


  • ILU
  • ILU with threshold
  • Interface decomposition
  • Iterative methods
  • Parallel incomplete LU factorization
  • Preconditioning
  • Sparse Gaussian elimination
  • Sparse linear systems
  • Wirebasket decomposition


Dive into the research topics of 'A parallel multistage ILU factorization based on a hierarchical graph decomposition'. Together they form a unique fingerprint.

Cite this