Linear time hierarchical capacitance extraction without multipole expansion

Hierarchical capacitance extraction algorithms have been shown an efficient and accurate capacitance extraction algorithm. An improved algorithm is also proposed to remove its runtime dependency on the number of conductors by a combination of hierarchical and multipole expansion algorithm. In this paper, we show that with the introduction of hierarchical merging operation and super-node representation, we can achieve linear runtime and accuracy without involving multipole expansion. Experimental results show over 10× runtime improvement and 20× memory saving over the multipole approaches with comparable accuracy and better numerical stability