Nested Reduction Algorithms for Generating a Rank-Minimized ℋ2-Matrix From FMM for Electrically Large Analysis

In this work, we develop efficient algorithms to generate a rank-minimized
H
²
-matrix to represent electrically large surface integral operators for a prescribed accuracy. We first generate an
H
²
-matrix using the fast multipole method (FMM), and hence, the complexity for
H
²
-construction is as low as O(NlogN) for solving electrically large surface integral equations. We then develop fast algorithms to convert the FMM-based
H
²
-matrix whose rank is full asymptotically to a new
H
²
-representation, whose rank is minimized based on accuracy. The proposed algorithms cost O(k
³
) in time for each cluster in cluster basis generation and O(k
²
) in memory, where k is the minimal rank of the cluster basis required by accuracy. When the rank of the
H
²
-matrix is a constant, the complexity of the proposed algorithms is O(N) in both time and memory consumption. When the rank is a variable dependent on electrical size, the total complexity can be evaluated based on the rank's behavior. The resultant rank-minimized
H
²
-matrix has been employed to accelerate both iterative and direct solutions. Numerical experiments on large-scale surface integral equation-based scattering analysis have demonstrated its accuracy and efficiency.