Rapid Rank Estimation and Low-Rank Approximation of Impedance Matrix Blocks Using Proxy Grids

摘要

A physics-based rank-revealing multilevel algorithm to more efficiently compute low-rank (LR) approximations of the method of moments matrix blocks Zos is presented. Using surface subsets of volumetric nonuniform spherical grids (proxy grids), an LR approximation Z^{os≈ AB†is obtained in two stages: 1) an upward pass and a downward pass on a multilevel tree, via truncated singular value decomposition-based analyses of interactions between source subclusters and their attendant proxy grids, rapidly estimates the rank and yields a domain of Zos, in the form of a matrix B with orthonormal columns and 2) a fast matrix-matrix multiplication step yields A. The algorithm reduces the O(N3) computational costs of revealing the rank to O(N2) or O(N3/2) operations and that of finding an LR approximation to O(N2) or O(N3/2log N) operations by adopting enclosing or belt-like proxy grids for electromagnetically large basis/testing function distributions that are either densely packed in a volume or quasi-planar, respectively.}