Efficiently compute parallel matrix-vector product for block vectors?
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.