1
$\begingroup$

Question 1:

Given two integer matrices $A$ and $B$, and let $C$ be $AB$.

$C$ can be very big in pratice, so what is the fastest way to compute the statistical data of $C$?

For example,

$$A=\begin{pmatrix}1&2\\3&4\end{pmatrix}$$ $$B=\begin{pmatrix}0&0\\0&1\end{pmatrix}$$

The statistical data of $C$ are:

Value Appearing times in $C$
0 2
2 1
4 1

Question 2:

Given a single value $v$, what is the fastest way to know its appearing times in $C$? Computing the product and counting the number is the only way or not?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Why would there be any faster way than just computing the product and counting the number of appearances of each integer in the result? $\endgroup$
    – Gerry Myerson
    Commented Apr 20 at 22:23
  • 6
    $\begingroup$ Say $A,B$ are $1000\times1000$ $0,1$ matrices. You want to know, say, how many $250$s there are in $AB$, faster than by computing $AB$ and counting. I'm skeptical that this can be done. Just changing a single one in $A$ to a zero can make a large change in the number of $250$s. $\endgroup$
    – Gerry Myerson
    Commented Apr 20 at 23:58

0

Reset to default

You must log in to answer this question.