Efficient Parallel ILU Factorization and Forward/Backward Substitution with Application to Large-Scale Nonlinear Circuit Simulation

Efficient techniques are proposed for parallel incomplete LU (ILU) factorization and forward/backward substitution, for the sparse matrices with the same sparsity pattern. These parallel algorithms are then used as a preconditioner for the generalized minimal residual (GMRES) algorithm to obtain an ILU-GMRES solver for large-scale circuit simulation. The novelty of the parallel ILU and substitution algorithms includes a subtree-based task scheduling scheme, a nested dissection-based approach for generating task queues, and the task packing and reverse-order execution techniques for forward/backward substitution. Experiments on 43 matrices dumped from circuit simulation show that the 8-thread parallel ILU with threshold (ILUT) factorization and forward/backward substitution with the proposed techniques achieve 4.2 \(×\) and 3.3 \(×\) parallel speedups on average, respectively. The proposed parallel ILUT-GMRES solver runs 5.3 \(×\) , on average, faster than PARDISO on these benchmarks. When integrated into Ngspice, it enables up to 2.3 \(×\) and 1.7 \(×\) faster execution of a step of Newton-Raphson iteration than the commercial parallel HSPICE, for the DC analysis and time integration stages, respectively.