Linear-Complexity Direct and Iterative Integral Equation Solvers Accelerated by a New Rank-Minimized ${cal H}^{2}$ -Representation for Large-Scale 3-D Interconnect Extraction

We develop a new rank-minimized H²-matrix-based representation of the dense system matrix arising from an integral-equation (IE)-based analysis of large-scale 3-D interconnects. Different from the H²-representation generated by the existing interpolation-based method, the new H²-representation minimizes the rank in nested cluster bases and all off-diagonal blocks at all tree levels based on accuracy. The construction algorithm of the new H²-representation is applicable to both real- and complex-valued dense matrices generated from scalar and/or vector-based IE formulations. It has a linear complexity, and hence, the computational overhead is small. The proposed new H²-representation can be employed to accelerate both iterative and direct solutions of the IE-based dense systems of equations. To demonstrate its effectiveness, we develop a linear-complexity preconditioned iterative solver as well as a linear-complexity direct solver for the capacitance extraction of arbitrarily shaped 3-D interconnects in multiple dielectrics. The proposed linear-complexity solvers are shown to outperform state-of-the-art H²-based linear-complexity solvers in both CPU time and memory consumption. A dense matrix resulting from the capacitance extraction of a 3-D interconnect having 3.71 million unknowns and 576 conductors 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.