A direct solver with O(N) complexity for integral equations on one-dimensional domains
From MaRDI portal
(Redirected from Publication:693189)
A direct solver with \(O(N)\) complexity for integral equations on one-dimensional domains
A direct solver with \(O(N)\) complexity for integral equations on one-dimensional domains
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.
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; zbMATH DE number 3868569
- scientific article; zbMATH DE number 3896256
Cites work
- scientific article; zbMATH DE number 554500 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- A Fast Algorithm for the Numerical Evaluation of Conformal Mappings
- A divide-and-conquer algorithm for the eigendecomposition of symmetric block-diagonal plus semiseparable matrices
- A fast algorithm for particle simulations
- A fast direct solver for boundary integral equations in two dimensions
- A fast direct solver for elliptic problems on general meshes in 2D
- A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix
- A high-order Nyström discretization scheme for boundary integral equations defined on rotationally symmetric surfaces
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- Algorithms to solve hierarchically semi-separable systems
- Corner singularities for elliptic problems: Integral equations, graded meshes, quadrature, and compressed inverse preconditioning
- Domain decomposition based \({\mathcal H}\)-LU preconditioning
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Efficient discretization of Laplace boundary integral equations on polygonal domains
- Fast algorithms for hierarchically semiseparable matrices
- Fast direct solvers for integral equations in complex three-dimensional domains
- High-Order Corrected Trapezoidal Quadrature Rules for Singular Functions
- On the Compression of Low Rank Matrices
- On the numerical solution of two‐point boundary value problems II
- Prolate spheroidal wavefunctions, quadrature and interpolation
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- The Numerical Solution of Integral Equations of the Second Kind
Cited in
(70)- A fast integral equation method for the two-dimensional Navier-Stokes equations
- Fast spatial Gaussian process maximum likelihood estimation via skeletonization factorizations
- 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
- Sparse hierarchical solvers with guaranteed convergence
- An O(N) algorithm for constructing the solution operator to 2D elliptic boundary value problems in the absence of body loads
- A Hierarchical Preconditioner for Wave Problems in Quasilinear Complexity
- 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
- On the complexity of the block low-rank multifrontal factorization
- Algorithm for flow of highly-concentrated emulsions through a narrow constriction
- Randomized compression of rank-structured matrices accelerated with graph coloring
- 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 Power Schur Complement Low-Rank Correction Preconditioner for General Sparse Linear Systems
- A recursive skeletonization factorization based on strong admissibility
- Hierarchical interpolative factorization for elliptic operators: differential equations
- Efficient preconditioning of \(hp\)-FEM matrices by hierarchical low-rank approximations
- Hierarchical interpolative factorization for elliptic operators: integral equations
- On the robustness of inverse scattering for penetrable, homogeneous objects with complicated boundary
- An FFT-accelerated direct solver for electromagnetic scattering from penetrable axisymmetric objects
- On the stability of some hierarchical rank structured matrix algorithms
- Bridging the gap between flat and hierarchical low-rank matrix formats: the multilevel block low-rank format
- Robust integral formulations for electromagnetic scattering from three-dimensional cavities
- A hierarchical matrix approach for computing hydrodynamic interactions
- Error analysis of an accelerated interpolative decomposition for 3D Laplace problems
- Block Low-Rank Matrices with Shared Bases: Potential and Limitations of the BLR$^2$ Format
- A simplified technique for the efficient and highly accurate discretization of boundary integral equations in 2D on domains with corners
- Asymmetric transport computations in Dirac models of topological insulators
- A fast solver for the narrow capture and narrow escape problems in the sphere
- A direct solver for variable coefficient elliptic PDEs discretized via a composite spectral collocation method
- 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 high-order accurate accelerated direct solver for acoustic scattering from surfaces
- A tensor-train accelerated solver for integral equations in complex geometries
- 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
- A neural network warm-start approach for the inverse acoustic obstacle scattering problem
- 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
- Broadband recursive skeletonization
- An \(O(N)\) direct solver for integral equations on the plane
- Improving multifrontal methods by means of block low-rank representations
- A direct solver for elliptic PDEs in three dimensions based on hierarchical merging of Poincaré-Steklov operators
- Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation
- A fast solver for elastic scattering from axisymmetric objects by boundary integral equations
- Analytical low-rank compression via proxy point selection
- 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
- Fast sparse selected inversion
- 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
- Computing functions of symmetric hierarchically semiseparable matrices
- Compressing Rank-Structured Matrices via Randomized Sampling
- A fast algorithm for simulating multiphase flows through periodic geometries of arbitrary shape
- Overlapping domain decomposition preconditioner for integral equations
- A fast direct solver for boundary value problems on locally perturbed geometries
- An efficient high order method for dislocation climb in two dimensions
- A technique for updating hierarchical skeletonization-based factorizations of integral operators
- Matrices with hierarchical low-rank structures
- 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
- An efficient and highly accurate solver for multi-body acoustic scattering problems involving rotationally symmetric scatterers
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)
