Geodesic
Communication balancing in parallel sparse matrix-vector multiplication
Electronic transactions on numerical analysis, Tome 21 (2005), pp. 47-65
Given a partitioning of a sparse matrix for parallel matrix-vector multiplication, which determines the total communication volume, we try to find a suitable vector partitioning that balances the communication load among the processors. We present a new lower bound for the maximum communication cost per processor, an optimal algorithm that attains this bound for the special case where each matrix column is owned by at most two processors, and a new heuristic algorithm for the general case that often attains the lower bound. This heuristic algorithm tries to avoid raising the current lower bound when assigning vector components to processors. Experimental results show that the new algorithm often improves upon the heuristic algorithm that is currently implemented in the sparse matrix partitioning package Mondriaan. Trying both heuristics combined with a greedy improvement procedure solves the problem optimally in most practical cases. The vector partitioning problem is proven to be NP-complete.
Classification : 05C65, 65F10, 65F50, 65Y05
Keywords: vector partitioning, matrix-vector multiplication, parallel computing, sparse matrix, bulk synchronous parallel 
@article{ETNA_2005__21__a5,
     author = {Bisseling,  Rob H. and Meesen,  Wouter},
     title = {Communication balancing in parallel sparse matrix-vector multiplication},
     journal = {Electronic transactions on numerical analysis},
     pages = {47--65},
     year = {2005},
     volume = {21},
     zbl = {1121.65318},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ETNA_2005__21__a5/}
}
TY  - JOUR
AU  - Bisseling,  Rob H.
AU  - Meesen,  Wouter
TI  - Communication balancing in parallel sparse matrix-vector multiplication
JO  - Electronic transactions on numerical analysis
PY  - 2005
SP  - 47
EP  - 65
VL  - 21
UR  - http://geodesic.mathdoc.fr/item/ETNA_2005__21__a5/
LA  - en
ID  - ETNA_2005__21__a5
ER  - 
%0 Journal Article
%A Bisseling,  Rob H.
%A Meesen,  Wouter
%T Communication balancing in parallel sparse matrix-vector multiplication
%J Electronic transactions on numerical analysis
%D 2005
%P 47-65
%V 21
%U http://geodesic.mathdoc.fr/item/ETNA_2005__21__a5/
%G en
%F ETNA_2005__21__a5
Bisseling,  Rob H.; Meesen,  Wouter. Communication balancing in parallel sparse matrix-vector multiplication. Electronic transactions on numerical analysis, Tome 21 (2005), pp. 47-65. http://geodesic.mathdoc.fr/item/ETNA_2005__21__a5/