An O(N) algorithm for constructing the solution operator to 2D elliptic boundary value problems in the absence of body loads

DOI10.1007/S10444-013-9326-ZzbMATH Open1295.65107arXiv1302.5995OpenAlexW2017150917MaRDI QIDQ404149FDOQ404149

P. G. Martinsson, A. Gillman

Publication date: 4 September 2014

Published in: Advances in Computational Mathematics (Search for Journal in Brave)

Abstract: The large sparse linear systems arising from the finite element or finite difference discretization of elliptic PDEs can be solved directly via, e.g., nested dissection or multifrontal methods. Such techniques reorder the nodes in the grid to reduce the asymptotic complexity of Gaussian elimination from $O(N^2)$ to $O(N^{1.5})$ for typical problems in two dimensions. It has recently been demonstrated that the complexity can be further reduced to O(N) by exploiting structure in the dense matrices that arise in such computations (using, e.g., $mathcalH$-matrix arithmetic). This paper demonstrates that such extit{accelerated} nested dissection techniques become particularly effective for boundary value problems without body loads when the solution is sought for several different sets of boundary data, and the solution is required only near the boundary (as happens, e.g., in the computational modeling of scattering problems, or in engineering design of linearly elastic solids.

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

Recommendations

• A fast direct solver for a class of elliptic partial differential equations
• A fast direct solver for boundary integral equations in two dimensions
• A fast nested dissection solver for Cartesian 3D elliptic problems using hierarchical matrices
• A direct solver with \(O(N)\) complexity for integral equations on one-dimensional domains
• An adaptive fast direct solver for boundary integral equations in two dimensions

zbMATH Keywords

fast algorithmdirect solversolution operatorDirichlet-to-Neumann operatormulti-frontal methodnested dissection method

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Numerical solution of discretized equations for boundary value problems involving PDEs (65N22)

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
• Nested Dissection of a Regular Finite Element Mesh
• Approximation of solution operators of elliptic partial differential equations by \({\mathcal H}\)- and \({\mathcal H}^2\)-matrices
• Domain decomposition based \({\mathcal H}\)-LU preconditioning
• Superfast Multifrontal Method for Large Structured Linear Systems of Equations
• A divide-and-conquer algorithm for the eigendecomposition of symmetric block-diagonal plus semiseparable matrices
• Algorithms to solve hierarchically semi-separable systems
• A fast direct solver for elliptic problems on general meshes in 2D
• A fast direct solver for a class of elliptic partial differential equations
• A direct solver with \(O(N)\) complexity for integral equations on one-dimensional domains
• Title not available (Why is that?)
• Efficient Structured Multifrontal Factorization for General Large Sparse Matrices

Cited In (18)

• Rapid zonal algorithm for polyelliptic PDEs in domains with high aspect ratio.
• H2Opus: a distributed-memory multi-GPU software package for non-local operators
• Fast algorithms for large dense matrices with applications to biofluids
• Efficient preconditioning of \(h p\)-FEM matrix sequences with slowly-varying coefficients: an application to topology optimization
• Partial evaluation of the discrete solution of elliptic boundary value problems
• Efficient mesh deformation based on radial basis function interpolation by means of the inverse fast multipole method
• Efficient preconditioning of \(hp\)-FEM matrices by hierarchical low-rank approximations
• Hierarchical interpolative factorization for elliptic operators: integral equations
• Linear-scaling selected inversion based on hierarchical interpolative factorization for self Green's function for modified Poisson-Boltzmann equation in two dimensions
• Asymmetric transport computations in Dirac models of topological insulators
• A Class of Iterative Solvers for the Helmholtz Equation: Factorizations, Sweeping Preconditioners, Source Transfer, Single Layer Potentials, Polarized Traces, and Optimized Schwarz Methods
• Bridging and Improving Theoretical and Computational Electrical Impedance Tomography via Data Completion
• A direct solver for elliptic PDEs in three dimensions based on hierarchical merging of Poincaré-Steklov operators
• Hierarchical Interpolative Factorization for Elliptic Operators: Differential Equations
• The ultraspherical spectral element method
• A fast block low-rank dense solver with applications to finite-element matrices
• The Inverse Fast Multipole Method: Using a Fast Approximate Direct Solver as a Preconditioner for Dense Linear Systems
• An efficient preconditioner for the fast simulation of a 2D Stokes flow in porous media

This page was built for publication: An \(O(N)\) algorithm for constructing the solution operator to 2D elliptic boundary value problems in the absence of body loads

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q404149)