Multiplication of matrices with different sparseness properties on dynamically reconfigurable meshes

Algorithms for multiplying several types of sparse nxn-matrices on dynamica lly reconfigurable n x n-arrays are presented. For some classes of sparse m atrices constant time algorithms are given, e.g., when the first matrix has at most kn elements in each column or in each row and the second matrix ha s at most kn nonzero elements in each row, where k is a constant, Moreover, O(k root n) algorithms are obtained for the case that one matrix is a gene ral sparse matrix with at most kn nonzero elements and the other matrix has at most k nonzero elements in every row or in every column. Also a lower b ound of Omega(root kn) is proved for this and other cases which shows that the algorithms are close to the optimum.