A fast direct solver for boundary integral equations in two dimensions

DOI10.1016/j.jcp.2004.10.033zbMath1078.65112MaRDI QIDQ1780663

Per-Gunnar Martinsson, Vladimir Rokhlin

Publication date: 13 June 2005

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

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.513.7645

zbMATH Keywords

algorithm; computational complexity; numerical examples; two dimensions; boundary integral equations; Nyström discretization; inverse of a matrix; non-oscillatory kernels; classical potential theory equations; compressed factorization; direct matrix inversion

Mathematics Subject Classification ID

35J05: Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation

65Y20: Complexity and performance of numerical algorithms

65F05: Direct numerical methods for linear systems and matrix inversion

65N38: Boundary element methods for boundary value problems involving PDEs

31A10: Integral representations, integral operators, integral equations methods in two dimensions

Related Items

``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices, Fast Spatial Gaussian Process Maximum Likelihood Estimation via Skeletonization Factorizations, A Class of Iterative Solvers for the Helmholtz Equation: Factorizations, Sweeping Preconditioners, Source Transfer, Single Layer Potentials, Polarized Traces, and Optimized Schwarz Methods, Adaptive Quadrature by Expansion for Layer Potential Evaluation in Two Dimensions, A Power Schur Complement Low-Rank Correction Preconditioner for General Sparse Linear Systems, Parallel Skeletonization for Integral Equations in Evolving Multiply-Connected Domains, SuperDC: Superfast Divide-And-Conquer Eigenvalue Decomposition With Improved Stability for Rank-Structured Matrices, Overlapping Domain Decomposition Preconditioner for Integral Equations, A Fast Boundary Integral Method for High-Order Multiscale Mesh Generation, Jump Relations of Certain Hypersingular Stokes Kernels on Regular Surfaces, Analytical Low-Rank Compression via Proxy Point Selection, Fast Approximation of the Gauss--Newton Hessian Matrix for the Multilayer Perceptron, Fast Coulomb Matrix Construction via Compressing the Interactions Between Continuous Charge Distributions, Interpolative Decomposition via Proxy Points for Kernel Matrices, On the Numerical Solution of Elliptic Partial Differential Equations on Polygonal Domains, Directional Preconditioner for 2D High Frequency Obstacle Scattering, Boundary Integral Equations for Calculating Complex Eigenvalues of Transmission Problems, Fast Computation of High‐Frequency Dirichlet Eigenmodes via Spectral Flow of the Interior Neumann‐to‐Dirichlet Map, An Efficient High Order Method for Dislocation Climb in Two Dimensions, A fast direct solver for quasi-periodic scattering problems, A simplified technique for the efficient and highly accurate discretization of boundary integral equations in 2D on domains with corners, A fast nested dissection solver for Cartesian 3D elliptic problems using hierarchical matrices, A fast direct solver for scattering from periodic structures with multiple material interfaces in two dimensions, A wideband FMBEM for 2D acoustic design sensitivity analysis based on direct differentiation method, Low-rank approximation of integral operators by using the Green formula and quadrature, A direct solver for variable coefficient elliptic PDEs discretized via a composite spectral collocation method, A fast direct solver for elliptic problems on general meshes in 2D, A fast direct solver for the integral equations of scattering theory on planar curves with corners, A high-order Nyström discretization scheme for boundary integral equations defined on rotationally symmetric surfaces, High-order accurate methods for Nyström discretization of integral equations on smooth curves in the plane, Second kind integral equation formulation for the modified biharmonic equation and its applications, An efficient and highly accurate solver for multi-body acoustic scattering problems involving rotationally symmetric scatterers, Fast and accurate numerical methods for solving elliptic difference equations defined on lattices, A fast direct solver for a class of elliptic partial differential equations, Fast integral equation methods for the modified Helmholtz equation, An adaptive fast direct solver for boundary integral equations in two dimensions, A direct solver with \(O(N)\) complexity for integral equations on one-dimensional domains, Structured eigenvalue condition numbers for parameterized quasiseparable matrices, A fast integral equation method for the two-dimensional Navier-Stokes equations, A fast algorithm for the inversion of general Toeplitz matrices, A fast direct solver for scattering problems involving elongated structures, Stability and convergence of the method of fundamental solutions for Helmholtz problems on analytic domains, Corner singularities for elliptic problems: Integral equations, graded meshes, quadrature, and compressed inverse preconditioning, Dynamic simulation of locally inextensible vesicles suspended in an arbitrary two-dimensional domain, a boundary integral method, Faster convergence and higher accuracy for the Dirichlet-Neumann map, A high-order algorithm for multiple electromagnetic scattering in three dimensions, Integral equation methods for elliptic problems with boundary conditions of mixed type, Periodic band structure calculation by the Sakurai-Sugiura method with a fast direct solver for the boundary element method with the fast multipole representation, FEM/wideband FMBEM coupling for structural-acoustic design sensitivity analysis, A tensor-train accelerated solver for integral equations in complex geometries, Application of the inverse fast multipole method as a preconditioner in a 3D Helmholtz boundary element method, A new fast direct solver for the boundary element method, A fast direct solver for boundary value problems on locally perturbed geometries, Multifrequency inverse obstacle scattering with unknown impedance boundary conditions using recursive linearization, Fast model order reduction boundary element method for large-scale acoustic systems involving surface impedance, Spectrally accurate solutions to inhomogeneous elliptic PDE in smooth geometries using function intension, A fast direct solver for integral equations on locally refined boundary discretizations and its application to multiphase flow simulations, Approximate inversion of discrete Fourier integral operators, A hierarchical matrix approach for computing hydrodynamic interactions, A fast multipole method for Fredholm integral equations of the second kind with general kernel \(K(x,y)=K(x-y)\), An accelerated, high-order accurate direct solver for the Lippmann-Schwinger equation for acoustic scattering in the plane, Error analysis of an accelerated interpolative decomposition for 3D Laplace problems, A novel fast direct solver for 3D elastic inclusion problems with the isogeometric boundary element method, An FMM for waveguide problems of 2-D Helmholtz' equation and its application to eigenvalue problems, Simple non-extensive sparsification of the hierarchical matrices, Two-level preconditioning for \(h\)-version boundary element approximation of hypersingular operator with GenEO, Spectrally-accurate numerical method for acoustic scattering from doubly-periodic 3D multilayered media, Fast algorithms for large dense matrices with applications to biofluids, Efficient discretization of Laplace boundary integral equations on polygonal domains, \({\mathscr{H}} \)-matrix approximability of inverses of discretizations of the fractional Laplacian, Efficient mesh deformation based on radial basis function interpolation by means of the inverse fast multipole method, A level-set-based topology optimisation for acoustic-elastic coupled problems with a fast BEM-FEM solver, Fast high-order integral equation methods for solving boundary value problems of two dimensional heat equation in complex geometry, On the BEM for acoustic wave problems, A high-order accurate accelerated direct solver for acoustic scattering from surfaces, An accurate integral equation method for simulating multi-phase Stokes flow, A fast block low-rank dense solver with applications to finite-element matrices, Likelihood approximation with hierarchical matrices for large spatial datasets, An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation, Krylov deferred correction accelerated method of lines transpose for parabolic problems, Diffusion wavelets, Approximate inverse preconditioners for some large dense random electrostatic interaction matrices, An \(O(N)\) direct solver for integral equations on the plane, Fast evaluation of electro-static interactions in multi-phase dielectric media, A fast direct solver for non-intrusive reduced order modeling of vibroacoustic problems, Parallelization of the inverse fast multipole method with an application to boundary element method, An Algebraic Multilevel Preconditioner with Low-Rank Corrections for Sparse Symmetric Matrices, Fast, Adaptive, High-Order Accurate Discretization of the Lippmann--Schwinger Equation in Two Dimensions, Hierarchical Interpolative Factorization for Elliptic Operators: Integral Equations, Fast Alternating BiDirectional Preconditioner for the 2D High-Frequency Lippmann--Schwinger Equation, A fast algorithm for Brownian dynamics simulation with hydrodynamic interactions, On preconditioners for the Laplace double-layer in 2D, Matrices with Hierarchical Low-Rank Structures, Fast algorithms for hierarchically semiseparable matrices, Hierarchical Interpolative Factorization for Elliptic Operators: Differential Equations, Existence of $\mathcal {H}$-matrix approximants to the inverses of BEM matrices: The simple-layer operator, A Technique for Updating Hierarchical Skeletonization-Based Factorizations of Integral Operators, Fast Structured Direct Spectral Methods for Differential Equations with Variable Coefficients, I. The One-Dimensional Case, Fast Algorithms for Boundary Integral Equations, Fast direct solvers for integral equations in complex three-dimensional domains, A Recursive Skeletonization Factorization Based on Strong Admissibility, The Inverse Fast Multipole Method: Using a Fast Approximate Direct Solver as a Preconditioner for Dense Linear Systems, Compressing Rank-Structured Matrices via Randomized Sampling, Butterfly Factorization Via Randomized Matrix-Vector Multiplications, On the robustness of inverse scattering for penetrable, homogeneous objects with complicated boundary, Randomized numerical linear algebra: Foundations and algorithms, Singular matrices whose Moore-Penrose inverse is tridiagonal, Robust fast direct integral equation solver for three-dimensional doubly periodic scattering problems with a large number of layers, FMM-LU: A Fast Direct Solver for Multiscale Boundary Integral Equations in Three Dimensions, A novel high‐order collocation indirect boundary element method based on the Leis formulation for three‐dimensional high frequency exterior acoustic problems, A multigrid method for kernel functions acting on interacting structures with applications to biofluids, Second‐order accurate hierarchical approximate factorizations for solving sparse linear systems, Algebraic inverse fast multipole method: a fast direct solver that is better than HODLR based fast direct solver, Recent Advances in Acoustic Boundary Element Methods, A fast solver for the narrow capture and narrow escape problems in the sphere, A neural network warm-start approach for the inverse acoustic obstacle scattering problem, Random walks in frequency and the reconstruction of obstacles with cavities from multi-frequency data, Fast multipole methods for the evaluation of layer potentials with locally-corrected quadratures

Cites Work

• Unnamed Item
• LU factorization of non-standard forms and direct multiresolution solvers
• A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
• Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices
• High-Order Corrected Trapezoidal Quadrature Rules for Singular Functions
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• On the Compression of Low Rank Matrices
• A fast, direct algorithm for the Lippmann-Schwinger integral equation in two dimensions