PRECONDITIONED ITERATIVE METHODS FOR SPARSE LINEAR ALGEBRA PROBLEMS ARISING IN-CIRCUIT SIMULATION

The DC operating point of a circuit may be computed by tracking the zero curve of an associated artificial-parameter homotopy. It is possible to devise homotopy algorithms that are globally convergent with probability one for the DC operating point problem. These algorithms require computing the one-dimensional kernel of the Jacobian matrix of the homotopy mapping at each step along the zero curve, and hence, the solution of a linear system of equations at each step. These linear systems are typically large, highly sparse, nonsymmetric and indefinite. Several iterative methods which are applicable to nonsymmetric and indefinite problems are applied to a suite of test problems derived from simulations of actual bipolar circuits. Methods tested include Craig's method, GMRES(k), BiCGSTAB, QMR, KACZ (a row-projection method) and LSQR. The convergence rates of these methods may be improved by use of a suitable preconditioner. Several such techniques are considered, including incomplete LU factorization (ILU), sparse submatrix ILU, and ILU allowing restricted fill in bands or blocks. Timings and convergence statistics are given for each iterative method and preconditioner.