Parallel product of matrix transpose by itself How to calculate in parallel (using data partitioning parallelism on GPU or MPI) a product of matrix transpose by itself?
Apparently it can be done via a parallel transpose and multiplication. Any other way (better) way doing it (e.g. via recursion, etc.)?
Any references will be very helpful.
 A: Let's say you have an $R$ row, $C$ column real matrix $M$, with elements $m_{r c}$, $r = 1 .. R$, $c = 1 .. C$.
$$[M^T M]_{r c} = \sum_{i=1}^{R} m_{i r} m_{i c} \tag{1}\label{1}$$
and
$$[M M^T]_{r c} = \sum_{i=1}^{C} m_{r i} m_{c i} \tag{2}\label{2}$$
In $\eqref{1}$, you need two columns from the original matrix, to calculate one element in the $C \times C$ product matrix.
In $\eqref{2}$, you need two rows from the original matrix, to calculate one element in the $R \times R$ product matrix.
Efficiency of computing the product in both cases will mostly depend on whether the data (for a column for $\eqref{1}$, and for a row for $\eqref{2}$) is consecutive in memory or not. Ensuring this should be your first priority.
Data partitioning (essentially, which computing unit needs which rows/columns from the original matrix to compute the cells it has been assigned) is the second priority; for MPI, this is quite important, unless each process already has a copy of $M$, since transferring the matrix data will take a significant time compared to the time taken by the calculations.
The partitioning strategy is obviously simple: minimize the number of rows ($\eqref{1}$) or columns ($\eqref{2}$) that are needed to calculate the set of resulting cells, while keeping the number of cells in each set (for each process or core) roughly equal. Unfortunately, I am not aware of any algorithm that would directly yield the partitioning, given the size of the resulting matrix (always square in this case).
As an example, consider $\eqref{1}$ with $R = C = 5$, to be computed using 4 separate processors (in the MPI sense, as in "entities that process"; not necessarily as in "CPU processors"). One efficient partitioning strategy is to partition the elements in the product to processors $A$, $B$, $C$, and $D$ as
$$\begin{array}{l|ccccc}
\; & 1 & 2 & 3 & 4 & 5 \\
\hline
1 & A & D & D & A & A \\
2 & D & A & D & B & B \\
3 & D & D & C & C & C \\
4 & A & B & C & C & B \\
5 & A & B & C & B & A \end{array} \qquad \begin{array}{l}A: \text{ columns } 1, 4, 5 \\
B: \text{ columns } 2, 4, 5 \\
C: \text{ columns } 3, 4, 5 \\
D: \text{ columns } 1, 2, 3 \end{array}$$
As you can see, using this particular scheme, each processor will need three columns of data, or $3/5$, or $60%$, or $15$ elements, from the original matrix, to calculate the elements assigned to it.
