Name
Abstract | ||
|---|---|---|
We investigate one dimensional partitioning of sparse matrices under a given ordering of the rows/columns. The partitioning constraint is to have load balance across processors when different parts are assigned to different processors. The load is defined as the number of rows, or columns, or the nonzeros assigned to a processor. The partitioning objective is to optimize different functions, including the well-known total communication volume arising in a distributed memory implementation of parallel sparse matrix-vector multiplication operations. The difference between our problem in this work and the general sparse matrix partitioning problem is that the parts should correspond to disjoint intervals of the given order. Whereas the partitioning problem without the interval constraint corresponds to the NP-complete hyper graph partitioning problem, the restricted problem corresponds to a polynomial-time solvable variant of the hyper graph partitioning problem. We adapt an existing dynamic programming algorithm designed for graphs to solve two related partitioning problems in graphs. We then propose graph models for a given hyper graph and a partitioning objective function so that the standard cut size definition in the graph model exactly corresponds to the hyper graph partitioning objective function. In extensive experiments, we show that our proposed algorithm is helpful in practice. It even demonstrates performance superior to the standard hyper graph partitioners when the number of parts is high. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/CLUSTER.2012.77 | CLUSTER |
Keywords | Field | DocType |
restricted problem corresponds,partitioning constraint,graph model,np-complete hyper graph,hyper graph,related partitioning problem,partitioning problem,partitioning objective function,partitioning objective,standard hyper graph partitioners,balanced sparse matrix partitioning,matrix multiplication,measurement,graph theory,parallel computing,vectors,computational complexity,dynamic programming,sparse matrices,parallel algorithms,hypergraphs,linear programming,resource allocation | Graph theory,Space partitioning,Graph power,Computer science,Parallel computing,Constraint graph,Algorithm,Theoretical computer science,Graph bandwidth,Graph partition,Voltage graph,Complement graph | Conference |
ISSN | Citations | PageRank |
1552-5244 | 0 | 0.34 |
References | Authors | |
11 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anael Grandjean | 1 | 0 | 0.68 |
| Johannes Langguth | 2 | 85 | 12.71 |
| Bora Ucar | 3 | 75 | 7.50 |