Sparse matrix decomposition with optimal load balancing

Load balancing in the decomposition of sparse matri-ces without disturbing the row/column ordering is inves-tigated. Both asymptotically and run-time efficient algo-rithms are proposed and implemented for one-dimensional (1D) striping and two-dimensional (2D) jagged partition-ing. Bisection method is successfully adopted to 1D parti-tioning by deriving and exploiting tight bounds on the value of an optimal solution. A bisection algorithm is proposed for 2D jagged partitioning by introducing a new 2D prob-ing scheme. A novel bidding algorithm is proposed for both 1D and 2D partitioning. Proposed algorithms are also space efficient since they only need the conventional compressed storage scheme for the given matrix, avoiding the need for a dense workload matrix in 2D decomposition. Experimental results on a large set of test matrices show that consider-ably better decompositions can be obtained by using opti-mal load balancing algorithms instead of heuristics. Pro-posed algorithms are 100 times faster than a single sparse matrix vector multiplication (SpMxV), in the-way 1D decompositions, on the overall average. Our jagged parti-tioning algorithms are only slower than a single Sp-MxV computation in the-way 2D decompositions, on the overall average.