Sparse Matrix Computations on Parallel Processor Arrays
Andrew T. Ogielski, William A. Aiello · SIAM Journal on Scientific Computing · 1993
This paper investigates the balancing of distributed compressed storage of large sparse matrices on a massively parallel computer. For fast computation of matrix–vector and matrix–matrix products on a rectangular processor array with efficient communications along its rows and columns it is required that the nonzero elements of each matrix row or column be distributed among the processors located within the same array row or column, respectively. Randomized packing algorithms are constructed with such properties, and it is proved that with high probability the algorithms produce well-balanced storage for sufficiently large matrices with bounded number of nonzeros in each row and column, but no other restrictions on structure. Then basic matrix–vector multiplication routines are described with fully parallel interprocessor communications and intraprocessor gather and scatter operations. Their efficiency isdemonstrated on the 16,384-processor MasPar computer.
Cited by 81 works. doi:10.1137/0914033
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- Probability Inequalities for sums of Bounded Random Variables
- Some Complexity Results for Matrix Computations on Parallel Processors
- The C++ programming language (2nd ed.)
- Probability Inequalities for Sums of Bounded Random Variables
- Probability Inequalities for the Sum of Independent Random Variables
- Sparse Matrix Technology
- Parallel Matrix and Graph Algorithms
- Krylov Subspace Methods on Supercomputers
- Parallel Algorithms for Dense Linear Algebra Computations