A butterfly-based direct combined-field integral-equation (CFIE) solver for analyzing scattering from electrically large, perfect electrically conducting objects is presented. The proposed solver leverages the butterfly scheme to compress blocks of the hierarchical LU-factorized discretized CFIE operator and uses randomized butterfly reconstruction schemes to expedite the factorization. The memory requirement and computational cost of the direct butterfly-CFIE solver scale as O(N log ² N) and O(N ^1.5 log N), respectively. These scaling estimates permit significant memory and CPU savings when compared to those realized by low-rank decomposition-based solvers. The efficacy and accuracy of the proposed solver are demonstrated through its application to the analysis of scattering from canonical and realistic objects involving up to 14 million unknowns.

This paper presents an adaptive randomized algorithm for computing the butterfly factorization of an $m\times n$ matrix with $m\approx n$ provided that both the matrix and its transpose can be rapi...

This article presents a low-rank decomposition algorithm based on subsampling of matrix entries. The proposed algorithm first computes rank-revealing decompositions of submatrices with a blocked adaptive cross approximation (BACA) algorithm, and then applies a hierarchical merge operation via truncated singular value decompositions (H-BACA). The proposed algorithm significantly improves the convergence of the baseline ACA algorithm and achieves reduced computational complexity compared to the traditional decompositions such as rank-revealing QR. Numerical results demonstrate the efficiency, accuracy, and parallel scalability of the proposed algorithm.

A butterfly-accelerated volume integral equation (VIE) solver is proposed for fast and accurate electromagnetic (EM) analysis of scattering from heterogeneous objects. The proposed solver leverages the hierarchical off-diagonal butterfly (HOD-BF) scheme to construct the system matrix and obtain its approximate inverse, used as a preconditioner. Complexity analysis and numerical experiments validate the $O(N\log ^{2}N)$ construction cost of the HOD-BF-compressed system matrix and $O(N^{1.5}\log N)$ inversion cost for the preconditioner, where $N$ is the number of unknowns in the high-frequency EM scattering problem. For many practical scenarios, the proposed VIE solver requires less memory and computational time to construct the system matrix and obtain its approximate inverse compared to a $\mathcal {H}$ matrix-accelerated VIE solver. The accuracy and efficiency of the proposed solver have been demonstrated via its application to the EM analysis of large-scale canonical and real-world structures comprising of broad permittivity values and involving millions of unknowns.

We present a fast and approximate multifrontal solver for large-scale sparse linear systems arising from finite-difference, finite-volume, or finite-element discretization of high-frequency wave eq...