On the scalability of hypergraph models for sparse matrix partitioning

Bora Uçar; Umit Catalyurek

On the scalability of hypergraph models for sparse matrix partitioning

Bora Uçar ^{1, 2} Umit Catalyurek ³

1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms

Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme

2 LIP - Laboratoire de l'Informatique du Parallélisme

3 Department of Biomedical Informatics [Columbus]

Abstract : We investigate the scalability of the hypergraph-based sparse matrix partitioning methods with respect to the increasing sizes of matrices and number of nonzeros. We propose a method to rowwise partition the matrices that correspond to the discretization of two-dimensional domains with the five-point stencil. The proposed method obtains perfect load balance and achieves very good total communication volume. We investigate the behaviour of the hypergraph-based rowwise partitioning method with respect to the proposed method, in an attempt to understand how scalable the former method is. In another set of experiments, we work on general sparse matrices under different scenarios to understand the scalability of various hypergraph-based one- and two-dimensional matrix partitioning methods.

Keywords : Sparse matrix-vector multiplication Matrix partitioning Hypergraph partitioning Sparse matrix-vector multiplication.

Document type :

Conference papers

Domain :

Computer Science [cs] / Distributed, Parallel, and Cluster Computing [cs.DC]

Mathematics [math] / Combinatorics [math.CO]

Complete list of metadatas

Cited literature [9 references] Display Hide Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00529088
Contributor : Bora Uçar <>
Submitted on : Sunday, October 24, 2010 - 7:28:44 PM
Last modification on : Friday, April 20, 2018 - 3:44:24 PM
Long-term archiving on : Friday, October 26, 2012 - 12:15:29 PM

ucca10.pdf

Files produced by the author(s)

On the scalability of hypergraph models for sparse matrix partitioning

File

Identifiers

Collections

Citation

Export

Metrics

434

218

Contact

On the scalability of hypergraph models for sparse matrix partitioning

File

Identifiers

Collections

Citation

Export

Share

Metrics

434

218

Contact