A direct solver with O(N) complexity for integral equations on one-dimensional domains
From MaRDI portal
Publication:693189
DOI10.1007/S11464-012-0188-3zbMATH Open1262.65198arXiv1105.5372OpenAlexW2010717035MaRDI QIDQ693189FDOQ693189
P. Young, P. G. Martinsson, A. Gillman
Publication date: 7 December 2012
Published in: Frontiers of Mathematics in China (Search for Journal in Brave)
Abstract: An algorithm for the direct inversion of the linear systems arising from Nystrom discretization of integral equations on one-dimensional domains is described. The method typically has O(N) complexity when applied to boundary integral equations (BIEs) in the plane with non-oscillatory kernels such as those associated with the Laplace and Stokes' equations. The scaling coefficient suppressed by the "big-O" notation depends logarithmically on the requested accuracy. The method can also be applied to BIEs with oscillatory kernels such as those associated with the Helmholtz and Maxwell equations; it is efficient at long and intermediate wave-lengths, but will eventually become prohibitively slow as the wave-length decreases. To achieve linear complexity, rank deficiencies in the off-diagonal blocks of the coefficient matrix are exploited. The technique is conceptually related to the H and H^2 matrix arithmetic of Hackbusch and co-workers, and is closely related to previous work on Hierarchically Semi-Separable matrices.
Full work available at URL: https://arxiv.org/abs/1105.5372
Recommendations
- An \(O(N)\) direct solver for integral equations on the plane
- Fast direct solvers for integral equations in complex three-dimensional domains
- A fast direct solver for boundary integral equations in two dimensions
- scientific article; zbMATH DE number 3266158
- Direct methods for solving one class of integral equations of first kind
- The direct method of soluting complete singular integral equations with solutions having singularities of order one
- A general [L, M] one-step integrator for initial value problems
- Efficient rational one-step numerical integrators for initial value problems in ordinary differential equations
- scientific article
- scientific article; zbMATH DE number 3896256
Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50) Numerical methods for integral equations (65R20) Linear integral equations (45A05) Fredholm integral equations (45B05)
Cites Work
- Title not available (Why is that?)
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- Fast algorithms for hierarchically semiseparable matrices
- A fast algorithm for particle simulations
- Prolate spheroidal wavefunctions, quadrature and interpolation
- Domain decomposition based \({\mathcal H}\)-LU preconditioning
- The Numerical Solution of Integral Equations of the Second Kind
- High-Order Corrected Trapezoidal Quadrature Rules for Singular Functions
- Corner singularities for elliptic problems: Integral equations, graded meshes, quadrature, and compressed inverse preconditioning
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- A divide-and-conquer algorithm for the eigendecomposition of symmetric block-diagonal plus semiseparable matrices
- A fast direct solver for boundary integral equations in two dimensions
- Algorithms to solve hierarchically semi-separable systems
- Fast direct solvers for integral equations in complex three-dimensional domains
- A Fast Algorithm for the Numerical Evaluation of Conformal Mappings
- A fast direct solver for elliptic problems on general meshes in 2D
- Title not available (Why is that?)
- On the numerical solution of two‐point boundary value problems II
- A high-order Nyström discretization scheme for boundary integral equations defined on rotationally symmetric surfaces
- On the Compression of Low Rank Matrices
- Efficient discretization of Laplace boundary integral equations on polygonal domains
- A Fast Randomized Algorithm for Computing a Hierarchically Semiseparable Representation of a Matrix
Cited In (70)
- A Recursive Skeletonization Factorization Based on Strong Admissibility
- A fast integral equation method for the two-dimensional Navier-Stokes equations
- A Hierarchical Preconditioner for Wave Problems in Quasilinear Complexity
- An \(O(N)\) algorithm for constructing the solution operator to 2D elliptic boundary value problems in the absence of body loads
- FMM-LU: A Fast Direct Solver for Multiscale Boundary Integral Equations in Three Dimensions
- Efficient preconditioning of \(h p\)-FEM matrix sequences with slowly-varying coefficients: an application to topology optimization
- Matrices with Hierarchical Low-Rank Structures
- Analytical Low-Rank Compression via Proxy Point Selection
- Improving Multifrontal Methods by Means of Block Low-Rank Representations
- Algorithm for flow of highly-concentrated emulsions through a narrow constriction
- Efficient sum-of-exponentials approximations for the heat kernel and their applications
- An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation
- A Technique for Updating Hierarchical Skeletonization-Based Factorizations of Integral Operators
- Fast Hierarchical Solvers For Sparse Matrices Using Extended Sparsification and Low-Rank Approximation
- Efficient preconditioning of \(hp\)-FEM matrices by hierarchical low-rank approximations
- Hierarchical interpolative factorization for elliptic operators: integral equations
- An FFT-accelerated direct solver for electromagnetic scattering from penetrable axisymmetric objects
- On the stability of some hierarchical rank structured matrix algorithms
- A hierarchical matrix approach for computing hydrodynamic interactions
- Robust integral formulations for electromagnetic scattering from three-dimensional cavities
- Error analysis of an accelerated interpolative decomposition for 3D Laplace problems
- Asymmetric transport computations in Dirac models of topological insulators
- A simplified technique for the efficient and highly accurate discretization of boundary integral equations in 2D on domains with corners
- A direct solver for variable coefficient elliptic PDEs discretized via a composite spectral collocation method
- A high-order accurate accelerated direct solver for acoustic scattering from surfaces
- A tensor-train accelerated solver for integral equations in complex geometries
- Overlapping Domain Decomposition Preconditioner for Integral Equations
- A fast multipole method for Fredholm integral equations of the second kind with general kernel \(K(x,y)=K(x-y)\)
- Algorithms for inversion of diagonal plus semiseparable operator matrices
- An accelerated, high-order accurate direct solver for the Lippmann-Schwinger equation for acoustic scattering in the plane
- Parallel Skeletonization for Integral Equations in Evolving Multiply-Connected Domains
- Fast Spatial Gaussian Process Maximum Likelihood Estimation via Skeletonization Factorizations
- An \(O(N)\) direct solver for integral equations on the plane
- A direct solver for elliptic PDEs in three dimensions based on hierarchical merging of Poincaré-Steklov operators
- An Efficient High Order Method for Dislocation Climb in Two Dimensions
- Hierarchical Interpolative Factorization for Elliptic Operators: Differential Equations
- A fast solver for elastic scattering from axisymmetric objects by boundary integral equations
- Smoothed corners and scattered waves
- A fast direct solver for quasi-periodic scattering problems
- A fast direct solver for scattering from periodic structures with multiple material interfaces in two dimensions
- High-order boundary integral equation solution of high frequency wave scattering from obstacles in an unbounded linearly stratified medium
- A fast direct solver for the integral equations of scattering theory on planar curves with corners
- A fast block low-rank dense solver with applications to finite-element matrices
- Multifrequency inverse obstacle scattering with unknown impedance boundary conditions using recursive linearization
- Space-fractional diffusion with variable order and diffusivity: discretization and direct solution strategies
- A fast direct solver for two dimensional quasi-periodic multilayered media scattering problems
- A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media
- Compressing Rank-Structured Matrices via Randomized Sampling
- A fast algorithm for simulating multiphase flows through periodic geometries of arbitrary shape
- On the Complexity of the Block Low-Rank Multifrontal Factorization
- A fast direct solver for boundary value problems on locally perturbed geometries
- Fast Sparse Selected Inversion
- A parallel shared-memory implementation of a high-order accurate solution technique for variable coefficient Helmholtz problems
- A fast direct solver for integral equations on locally refined boundary discretizations and its application to multiphase flow simulations
- An alternative extended linear system for boundary value problems on locally perturbed geometries
- Bridging the Gap Between Flat and Hierarchical Low-Rank Matrix Formats: The Multilevel Block Low-Rank Format
- An efficient and highly accurate solver for multi-body acoustic scattering problems involving rotationally symmetric scatterers
- Sparse hierarchical solvers with guaranteed convergence
- Randomized compression of rank-structured matrices accelerated with graph coloring
- A Power Schur Complement Low-Rank Correction Preconditioner for General Sparse Linear Systems
- On the robustness of inverse scattering for penetrable, homogeneous objects with complicated boundary
- Block Low-Rank Matrices with Shared Bases: Potential and Limitations of the BLR$^2$ Format
- A fast solver for the narrow capture and narrow escape problems in the sphere
- Intuitionistic fuzzy least square twin support vector machines for pattern classification
- SlabLU: a two-level sparse direct solver for elliptic PDEs
- HODLR2D: A New Class of Hierarchical Matrices
- A neural network warm-start approach for the inverse acoustic obstacle scattering problem
- Broadband recursive skeletonization
- Computing functions of symmetric hierarchically semiseparable matrices
- HODLR\(d\)D: a new black-box fast algorithm for \(N\)-body problems in \(d\)-dimensions with guaranteed error bounds. Applications to integral equations and support vector machines
Uses Software
This page was built for publication: A direct solver with \(O(N)\) complexity for integral equations on one-dimensional domains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q693189)
