Given a sparse matrix $M \in \mathbb{R}^{n \times m}$ with $n \ll m$ and $\mathsf{nnz}$ being the number of non-zero-components. What is the running time of computing $M M^T$?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ What do you think? $\endgroup$– Yuval FilmusDec 3, 2016 at 18:44
-
1$\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$– Raphael ♦Dec 3, 2016 at 19:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The question doesn't make any sense. It doesn't make sense to ask for the running time of a computation, unless you specify an algorithm for that computation. So how would you calculate this product? That's the first thing you need to do: Specify an algorithm how you calculate the product.
The next step: Assuming that many array elements are zero, can you reduce the amount of work that this algorithm would be doing? For example, if you know that x = 0, then it's pointless to multiply xy because you know the result is 0. And it's pointless to add xy to z, because that doesn't change z. So how can you take advantage of many array elements being zero? What's the runtime if you do that?
The next step: Assuming that many array elements are zero, can you reduct the amount of work further? Would you need some clever data structures? If yes, which ones?
