0
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ What do you think? $\endgroup$ – Yuval Filmus Dec 3 '16 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 '16 at 19:53
1
$\begingroup$

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?

$\endgroup$

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.