PILOT: a fast algorithm for enhanced 3D parasitic extraction efficiency

Integral equation methodologies applied to extract parasitics at the board, package, and on-chip levels involve solving a dense system of equations. In this paper, we present an improved oct-tree based multilevel QR compression technique for fast iterative solution. The regular tree and interaction structure of the fast multipole method, and the QR compression scheme applied to interaction sub-matrices as in IES/sup 3/ are combined to achieve superior time and memory efficiency. As is demonstrated by numerical simulation results presented herein, the new algorithm is found to be faster than both existing QR based methods and FastCap.