Workshops Archive

SpSYRK: Half the Work in Distributed Sparse Matrix Multiplication


Workshop: IA^3 2026 — 16th Workshop on Irregular Applications: Architectures and Algorithms

Authors: Thomas McFarland and Julian Bellavita (Cornell University) and Giulia Guidi (Cornell University, Lawrence Berkeley National Laboratory)

Abstract: The symmetric rank-k update (SYRK), C = AA^⊤, computes the dot product between each pair of rows of A. Its sparse variant is central to similarity-based approaches in machine learning, graph analytics, and genomics. Existing distributed sparse matrix multiplication algorithms, such as Sparse SUMMA, treat sparse SYRK as a generic multiplication, leaving performance untapped.

In this paper, we present a distributed sparse SYRK algorithm that leverages symmetry. The approach reduces per-process computation compared with state-of-the-art distributed SpGEMM. A second variant reorders communication to avoid materializing A^⊤ and reduce communication volume.

The algorithm achieves a 2× speedup over an optimized Sparse SUMMA on matrices. Our variant achieves superior scaling at high process counts. The approach is a drop- in replacement for any application computing C = AA^⊤ via a distributed SpGEMM routine, and its triangular output can be consumed directly by subsequent operations with reduced compute and memory footprint.


Back to IA^3 2026 — 16th Workshop on Irregular Applications: Architectures and Algorithms Archive Listing

Back to Full Workshop Archive Listing