Direct Integral Equation Solvers (Inverse and LU) of Linear Complexity for Large-Scale Circuit Extraction

Prevailing fast integral equation (IE) solvers are iterative solvers relying on fast techniques that can perform a dense matrix-vector multiplication in O(N) or O(NlogN) complexity. The complexity of an iterative solver is at best O(N_{rhs}N_{it}N), where N_{it} is the number of iterations, and N_{rhs} the number of right hand sides. We have originated linear (optimal) complexity dense matrix inversion and LU factorization algorithms for general 3-D circuit extraction, including capacitance, resistance, inductance, and full-wave extraction of general 3-D structures involving inhomogeneous dielectrics and arbitrarily shaped lossy conductors. This work breaks the conventional computational barrier of IE-based methods.


In our direct surface IE solver for capacitance extraction, a dense matrix having 3.71 million unknowns is inverted in fast CPU time (1.6 h), modest memory consumption (4.4 GB), and with prescribed accuracy satisfied on a single core running at 3 GHz. In our O(N) direct surface IE solvers as well as O(N) direct volume IE solvers for full-wave extraction, we overcome the numerical challenge of solving a highly unstructured system matrix mixed with both square and rectangular dense and sparse matrices by developing a fast linear complexity direct solution. The inverse of a 2.68-million-unknown matrix arising from the full-wave extraction of a large-scale 3-D interconnect, which is a matrix solution for 2.68 million right hand sides, was obtained in less than 1.5 GB memory and 1.3 h on a single 3 GHz CPU core. Comparisons with both state-of the-art iterative and direct IE solvers for circuit extraction have demonstrated clear advantages of the O(N) direct IE solvers in both CPU time and memory consumption.

Selected Publications