Parallel Threshold-based ILU Factorization

Factorization algorithms based on threshold incomplete LU factorization have been found to be quite effective in preconditioning iterative system solvers. However, because these factorizations allow the fill elements to be created dynamically, they have been considered to be unsuitable for distributed-memory parallel computers. We present a highly parallel formulation of the ILUT(m, t) threshold-based incomplete factorization algorithm. ILUT employs a dual dropping strategy that is able to control the computational requirements during the factorization as well as during the application of the preconditioner. Our parallel ILUT algorithm utilizes parallel multilevel k-way partitioning and parallel independent set computation algorithms to effectively parallelize both the factorization as well as the application of the preconditioner.