2

如何并行化矩阵转置？

我知道要转置矩阵，我必须对此应用一些东西：

for (int i = 0; i < matrix.length - 1; i++) {
    for (int j = i + 1; j < matrix[i].length; j++) {
        tmp = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = tmp;
    }
}

但是如何并行化这个操作，我不知道。

我需要创建 N 个线程来转置矩阵 4n x 4n。

4

3 回答 3

8

因为这听起来像是一个家庭作业问题，所以我不会直接给你答案，但我会为你指出正确的方向。

假设您要转置一个 4x4 矩阵：

A B C D      A E I M
E F G H  ->  B F J N
I J K L      C G K O
M N O P      D H L P

如果我们将其分解为四个子矩阵：

A B | C D      A E | I M
E F | G H      B F | J N
----+----  ->  ----+----
I J | K L      C G | K O
M N | O P      D H | L P

请注意，生成的四个子矩阵都是您开始使用的四个子矩阵的转置（右上和左下矩阵交换了）。你怎么能利用这个？:)

于 2013-05-31T20:53:13.340 回答
1

我发现最好只携带一个“转置”标志（布尔、位等）并使用它来反转您的索引计算。这似乎是 BLAS、LAPACK 等的方式。

无论如何，由于缓存争用，在这里很难获得很多并行加速。

于 2013-05-31T20:54:24.493 回答
0

如果你想要一个简单的并行解决方案来解决你的问题，这样的事情可能会奏效。

double[][] matrix=new double[numberOfRows][numberOfColumns];
double[][] transpose = new double[numberOfColumns][numberOfRows];
IntStream.range(0, numberOfColumns * numberOfRows).parallel().forEach(i ->
{
    int m = i / numberOfRows;
    int n = i % numberOfRows;
    transpose[m][n] = matrix[n][m];
});

这使用了并行 IntStream，您可以将其视为针对矩阵中元素数量运行的并行化 for 循环。请注意，我分配了两个变量来获取我需要针对转置的实际行和列。

将流当前所在的索引除以行数，即可得到转置矩阵中目标行的索引。索引 i 和行数的模数为您提供了应分配的转置矩阵的列。

于 2018-06-21T10:51:15.783 回答