Sparse Matrix Multiplication on a Reconfigurable Mesh.
Martin Middendorf, Hartmut Schmeck, Gavin Turner · OpenGrey (Institut de l'Information Scientifique et Technique) · 1995
In this paper we show how mesh-connected n x n-processor arrays with dynamically reconfigurable busses can be used efficiently to compute the product of sparse n x n-matrices A and B. If A contains at most 0(1) nonzero elements per row and B contains at most 0(1) nonzero elements per column, the time of the algorithm is in 0(1). (orig.)