Distributed-memory hierarchical interpolative factorization
From MaRDI portal
Publication:2408983
Abstract: The hierarchical interpolative factorization (HIF) offers an efficient way for solving or preconditioning elliptic partial differential equations. By exploiting locality and low-rank properties of the operators, the HIF achieves quasi-linear complexity for factorizing the discrete positive definite elliptic operator and linear complexity for solving the associated linear system. In this paper, the distributed-memory HIF (DHIF) is introduced as a parallel and distributed-memory implementation of the HIF. The DHIF organizes the processes in a hierarchical structure and keep the communication as local as possible. The computation complexity is and for constructing and applying the DHIF, respectively, where is the size of the problem and is the number of processes. The communication complexity is where is the latency and is the inverse bandwidth. Extensive numerical examples are performed on the NERSC Edison system with up to 8192 processes. The numerical results agree with the complexity analysis and demonstrate the efficiency and scalability of the DHIF.
Recommendations
- Robust memory-aware mappings for parallel multifrontal factorizations
- Data-Parallel Sparse Factorization
- scientific article; zbMATH DE number 434523
- scientific article; zbMATH DE number 741173
- Parallel Sparse Orthogonal Factorization on Distributed-Memory Multiprocessors
- Parallel nonnegative matrix factorization algorithm on the distributed memory platform
- A Fan-In Algorithm for Distributed Sparse Numerical Factorization
- scientific article; zbMATH DE number 3858845
Cites work
- H-LU factorization on many-core systems
- A direct solver for elliptic PDEs in three dimensions based on hierarchical merging of Poincaré-Steklov operators
- A direct solver with O(N) complexity for variable coefficient elliptic PDEs discretized via a high-order composite spectral collocation method
- A fast direct solver for a class of elliptic partial differential equations
- A fast direct solver for elliptic problems on general meshes in 2D
- A fast nested dissection solver for Cartesian 3D elliptic problems using hierarchical matrices
- A fully asynchronous multifrontal solver using distributed dynamic scheduling
- A Multigrid Tutorial, Second Edition
- A parallel geometric multifrontal solver using hierarchically semiseparable structure
- A parallel sweeping preconditioner for heterogeneous 3D Helmholtz equations
- A sparse \({\mathcal H}\)-matrix arithmetic. II: Application to multi-dimensional problems
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation
- Approximation of solution operators of elliptic partial differential equations by \({\mathcal H}\)- and \({\mathcal H}^2\)-matrices
- Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices
- Efficient inversion of the Galerkin matrix of general second-order elliptic operators with nonsmooth coefficients
- Efficient structured multifrontal factorization for general large sparse matrices
- Elemental, a new framework for distributed memory dense matrix computations
- Existence of H-matrix approximants to the inverse FE-matrix of elliptic operators with L^-coefficients
- Fast algorithms for hierarchically semiseparable matrices
- Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation
- Hierarchical interpolative factorization for elliptic operators: differential equations
- Hierarchical interpolative factorization for elliptic operators: integral equations
- scientific article; zbMATH DE number 1623019 (Why is no real title available?)
- scientific article; zbMATH DE number 1953444 (Why is no real title available?)
- Improving multifrontal methods by means of block low-rank representations
- Minimizing communication in numerical linear algebra
- Multifrontal parallel distributed symmetric and unsymmetric solvers
- Nested Dissection of a Regular Finite Element Mesh
- On the Compression of Low Rank Matrices
- On the numerical rank of the off-diagonal blocks of Schur complements of discretized elliptic PDEs
- Parallel \(\mathcal {H}\)-matrix arithmetic on distributed-memory systems
- Parallel iterative methods for sparse linear systems
- Parallel randomized and matrix-free direct solvers for large structured dense linear systems
- Randomized sparse direct solvers
- Some Fast Algorithms for Sequentially Semiseparable Representations
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- The Multifrontal Method for Sparse Matrix Solution: Theory and Practice
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
Cited in
(12)- Recursively preconditioned hierarchical interpolative factorization for elliptic partial differential equations
- Interconnected hierarchical structures for fast direct elliptic solution
- Approximate inversion of discrete Fourier integral operators
- Hierarchical interpolative factorization for elliptic operators: differential equations
- ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- Parallel Skeletonization for Integral Equations in Evolving Multiply-Connected Domains
- Sparse Hierarchical Preconditioners Using Piecewise Smooth Approximations of Eigenvectors
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- Second‐order accurate hierarchical approximate factorizations for solving sparse linear systems
- Distributed-memory \(\mathcal{H}\)-matrix algebra. I: Data distribution and matrix-vector multiplication
- Variational training of neural network approximations of solution maps for physical models
This page was built for publication: Distributed-memory hierarchical interpolative factorization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2408983)
