I have $P$ processors, each having a different vector $v_p$ of size $N$, $p=1, ..., P$. I now want to compute the matrix-vector product $$w = (E\otimes I_N)v$$ in parallel, where $\otimes$ is the Kronecker product, $v = (v_1, ..., v_P)^T$ is the stacked vector consisting of all local vectors $v_p$, $E = (e_{pj})_{p,j}\in\mathbb{C}^{P\times P}$ some dense matrix and $I_N$ is the identity matrix of size $N\times N$.

So, to do this, each processor $p=1, ..., P$ has to compute $$w_p = \sum_{j=1}^P e_{pj} v_j$$ and for this, all $P$ vectors $v_p$ have to be sent to all $P$ processors.

Now, $N$ is pretty large (say, $10^8$), in particular much larger than $P$ (which is only 10-100) and so large that $NP$ (the size of $w$ and/or all vectors $v_p$ together) does not fit into each processor's memory. Also, sending all these vectors $v_p$ in an all-to-all fashion seems pretty hard on the network.

Is there a standard and/or particular efficient way to compute this sum for a general matrix $E$? What would be the complexity of this approach?

Any help, suggestions or links to publications are appreciated!

  • $\begingroup$ Please ask only one separate question per post. It seems to me that your questions 1 and 2 can be answered independently of each other. $\endgroup$
    – Raphael
    Feb 16, 2018 at 15:21
  • $\begingroup$ Welcome to CS.SE! What does the notation $E\otimes I_N$ represent? $\endgroup$
    – D.W.
    Feb 16, 2018 at 16:52
  • $\begingroup$ You're both right, of course. I edited the question accordingly. Thanks for your help! $\endgroup$ Feb 17, 2018 at 8:39

1 Answer 1


You can do this as a parallel sum. You want to compute

$$w_i = \sum_{j=1}^P e_{ij} v_j,$$

where processor $j$ has the vector $v_j$.

One way to do this is to have each processor compute $e_{ij} v_j$ locally. Then, use a binary tree to compute the sum. In particular, processor 1 sends $e_{i1} v_1$ to processor 2, which computes the sum $e_{i1} v_1 + e_{i2} v_2$; processor 3 sends $e_{i3} v_3$ to processor 4, which computes the sum $e_{i3} v_3 + e_{i4} v_4$; and so on. Then, processor 2 sends $e_{i1} v_1 + e_{i2} v_2$ to processor 4, which computes the sum $e_{i1} v_1 + e_{i2} v_2 + e_{i3} v_3 + e_{i4} v_4$; and so on. Repeat until you have computed the final sum. Basically, this is just parallel sum of some vectors (parallel aggregation).

This requires sending $\Theta(NP)$ data over the network, and $\Theta(\log P)$ rounds of communication. Each processor only needs memory for $\Theta(N)$ data. So, it looks like it meets all your requirements. It may still be hard on the network, but that seems unavoidable given what you are trying to compute. You'll do this $P$ times, to compute $w_1,\dots,w_P$, so in total it will require $\Theta(NP^2)$ data on the network, $\Theta(P \log P)$ rounds of communication (though they can be parallelized down to $\Theta(\log P)$ if the network is fast enough), and $\Theta(N)$ space on each processor.

  • $\begingroup$ Hm, interesting.. I was so focused on matrix-vector products that I did not see the relations to parallel sums. Thanks, very enlightening! $\endgroup$ Feb 17, 2018 at 8:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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