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?
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).
