1
$\begingroup$

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?

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$ Apr 8 '18 at 0:46
  • $\begingroup$ The product of two sparse matrices can be dense. $\endgroup$
    – Mahdi
    Apr 8 '18 at 13:03
  • 1
    $\begingroup$ To get sensible bounds you need some structure of the matrices. $\endgroup$
    – Igor Rivin
    Apr 8 '18 at 16:54
1
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.