Randomized GPU Algorithms for the Construction of Hierarchical Matrices from Matrix-Vector Operations

DOI10.1137/18M1210101OpenAlexW2959257025WikidataQ127545005 ScholiaQ127545005MaRDI QIDQ5230631

Wajih Boukaram, David E. Keyes, George M. Turkiyyah

Publication date: 28 August 2019

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/18m1210101

zbMATH Keywords

randomized algorithmsmatrix compressionhierarchical matricesGPUnested basesmatrix-matrix multiplicationlow rank factorizationlow rank updatesbatched algorithms

Mathematics Subject Classification ID

Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) (68N19) Parallel algorithms in computer science (68W10) Approximation algorithms (68W25) Randomized algorithms (68W20) Numerical linear algebra (65Fxx)

Related Items (9)

H2Opus: a distributed-memory multi-GPU software package for non-local operators ⋮ A GPU-accelerated fast multipole method based on barycentric Lagrange interpolation and dual tree traversal ⋮ Hierarchical off-diagonal low-rank approximation of Hessians in inverse problems, with application to ice sheet model initialization ⋮ Scalable Physics-Based Maximum Likelihood Estimation Using Hierarchical Matrices ⋮ Learning elliptic partial differential equations with randomized linear algebra ⋮ Hierarchical Matrix Approximations of Hessians Arising in Inverse Problems Governed by PDEs ⋮ Hierarchical matrix approximations for space-fractional diffusion equations ⋮ Hierarchical algorithms on hierarchical architectures ⋮ Space-fractional diffusion with variable order and diffusivity: discretization and direct solution strategies

Uses Software

• hlib
• LBNL
• Torch
• cuRAND
• CholQR
• TensorFlow
• STRUMPACK

Cites Work

• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• Fast construction of hierarchical matrix representation from matrix-vector multiplication
• Efficient numerical methods for non-local operators. \(\mathcal H^2\)-matrix compression, algorithms and analysis.
• A direct solver for elliptic PDEs in three dimensions based on hierarchical merging of Poincaré-Steklov operators
• Towards dense linear algebra for hybrid GPU accelerated manycore systems
• Adaptive low-rank approximation of collocation matrices
• Construction and arithmetics of \(\mathcal H\)-matrices
• Efficient arithmetic operations for rank-structured matrices based on hierarchical low-rank updates
• An Efficient Multicore Implementation of a Novel HSS-Structured Multifrontal Solver Using Randomized Sampling
• A Randomized Blocked Algorithm for Efficiently Computing Rank-revealing Factorizations of Matrices
• Hierarchical Matrices: Algorithms and Analysis
• Accelerating GPU Kernels for Dense Linear Algebra
• A Fast Randomized Algorithm for Computing a Hierarchically Semiseparable Representation of a Matrix
• Software for estimating sparse Jacobian matrices
• Reorthogonalization and Stable Algorithms for Updating the Gram-Schmidt QR Factorization
• A Block Orthogonalization Procedure with Constant Synchronization Requirements
• Block Gram–Schmidt Orthogonalization
• Hierarchical Matrix Operations on GPUs
• Mixed-Precision Cholesky QR Factorization and Its Case Studies on Multicore CPU with Multiple GPUs
• A Distributed-Memory Package for Dense Hierarchically Semi-Separable Matrix Computations Using Randomization
• Randomized Sparse Direct Solvers
• What Color Is Your Jacobian? Graph Coloring for Computing Derivatives
• Compressing Rank-Structured Matrices via Randomized Sampling

This page was built for publication: Randomized GPU Algorithms for the Construction of Hierarchical Matrices from Matrix-Vector Operations