Abstract
State-of-the-art integral equation based solvers rely on techniques that can perform a dense matrix-vector multiplication in linear complexity. We introduce H2 matrix as a mathematical framework to enable a highly efficient computation of dense matrices. Under this mathematical framework, as yet, no linear complexity has been established for matrix inversion. In this work, we developed a matrix inverse of linear complexity to directly solve the dense system of linear equations for the capacitance extraction involving arbitrary geometry and nonuniform materials. We theoretically proved the existence of the H2 matrix representation of the inverse of the dense system matrix, and revealed the relationship between the block cluster tree of the original matrix and that of its inverse. We analyzed the complexity and the accuracy of the proposed inverse, and proved its linear complexity as well as controlled accuracy. The proposed inverse-based direct solver has demonstrated clear advantages over state-of-the-art capacitance solvers such as FastCap and HiCap: with fast CPU time and modest memory consumption, and without sacrificing accuracy. It successfully inverts a dense matrix that involves more than one million unknowns associated with a large-scale, on-chip, 3-D interconnect embedded in inhomogeneous materials with fast CPU time and less than 5 GB memory.
Keywords
Integral-equation-based methods, H2 matrix, direct solver, matrix inversion, capacitance extraction
Date of this Version
2-15-2011