An O(N) multilevel solver for dense method of moment systems in electrostatic applications

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 a multilevel matrix compression algorithm that reduces both computational complexity and memory requirement to O(N) for N number of unknowns. The approach is based on the adaptive cross approximation method that exploits the rank deficiency of matrix blocks for physically separated groups of basis functions without explicitly dealing with the integral equation kernel. Hence the proposed method is practical for large-scale problems and can be implemented in a wide range of applications with a few or no modifications.