Upper bound on the number of non-zero entries of the product of sparse matrices

I have two sparse matrices: $A$ of dimension $m \times k$ and $B$ of dimension $k \times n$.

Is there a way to know how many non-zero entries there are in $C = A B$ without computing $A B$?

I can see that the trivial upper bound is $m n$ but can I get a better upper bound?

• For many cases that occur in practice, not really. You just need one column of m ones and one row of n ones to generate (potentially) the maximum number of nonzero entries. If the first matrix has a lot of zero rows or the second a lot of zero columns, you can narrow the bound a bit. Gerhard "That's Not Sparse, It's Vacant" Paseman, 2018.04.07. Apr 8 '18 at 0:46
• The product of two sparse matrices can be dense. Apr 8 '18 at 13:03
• To get sensible bounds you need some structure of the matrices. Apr 8 '18 at 16:54

Rephrasing:

Given matrices $\mathrm A_1 \in \mathbb R^{m \times k}$ and $\mathrm A_2 \in \mathbb R^{k \times n}$, is there an upper bound on the number of nonzero entries of the $m \times n$ matrix $\mathrm A_1 \mathrm A_2$?

Let Boolean matrices $\mathrm B_1 \in \{0,1\}^{m \times k}$ and $\mathrm B_2 \in \{0,1\}^{k \times n}$ be obtained by applying the function

$$x \mapsto \begin{cases} 1 & \text{if } x \neq 0\\ 0 & \text{if } x = 0\end{cases}$$

to each entry of $\mathrm A_1$ and $\mathrm A_2$, respectively. Note that $\mathrm B_1$ and $\mathrm B_2$ contain information on the sparsity patterns of $\mathrm A_1$ and $\mathrm A_2$, respectively. The number of nonzero entries of $\mathrm B_1 \mathrm B_2$ provides an upper bound on the number of nonzero entries of $\mathrm A_1 \mathrm A_2$.

Since we are interested only in deciding whether an entry is zero or not, let us use Boolean algebra. The cost of deciding whether an entry of $\mathrm B_1 \mathrm B_2$ is zero or not is at most $k$ AND operations and $k-1$ OR operations. If one is lucky, only one AND operation is required.

Thus, the total computational cost is at most $m n (2k-1)$ logical operations, which is cheaper than performing $m n (2k-1)$ floating-point operations (plus counting the number of nonzero entries).