A linear-complexity direct integral equation solver accelerated by a new rank-minimized H2-representation for large-scale 3-D interconnect extraction

We develop a new H²-matrix-based representation of the dense system matrix arising from an integral-equation based analysis of large-scale 3D interconnects. The new H²-representation possesses a minimized rank in both nested cluster bases and coupling matrices for a prescribed accuracy. It is applicable to both scalar and vector based integral equation formulations, and real- and complex-valued system matrices. In addition, the new H²-representation is constructed in linear time, and hence the computational overhead is small. Based on the proposed new H²-representation, we develop a linear-complexity direct integral equation solver for 3-D impedance extraction and capacitance extraction of on-chip and package interconnects. The proposed solver is shown to outperform the state-of-the-art linear-complexity direct solver in both memory and CPU consumption. A dense matrix resulting from the capacitance extraction of large-scale 3-D interconnects having 3.71 million unknowns and 576 conductors is inverted in fast CPU time (1.6 hours), modest memory consumption (4.4 GB), and with prescribed accuracy satisfied on a single core running at 3 GHz.