A Distributed-Memory Randomized Structured Multifrontal Method for Sparse Direct Solutions

DOI10.1137/16M1079221zbMath1393.65002OpenAlexW2749893789MaRDI QIDQ5350214

Venkataramanan Balakrishnan, Jian-Lin Xia, Zixing Xin, Stephen Cauley, Maarten V. de Hoop

Publication date: 28 August 2017

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

Full work available at URL: https://doi.org/10.1137/16m1079221

zbMATH Keywords

fast direct solverdistributed memoryrank structureskinny matricesrandomized multifrontal methodtree parallelism

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Factorization of matrices (15A23) Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20) Direct numerical methods for linear systems and matrix inversion (65F05) Numerical algorithms for specific classes of architectures (65Y10)

Related Items

An Incomplete Cholesky Preconditioner Based on Orthogonal Approximations, A numerical study of multi-parameter full waveform inversion with iterative regularization using multi-frequency vibroseis data, A Distributed-Memory Randomized Structured Multifrontal Method for Sparse Direct Solutions, Fast Factorization Update for General Elliptic Equations Under Multiple Coefficient Updates, Interconnected hierarchical structures for fast direct elliptic solution

Uses Software

• SuperLU-DIST
• ScaLAPACK
• MUMPS
• Scotch

Cites Work

• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• A fast direct solver for elliptic problems on general meshes in 2D
• Communication results for parallel sparse Cholesky factorization on a hypercube
• Multifrontal parallel distributed symmetric and unsymmetric solvers
• Hierarchical matrices based on a weak admissibility criterion
• Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices
• An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation
• Parallel Randomized and Matrix-Free Direct Solvers for Large Structured Dense Linear Systems
• A Direct Solver with $O(N)$ Complexity for Variable Coefficient Elliptic PDEs Discretized via a High-Order Composite Spectral Collocation Method
• Randomized algorithms for the low-rank approximation of matrices
• On the Numerical Rank of the Off-Diagonal Blocks of Schur Complements of Discretized Elliptic PDEs
• Fast algorithms for hierarchically semiseparable matrices
• A Fast Randomized Algorithm for Computing a Hierarchically Semiseparable Representation of a Matrix
• Superfast Multifrontal Method for Large Structured Linear Systems of Equations
• The Multifrontal Solution of Indefinite Sparse Symmetric Linear
• The Multifrontal Method for Sparse Matrix Solution: Theory and Practice
• An Algorithm for Reducing the Bandwidth and Profile of a Sparse Matrix
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• A Mapping Algorithm for Parallel Sparse Cholesky Factorization
• ScaLAPACK Users' Guide
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• A Superfast Structured Solver for Toeplitz Linear Systems via Randomized Sampling
• Improving Multifrontal Methods by Means of Block Low-Rank Representations
• A Parallel Geometric Multifrontal Solver Using Hierarchically Semiseparable Structure
• A Fast $ULV$ Decomposition Solver for Hierarchically Semiseparable Representations
• Efficient Structured Multifrontal Factorization for General Large Sparse Matrices
• Randomized Sparse Direct Solvers
• A Distributed-Memory Randomized Structured Multifrontal Method for Sparse Direct Solutions
• Efficient Scalable Algorithms for Solving Dense Linear Systems with Hierarchically Semiseparable Structures
• SuperLU_DIST
• Nested Dissection of a Regular Finite Element Mesh