Efficiently compute parallel matrix-vector product for block vectors?

Question

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!

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.