A hierarchical butterfly LU preconditioner for two-dimensional electromagnetic scattering problems involving open surfaces

DOI10.1016/J.JCP.2019.109014zbMATH Open1453.65455OpenAlexW2913494672WikidataQ127099390 ScholiaQ127099390MaRDI QIDQ2222698FDOQ2222698

Authors Yang Liu, Haizhao Yang 

Publication date 27 January 2021

Published in Journal of Computational Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.11371

zbMATH Keywords

scatteringLU factorizationpreconditioned iterative solverelectric-field integral equation (EFIE)interpolative decomposition butterfly factorization

Mathematics Subject Classification ID

Preconditioners for iterative methods (65F08) Diffraction, scattering (78A45) Numerical methods for integral equations (65R20) Applications to the sciences (65Z05)

Abstract: This paper introduces a hierarchical interpolative decomposition butterfly-LU factorization (H-IDBF-LU) preconditioner for solving two-dimensional electric-field integral equations (EFIEs) in electromagnetic scattering problems of perfect electrically conducting objects with open surfaces. H-IDBF-LU leverages the interpolative decomposition butterfly factorization (IDBF) to compress dense blocks of the discretized EFIE operator to expedite its application; this compressed operator also serves as an approximate LU factorization of the EFIE operator leading to an efficient preconditioner in iterative solvers. Both the memory requirement and computational cost of the H-IDBF-LU solver scale as $O(Nlo{g}^{2}N)$ in one iteration; the total number of iterations required for a reasonably good accuracy scales as $O(1)$ to $O(lo{g}^{2}N)$ in all of our numerical tests. The efficacy and accuracy of the proposed preconditioned iterative solver are demonstrated via its application to a broad range of scatterers involving up to $100$ million unknowns.

Recommendations

• Incomplete LU Preconditioning with the Multilevel Fast Multipole Algorithm for Electromagnetic Scattering
• A hierarchical preconditioner for the electric field integral equation on unstructured meshes based on primal and dual Haar bases
• Incomplete LU preconditioning for large scale dense complex linear systems from electromagnetic wave scattering problems
• Physics-based preconditioner for iterative algorithms in multi-scatterer and multi-boundary method of moments formulations
• A matrix-free two-grid preconditioner for solving boundary integral equations in electromagnetism

Cites Work

• scientific article; zbMATH DE number 819734 (Why is no real title available?)
• A Preconditioner for the Electric Field Integral Equation Based on Calderon Formulas
• A fast direct solver for scattering problems involving elongated structures
• A fast directional algorithm for high frequency acoustic scattering in two dimensions
• A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix
• A recursive skeletonization factorization based on strong admissibility
• A wideband fast multipole method for the Helmholtz equation in three dimensions
• An ${\cal H}^{2}$-Matrix-Based Integral-Equation Solver of Reduced Complexity and Controlled Accuracy for Solving Electrodynamic Problems
• An \(O(N)\) direct solver for integral equations on the plane
• An algorithm for the rapid evaluation of special function transforms
• An algorithm for the rapid numerical evaluation of Bessel functions of real orders and arguments
• An introduction to hierarchical matrices
• Analytic preconditioners for the electric field integral equation
• Butterfly factorization
• Construction and arithmetics of \(\mathcal H\)-matrices
• Diagonal forms of translation operators for the Helmholtz equation in three dimensions
• Direct Solve of Electrically Large Integral Equations for Problem Sizes to 1 M Unknowns
• Directional preconditioner for 2D high frequency obstacle scattering
• Divergence (Runge phenomenon) for least-squares polynomial approximation on an equispaced grid and mock-Chebyshev subset interpolation
• Efficient computation of oscillatory integrals via adaptive multiscale local Fourier bases
• Fast Direct Solver for Essentially Convex Scatterers Using Multilevel Non-Uniform Grids
• Fast Directional Multilevel Algorithms for Oscillatory Kernels
• Fast construction of hierarchical matrix representation from matrix-vector multiplication
• Fast direct solvers for integral equations in complex three-dimensional domains
• Fast directional computation of high frequency boundary integrals via local FFTs
• Fast directional multilevel summation for oscillatory kernels based on Chebyshev interpolation
• Fast numerical computations of oscillatory integrals related to acoustic scattering. I
• Fast solution of electromagnetic integral equations using adaptive wavelet packet transform
• Hierarchical LU decomposition-based preconditioners for BEM
• Multidimensional butterfly factorization
• Multipole Translation Theory for the Three-Dimensional Laplace and Helmholtz Equations
• Multiscale Compressed Block Decomposition for Fast Direct Solution of Method of Moments Linear System
• Numerical Differentiation by High Order Interpolation
• On the existence of nonoscillatory phase functions for second order ordinary differential equations in the high-frequency regime
• Rapid solution of integral equations of scattering theory in two dimensions
• Sparse Approximation for Solving Integral Equations with Oscillatory Kernels
• Sweeping preconditioner for the Helmholtz equation: hierarchical matrix representation
• The Fast Multipole Method I: Error Analysis and Asymptotic Complexity
• Wave atoms and sparsity of oscillatory patterns

Cited In (4)

• Butterfly factorization via randomized matrix-vector multiplications
• Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
• A Fast Butterfly-Compressed Hadamard–Babich Integrator for High-Frequency Helmholtz Equations in Inhomogeneous Media with Arbitrary Sources
• Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations

Uses Software

• BesselEval

This page was built for publication: A hierarchical butterfly LU preconditioner for two-dimensional electromagnetic scattering problems involving open surfaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2222698)