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

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

Authors: Yang Liu, Haizhao Yang 

Publication date: 27 January 2021

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

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.

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

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

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)

Cites Work

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

Cited In (4)

• Sparse Approximate Multifrontal Factorization with Butterfly Compression for High-Frequency Wave Equations
• 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
• Butterfly Factorization Via Randomized Matrix-Vector Multiplications

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)