A fast direct solver for boundary integral equations in two dimensions

DOI10.1016/j.jcp.2004.10.033zbMath1078.65112OpenAlexW4294988936MaRDI 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

algorithmcomputational complexitynumerical examplestwo dimensionsboundary integral equationsNyström discretizationinverse of a matrixnon-oscillatory kernelsclassical potential theory equationscompressed factorizationdirect matrix inversion

Mathematics Subject Classification ID

Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation (35J05) Complexity and performance of numerical algorithms (65Y20) Direct numerical methods for linear systems and matrix inversion (65F05) Boundary element methods for boundary value problems involving PDEs (65N38) Integral representations, integral operators, integral equations methods in two dimensions (31A10)

Related Items

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, 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, SuperDC: Superfast Divide-And-Conquer Eigenvalue Decomposition With Improved Stability for Rank-Structured Matrices, Approximate inversion of discrete Fourier integral operators, A hierarchical matrix approach for computing hydrodynamic interactions, Overlapping Domain Decomposition Preconditioner for Integral Equations, Existence of $\mathcal {H}$-matrix approximants to the inverses of BEM matrices: The simple-layer operator, An accurate integral equation method for simulating multi-phase Stokes flow, A fast block low-rank dense solver with applications to finite-element matrices, A fast multipole method for Fredholm integral equations of the second kind with general kernel \(K(x,y)=K(x-y)\), 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, Hierarchical Interpolative Factorization for Elliptic Operators: Differential Equations, An accelerated, high-order accurate direct solver for the Lippmann-Schwinger equation for acoustic scattering in the plane, Periodic band structure calculation by the Sakurai-Sugiura method with a fast direct solver for the boundary element method with the fast multipole representation, 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, ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices, A fast direct solver for scattering problems involving elongated structures, A wideband FMBEM for 2D acoustic design sensitivity analysis based on direct differentiation method, FEM/wideband FMBEM coupling for structural-acoustic design sensitivity analysis, 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, Low-rank approximation of integral operators by using the Green formula and quadrature, Fast and accurate numerical methods for solving elliptic difference equations defined on lattices, On preconditioners for the Laplace double-layer in 2D, Boundary Integral Equations for Calculating Complex Eigenvalues of Transmission Problems, Likelihood approximation with hierarchical matrices for large spatial datasets, An FMM for waveguide problems of 2-D Helmholtz' equation and its application to eigenvalue problems, 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 fast direct solver for a class of elliptic partial differential equations, A direct solver for variable coefficient elliptic PDEs discretized via a composite spectral collocation method, Simple non-extensive sparsification of the hierarchical matrices, Fast integral equation methods for the modified Helmholtz equation, A new fast direct solver for the boundary element method, A Fast Boundary Integral Method for High-Order Multiscale Mesh Generation, 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, Fast Spatial Gaussian Process Maximum Likelihood Estimation via Skeletonization Factorizations, A fast direct solver for boundary value problems on locally perturbed geometries, A fast direct solver for non-intrusive reduced order modeling of vibroacoustic problems, Matrices with Hierarchical Low-Rank Structures, Parallelization of the inverse fast multipole method with an application to boundary element method, Two-level preconditioning for \(h\)-version boundary element approximation of hypersingular operator with GenEO, A high-order Nyström discretization scheme for boundary integral equations defined on rotationally symmetric surfaces, An adaptive fast direct solver for boundary integral equations in two dimensions, An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation, Jump Relations of Certain Hypersingular Stokes Kernels on Regular Surfaces, High-order accurate methods for Nyström discretization of integral equations on smooth curves in the plane, A Class of Iterative Solvers for the Helmholtz Equation: Factorizations, Sweeping Preconditioners, Source Transfer, Single Layer Potentials, Polarized Traces, and Optimized Schwarz Methods, Second kind integral equation formulation for the modified biharmonic equation and its applications, Spectrally-accurate numerical method for acoustic scattering from doubly-periodic 3D multilayered media, Fast algorithms for large dense matrices with applications to biofluids, Stability and convergence of the method of fundamental solutions for Helmholtz problems on analytic domains, Analytical Low-Rank Compression via Proxy Point Selection, Fast Approximation of the Gauss--Newton Hessian Matrix for the Multilayer Perceptron, Adaptive Quadrature by Expansion for Layer Potential Evaluation in Two Dimensions, Corner singularities for elliptic problems: Integral equations, graded meshes, quadrature, and compressed inverse preconditioning, Fast Computation of High‐Frequency Dirichlet Eigenmodes via Spectral Flow of the Interior Neumann‐to‐Dirichlet Map, Krylov deferred correction accelerated method of lines transpose for parabolic problems, An efficient and highly accurate solver for multi-body acoustic scattering problems involving rotationally symmetric scatterers, A direct solver with \(O(N)\) complexity for integral equations on one-dimensional domains, An Efficient High Order Method for Dislocation Climb in Two Dimensions, Efficient discretization of Laplace boundary integral equations on polygonal domains, Diffusion wavelets, Approximate inverse preconditioners for some large dense random electrostatic interaction matrices, Dynamic simulation of locally inextensible vesicles suspended in an arbitrary two-dimensional domain, a boundary integral method, An Algebraic Multilevel Preconditioner with Low-Rank Corrections for Sparse Symmetric Matrices, Structured eigenvalue condition numbers for parameterized quasiseparable matrices, Fast Algorithms for Boundary Integral Equations, An \(O(N)\) direct solver for integral equations on the plane, Fast Coulomb Matrix Construction via Compressing the Interactions Between Continuous Charge Distributions, Faster convergence and higher accuracy for the Dirichlet-Neumann map, Fast, Adaptive, High-Order Accurate Discretization of the Lippmann--Schwinger Equation in Two Dimensions, Hierarchical Interpolative Factorization for Elliptic Operators: Integral Equations, Interpolative Decomposition via Proxy Points for Kernel Matrices, A high-order algorithm for multiple electromagnetic scattering in three dimensions, \({\mathscr{H}} \)-matrix approximability of inverses of discretizations of the fractional Laplacian, Fast algorithms for hierarchically semiseparable matrices, 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 direct solvers for integral equations in complex three-dimensional domains, Fast high-order integral equation methods for solving boundary value problems of two dimensional heat equation in complex geometry, On the Numerical Solution of Elliptic Partial Differential Equations on Polygonal Domains, Fast Alternating BiDirectional Preconditioner for the 2D High-Frequency Lippmann--Schwinger Equation, Multifrequency inverse obstacle scattering with unknown impedance boundary conditions using recursive linearization, A Power Schur Complement Low-Rank Correction Preconditioner for General Sparse Linear Systems, Integral equation methods for elliptic problems with boundary conditions of mixed type, A fast algorithm for Brownian dynamics simulation with hydrodynamic interactions, A fast integral equation method for the two-dimensional Navier-Stokes equations, On the BEM for acoustic wave problems, 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, Parallel Skeletonization for Integral Equations in Evolving Multiply-Connected Domains, Fast evaluation of electro-static interactions in multi-phase dielectric media, A fast direct solver for integral equations on locally refined boundary discretizations and its application to multiphase flow simulations, Directional Preconditioner for 2D High Frequency Obstacle Scattering, A high-order accurate accelerated direct solver for acoustic scattering from surfaces, A fast algorithm for the inversion of general Toeplitz matrices

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