A Directionally Grouping Multilevel Green’s Function Interpolation Method With a Novel Low-Rank Compression Scheme

In this paper, we propose a novel low-rank compression scheme for implementing the Directionally Grouping Multilevel Green's Function Interpolation Method (DGMLGFIM), a fast electromagnetic scattering solver. In this scheme, a directional grouping is performed to construct the tree structure of the DGMLGFIM so that the rank of Green's function (GF) matrix of a direction <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</i> is constant. Subsequently, at each level of the tree, a low-cost procedure is devised to obtain a common unitary matrix Q, which is shared by groups in one directional interaction list. The common Q enables the constructions of interpolation coefficient matrix G and interpolation basis matrices W, C with their dimensions being compressed from the number of interpolation points (NIP) to the rank of GF matrix. Consequently, in the DGMLGFIM, the computational cost of the upper pass, translation and down pass operations is related to the constant rank instead of the NIP. As a result, the time and memory complexities of DGMLGFIM scale as <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N log N</i>) and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(N)</i>, respectively, in solving electrically large problems where <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i> is the number of unknowns. Numerical results of the scatterings from a sphere of diameter 128-wavelength and a squared patch array of size 50-wavelength by 50-wavelength are presented to demonstrate its efficiency and accuracy.