  Sparse matrix multiplication (SpGEMM) is a fundamental kernel used in many
diverse application areas, both numerical and discrete. For example, many
algebraic graph algorithms rely on SpGEMM in the tropical semiring to compute
shortest paths in graphs. Recently, SpGEMM has received growing attention
regarding implementations for specific (parallel) architectures. Yet, this
concerns only the static problem, where both input matrices do not change. In
many applications, however, matrices (or their corresponding graphs) change
over time. Although recomputing from scratch is very expensive, we are not
aware of any dynamic SpGEMM algorithms in the literature. In this paper, we
thus propose a batch-dynamic algorithm for MPI-based parallel computing.
Building on top of a distributed graph/matrix data structure that allows for
fast updates, our dynamic SpGEMM reduces the communication volume
significantly. It does so by exploiting that updates change far fewer matrix
entries than there are non-zeros in the input operands. Our experiments with
popular benchmark graphs show that our approach pays off. For batches of
insertions or removals of matrix entries, our dynamic SpGEMM is substantially
faster than the static algorithms in the state-of-the-art competitors CombBLAS,
CTF and PETSc.
