Linear time hierarchical capacitance extraction without multipole expansion

Recently, 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 supernode representation, we can achieve linear runtime and accuracy without involving multipole expansion. Experimental results show over 10X runtime improvement and 20X memory saving over the multipole approaches with comparable accuracy and better numerical stability.