Load Balancing and Sparse Matrix Vector Multiplication on the Hypercube

摘要

We consider the calculation on a hypercube concurrent computer, of matrix vector multiplication y = Ax where A is a large sparse matrix. A good decomposition is crucial for the case when each column of A on the average has fewer non zero elements than there are nodes in the hypercube. We develop graph theoretical and simulated annealing techniques which can lead to essentially optimal hypercube decompositions. The performance of the concurrent computer depends strongly on any correlations in the placement of non zero elements of A. 7 refs., 8 figs., 2 tabs. (ERA citation 12:012987)