A novel partitioning method for accelerating the block Cimmino algorithm
From MaRDI portal
Abstract: We propose a novel block-row partitioning method in order to improve the convergence rate of the block Cimmino algorithm for solving general sparse linear systems of equations. The convergence rate of the block Cimmino algorithm depends on the orthogonality among the block rows obtained by the partitioning method. The proposed method takes numerical orthogonality among block rows into account by proposing a row inner-product graph model of the coefficient matrix. In the graph partitioning formulation defined on this graph model, the partitioning objective of minimizing the cutsize directly corresponds to minimizing the sum of inter-block inner products between block rows thus leading to an improvement in the eigenvalue spectrum of the iteration matrix. This in turn leads to a significant reduction in the number of iterations required for convergence. Extensive experiments conducted on a large set of matrices confirm the validity of the proposed method against a state-of-the-art method.
Recommendations
- Partitioning strategies for the block Cimmino algorithm
- A Block Projection Method for Sparse Matrices
- Block-iterative algorithm with row projection for consistent linear system
- Enhancing Block Cimmino for Sparse Linear Systems with Dense Columns via Schur Complement
- scientific article; zbMATH DE number 434532
Cites work
- A Block Projection Method for Sparse Matrices
- A fully asynchronous multifrontal solver using distributed dynamic scheduling
- A multithreaded recursive and nonrecursive parallel sparse direct solver
- A Parallel Matrix Scaling Algorithm
- A projection method for solving nonsymmetric linear systems on multiprocessors
- An overview of SuperLU
- Benchmarking optimization software with performance profiles.
- Block Lanczos Techniques for Accelerating the Block Cimmino Method
- Block-iterative methods for consistent and inconsistent linear equations
- Calculating the Singular Values and Pseudo-Inverse of a Matrix
- Component-Averaged Row Projections: A Robust, Block-Parallel Scheme for Sparse Linear Systems
- Exploiting multiple levels of parallelism in sparse matrix-matrix multiplication
- scientific article; zbMATH DE number 3523319 (Why is no real title available?)
- scientific article; zbMATH DE number 833705 (Why is no real title available?)
- scientific article; zbMATH DE number 3892457 (Why is no real title available?)
- Improved Error Bounds for Underdetermined System Solvers
- Influence of the Eigenvalue Spectrum on the Convergence Rate of the Conjugate Gradient Method
- MIQR: A Multilevel Incomplete QR Preconditioner for Large Sparse Least‐Squares Problems
- Numerical Methods for Computing Angles Between Linear Subspaces
- On the augmented system approach to sparse least-squares problems
- Parallel application of block-iterative methods in medical imaging and radiation therapy
- Parallel minimum norm solution of sparse block diagonal column overlapped underdetermined systems
- Partitioning strategies for the block Cimmino algorithm
- Properties of a class of block-iterative methods
- Row Projection Methods for Large Nonsymmetric Linear Systems
- Simultaneous input and output matrix partitioning for outer-product -- parallel sparse matrix-matrix multiplication
- Stopping Criteria for Iterative Solvers
- The augmented block Cimmino distributed method
- The block conjugate gradient algorithm and related methods
- The rate of convergence of conjugate gradients
- The University of Florida sparse matrix collection
- Two Fast Algorithms for Sparse Matrices: Multiplication and Permuted Transposition
Cited in
(12)- Restarted randomized surrounding methods for solving large linear equations
- A hybrid approach for the parallelization of a block iterative algorithm
- scientific article; zbMATH DE number 434532 (Why is no real title available?)
- A Block Projection Method for Sparse Matrices
- Block Lanczos Techniques for Accelerating the Block Cimmino Method
- Extensions of the Augmented Block Cimmino Method to the Solution of Full Rank Rectangular Systems
- Randomized extended average block Kaczmarz for solving least squares
- Partitioning strategies for the block Cimmino algorithm
- Enhancing Block Cimmino for Sparse Linear Systems with Dense Columns via Schur Complement
- The Reflection Method for the Numerical Solution of Linear Systems
- Row Replicated Block Cimmino
- On a deterministic block Kaczmarz-type method and its acceleration for the solution of large-scale linear systems
This page was built for publication: A novel partitioning method for accelerating the block Cimmino algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4562334)
