Return to 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!

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!

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

This results in two questions:

1. 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?
2. Depending on the application, the matrix $E$ could be a Fourier matrix, i.e. computing $w_p$ could be done by an FFT. Do I have to do $N$ FFTs then or is there a "block-wise" FFT idea/implementation?

Any help, suggestions or links to publications are appreciated!

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!