An LU Decomposition Based Direct Integral Equation Solver of Linear Complexity and Higher-Order Accuracy for Large-Scale Interconnect Extraction

A fast LU factorization of linear complexity is developed to directly solve a dense system of linear equations for the capacitance extraction of any arbitrary shaped 3-D structure embedded in inhomogeneous materials. In addition, a higher-order scheme is developed to achieve any higher-order accuracy for the proposed fast solver without sacrificing its linear computational complexity. The proposed solver successfully factorizes dense matrices that involve more than one million unknowns in fast CPU run time and modest memory consumption. Comparisons with state-of-the-art integral-equation-based capacitance solvers have demonstrated its clear advantages. In addition to capacitance extraction, the proposed LU solver has been successfully applied to large-scale full-wave extraction.