LEVELIZED INCOMPLETE LU FACTORIZATION AND ITS APPLICATION TO LARGE-SCALE CIRCUIT SIMULATION

In the simulation of targe circuits, the CPU time for solving the resu lting 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(4) devices for a vecto rizing table model [1]. To further speed up large-scale circuit simula tion, one therefore has to focus on the solution algorithm. In this pa per the excessive propagation of fill-in elements during sparse matrix factorization is identified as the major source of the superlinear in crease of solution time, The idea of truncating the fill-in propagatio n in a variable manner forms the basis for the construction of a hiera rchical solver with the same robustness as Newton's method but much le ss effort for large circuits, The method was applied to MOS circuits w ith up to 63 000 transistors and in all cases the predominance of the solution part was broken, The new algorithm can be used efficiently bo th on sequential and vector architectures.