Levelized incomplete LU factorization and its application to large-scale circuit simulation

In the simulation of large circuits, the CPU time for solving the resulting linear equations may exceed the time required for evaluating the circuit elements. The circuit size above which this occurs depends on the applied transistor model and is roughly 10⁴ devices for a vectorizing table model. To further speed up large-scale circuit simulation, one therefore has to focus on the solution algorithm. In this paper the excessive propagation of fill-in elements during sparse matrix factorization is identified as the major source of the superlinear increase of solution time. The idea of truncating the fill-in propagation in a variable manner forms the basis for the construction of a hierarchical solver with the same robustness as Newton´s method but much less effort for large circuits. The method was applied to MOS circuits with up to 63000 transistors and in all cases the predominance of the solution part was broken. The new algorithm can be used efficiently both on sequential and vector architectures