An improved exact algorithm and an NP-completeness proof for sparse matrix bipartitioning

Timon E. Knigge, Rob H. Bisseling

We investigate sparse matrix bipartitioning -- a problem where we minimize the communication volume in parallel sparse matrix-vector multiplication. We prove, by reduction from gra…