Simple non-extensive sparsification of the hierarchical matrices

DOI10.1007/S10444-020-09794-YzbMATH Open1442.65074arXiv1705.04601OpenAlexW3035285971MaRDI QIDQ2190667FDOQ2190667

Authors: Daria A. Sushnikova, Ivan Oseledets 

Publication date: 21 June 2020

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

Abstract: In this paper, we consider the matrices approximated in H2 format. The direct solution, as well as the preconditioning, of systems with such matrices is a challenging problem. We propose a non-extensive sparse factorization of the H2 matrix that allows to substitute the direct H2 solution with the solution of the system with an equivalent sparse matrix of the same size. The sparse factorization is constructed out of parameters of the H2 matrix. In the numerical experiments, we show the consistency of this approach in comparison to the other approximate block low-rank hierarchical solvers, such as HODLR, H2Lib and IFMM.

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

Recommendations

• Construction of data-sparse \(\mathcal{H}^2\)-matrices by hierarchical compression
• Introduction to hierarchical matrices with applications.
• Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices
• A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
• Hierarchical matrices. A means to efficiently solve elliptic boundary value problems

zbMATH Keywords

preconditioningsparse factorization

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50) Factorization of matrices (15A23)

Cites Work

• Efficient numerical methods for non-local operators. \(\mathcal H^2\)-matrix compression, algorithms and analysis.
• A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
• A sparse \({\mathcal H}\)-matrix arithmetic. II: Application to multi-dimensional problems
• An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation
• A fast algorithm for particle simulations
• Efficient arithmetic operations for rank-structured matrices based on hierarchical low-rank updates
• Title not available (Why is that?)
• Superfast Multifrontal Method for Large Structured Linear Systems of Equations
• Mosaic-skeleton approximations
• Hierarchical matrices based on a weak admissibility criterion
• A fast direct solver for boundary integral equations in two dimensions
• Algorithms to solve hierarchically semi-separable systems
• A Fast Solver for HSS Representations via Sparse Matrices
• Introduction to hierarchical matrices with applications.
• Hierarchical LU decomposition-based preconditioners for BEM
• Title not available (Why is that?)
• A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix
• The inverse fast multipole method: using a fast approximate direct dolver as a preconditioner for dense linear systems
• \(\mathcal{H}^2\)-matrix compression
• Multifrontal Hierarchically Solver for 3D Discretized Elliptic Equations
• Iterative representing set selection for nested cross approximation.
• A recursive skeletonization factorization based on strong admissibility
• ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices
• Preconditioners for hierarchical matrices based on their extended sparse form

Cited In (3)

• Second‐order accurate hierarchical approximate factorizations for solving sparse linear systems
• Preconditioners for hierarchical matrices based on their extended sparse form
• A hierarchical algorithm for making sparse matrices sparser

Uses Software

• hlib
• George
• H2Lib

This page was built for publication: Simple non-extensive sparsification of the hierarchical matrices

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