Structure prediction and computation of sparse matrix products

We consider(1) the problem of predicting the nonzero structure of a product of two or more matrices. Prior knowledge of the nonzero structure can be applied to optimize memory allocation and to determine the optimal multiplication order for a chain product of sparse matrices. We adapt a recent algorithm by the author and show that the essence of the nonzero structure and hence, a near-optimal order of multiplications, can be determined in near-linear time in the number of nonzero entries, which is much smaller than the lime required for the multiplications. An experimental evaluation of the algorithm demonstrates that it is practical for matrices of order 10(3) with 10(4) nonzeros (or larger). A relatively small pre-computation results in a large time saved in the computation-intensive multiplication.