Hierarchical matrix operations on GPUs. Matrix-vector multiplication and compression
From MaRDI portal
Abstract: Hierarchical matrices are space and time efficient representations of dense matrices that exploit the low rank structure of matrix blocks at different levels of granularity. The hierarchically low rank block partitioning produces representations that can be stored and operated on in near-linear complexity instead of the usual polynomial complexity of dense matrices. In this paper, we present high performance implementations of matrix vector multiplication and compression operations for the variant of hierarchical matrices on GPUs. This variant exploits, in addition to the hierarchical block partitioning, hierarchical bases for the block representations and results in a scheme that requires only storage and complexity for the mat-vec and compression kernels. These two operations are at the core of algebraic operations for hierarchical matrices, the mat-vec being a ubiquitous operation in numerical algorithms while compression/recompression represents a key building block for other algebraic operations, which require periodic recompression during execution. The difficulties in developing efficient GPU algorithms come primarily from the irregular tree data structures that underlie the hierarchical representations, and the key to performance is to recast the computations on flattened trees in ways that allow batched linear algebra operations to be performed. This requires marshaling the irregularly laid out data in a way that allows them to be used by the batched routines. Marshaling operations only involve pointer arithmetic with no data movement and as a result have minimal overhead. Our numerical results on covariance matrices from 2D and 3D problems from spatial statistics show the high efficiency our routines achieve---over 550GB/s for the bandwidth-limited mat-vec and over 850GFLOPS/s in sustained performance for the compression on the P100 Pascal GPU.
Recommendations
- Algorithmic patterns for \(\mathcal {H}\)-matrices on many-core processors
- \(\mathcal H^2\)-matrix arithmetics in linear complexity
- Construction of data-sparse \(\mathcal{H}^2\)-matrices by hierarchical compression
- Survey on the technique of hierarchical matrices
- H2Opus: a distributed-memory multi-GPU software package for non-local operators
Cited in
(14)- Exploiting low-rank covariance structures for computing high-dimensional normal and Student-\(t\) probabilities
- Space-fractional diffusion with variable order and diffusivity: discretization and direct solution strategies
- KSPHPDDM and PCHPDDM: extending PETSc with advanced Krylov methods and robust multilevel overlapping Schwarz preconditioners
- Hierarchical matrix approximations for space-fractional diffusion equations
- H2Opus: a distributed-memory multi-GPU software package for non-local operators
- A parallel low-rank solver for the six-dimensional Vlasov-Maxwell equations
- Hierarchical algorithms on hierarchical architectures
- Semiautomatic task graph construction for \(\mathcal{H}\)-matrix arithmetic
- Hierarchical Matrix Approximations of Hessians Arising in Inverse Problems Governed by PDEs
- Randomized GPU Algorithms for the Construction of Hierarchical Matrices from Matrix-Vector Operations
- Finite element discretizations for variable-order fractional diffusion problems
- A GPU-accelerated fast multipole method based on barycentric Lagrange interpolation and dual tree traversal
- \(\mathcal{H}^2\)-MG: a multigrid method for hierarchical rank structured matrices
- Quasi-optimal hierarchically semi-separable matrix approximation
This page was built for publication: Hierarchical matrix operations on GPUs. Matrix-vector multiplication and compression
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5237414)
