An Efficient Multicore Implementation of a Novel HSS-Structured Multifrontal Solver Using Randomized Sampling

DOI10.1137/15M1010117zbMath1352.65092arXiv1502.07405OpenAlexW1559275088MaRDI QIDQ2830621

Artem Napov, François-Henry Rouet, Xiaoye Sherry Li, Samuel Williams, Pieter Ghysels

Publication date: 28 October 2016

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

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

zbMATH Keywords

computational complexity numerical experiments parallel algorithm multifrontal method sparse Gaussian elimination hierarchically semiseparable (HSS) matrices interpolative decompositions randomized sampling algorithm

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items

A Direct Elliptic Solver Based on Hierarchically Low-Rank Schur Complements, Hierarchical orthogonal factorization: sparse least squares problems, SemiAutomatic Task Graph Construction for $\mathcal{H}$-Matrix Arithmetic, Low-Rank Correction Methods for Algebraic Domain Decomposition Preconditioners, An Incomplete Cholesky Preconditioner Based on Orthogonal Approximations, On the Complexity of the Block Low-Rank Multifrontal Factorization, Algorithmic patterns for $\mathcal {H}$-matrices on many-core processors, Second‐order accurate hierarchical approximate factorizations for solving sparse linear systems, hm-toolbox: MATLAB Software for HODLR and HSS Matrices, Communication Avoiding Block Low-Rank Parallel Multifrontal Triangular Solve with Many Right-Hand Sides, Block Preconditioning Techniques for Geophysical Electromagnetics, An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations, Matrices with Hierarchical Low-Rank Structures, Bridging the Gap Between Flat and Hierarchical Low-Rank Matrix Formats: The Multilevel Block Low-Rank Format, MFEM: a modular finite element methods library, Inexact Newton-type methods based on Lanczos orthonormal method and application for full waveform inversion, Unnamed Item, Fast Approximation of the Gauss--Newton Hessian Matrix for the Multilayer Perceptron, Preserving Positive Definiteness in Hierarchically Semiseparable Matrix Approximations, A highly accurate finite-difference method with minimum dispersion error for solving the Helmholtz equation, An efficient hybrid tridiagonal divide-and-conquer algorithm on distributed memory architectures, Parallel accelerated cyclic reduction preconditioner for three-dimensional elliptic PDEs with variable coefficients, A polygonal discontinuous Galerkin method with minus one stabilization, Truncated trust region method for nonlinear inverse problems and application in full-waveform inversion, Randomized GPU Algorithms for the Construction of Hierarchical Matrices from Matrix-Vector Operations, A Power Schur Complement Low-Rank Correction Preconditioner for General Sparse Linear Systems, Efficient Construction of an HSS Preconditioner for Symmetric Positive Definite $\mathcal{H}^2$ Matrices, Robust and Accurate Stopping Criteria for Adaptive Randomized Sampling in Matrix-Free Hierarchically Semiseparable Construction, Single-pass randomized QLP decomposition for low-rank approximation, A p-robust polygonal discontinuous Galerkin method with minus one stabilization, Interconnected hierarchical structures for fast direct elliptic solution, A Hierarchical Preconditioner for Wave Problems in Quasilinear Complexity, Hierarchical Orthogonal Factorization: Sparse Square Matrices

Uses Software

Cites Work