Copyright Notice:

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Publications of SPCL

N. Gleinig, M. Besta, T. Hoefler:

 I/O-Optimal Cache-Oblivious Sparse Matrix-Sparse Matrix Multiplication

(In Proceedings of the 36th IEEE Interational Parallel and Distributed Processing Symposium (to appear), Jun. 2022)

Publisher Reference


Data movements between different levels of the memory hierarchy (I/O-transitions, or simply I/Os) are a critical performance bottleneck in modern computing. Therefore it is a problem of high practical relevance to find algorithms that use a minimal number of I/Os. We present a cache-oblivious sparse matrix-sparse matrix multiplication algorithm that uses a worst-case number of I/Os that matches a previously established lower bound for this problem. This improves the worst-case I/O-complexity of the previously best known algorithm for this problem (which is cache-aware) by a logarithmic multiplicative factor.


download article:


  author={Niels Gleinig and Maciej Besta and Torsten Hoefler},
  title={{I/O-Optimal Cache-Oblivious Sparse Matrix-Sparse Matrix Multiplication}},
  booktitle={Proceedings of the 36th IEEE Interational Parallel and Distributed Processing Symposium (to appear)},