A Novel Partitioning Method for Accelerating the Block Cimmino Algorithm

DOI10.1137/18M1166407zbMath1404.65018arXiv1710.07769OpenAlexW2963896572WikidataQ128757446 ScholiaQ128757446MaRDI QIDQ4562334

Cevdet Aykanat, F. Sukru Torun, Murat Manguoglu

Publication date: 19 December 2018

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

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

zbMATH Keywords

graph partitioningKrylov subspace methodsrow projection methodsblock Cimmino algorithmrow inner-product graph

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Iterative numerical methods for linear systems (65F10)

Related Items

Enhancing Block Cimmino for Sparse Linear Systems with Dense Columns via Schur Complement, Restarted randomized surrounding methods for solving large linear equations, The Reflection Method for the Numerical Solution of Linear Systems, Row Replicated Block Cimmino, Randomized Extended Average Block Kaczmarz for Solving Least Squares, Extensions of the Augmented Block Cimmino Method to the Solution of Full Rank Rectangular Systems

Uses Software

• Matlab
• PARDISO
• SuperLU
• MUMPS
• METIS
• SparseMatrix
• PaToH

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling
• Partitioning strategies for the block Cimmino algorithm
• Block-iterative methods for consistent and inconsistent linear equations
• The rate of convergence of conjugate gradients
• Parallel application of block-iterative methods in medical imaging and radiation therapy
• A projection method for solving nonsymmetric linear systems on multiprocessors
• On the augmented system approach to sparse least-squares problems
• The block conjugate gradient algorithm and related methods
• Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication
• Simultaneous Input and Output Matrix Partitioning for Outer-Product--Parallel Sparse Matrix-Matrix Multiplication
• A Multithreaded Recursive and Nonrecursive Parallel Sparse Direct Solver
• The university of Florida sparse matrix collection
• Parallel Minimum Norm Solution of Sparse Block Diagonal Column Overlapped Underdetermined Systems
• MIQR: A Multilevel Incomplete QR Preconditioner for Large Sparse Least‐Squares Problems
• An overview of SuperLU
• A Parallel Matrix Scaling Algorithm
• Properties of a class of block-iterative methods
• Stopping Criteria for Iterative Solvers
• A Block Projection Method for Sparse Matrices
• Row Projection Methods for Large Nonsymmetric Linear Systems
• Improved Error Bounds for Underdetermined System Solvers
• Influence of the Eigenvalue Spectrum on the Convergence Rate of the Conjugate Gradient Method
• Two Fast Algorithms for Sparse Matrices: Multiplication and Permuted Transposition
• Numerical Methods for Computing Angles Between Linear Subspaces
• Block Lanczos Techniques for Accelerating the Block Cimmino Method
• The Augmented Block Cimmino Distributed Method
• Component-Averaged Row Projections: A Robust, Block-Parallel Scheme for Sparse Linear Systems
• Calculating the Singular Values and Pseudo-Inverse of a Matrix
• Benchmarking optimization software with performance profiles.