A fast band-matching technique for interconnect inductance modeling

Sparsification of the inverse of inductance matrix L has been widely used to facilitate the interconnect simulation. The band-matching method, proposed in [5] was proven to be stable and optimal. However, the technique in [5] exhibits a cubic computation complexity. In this paper, we reveal additional relationship between the entries in band-matching inductance matrices. We propose a fast technique that can calculate the entries in the band-matching approximation, in linear computational time. Experiments show accurate results for proposed method with orders of magnitude improvement in computational time.