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? 



Upper bound on the number of non-zero entries of the product of sparse matrices
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).


