如何在不额外使用内存的情况下将矩阵分成四等分

本文关键字：情况下 内存 | 更新日期: 2023-09-27 18:02:00

我正在制作矩阵乘法的Strassen算法。该算法的基础是将矩阵A (N * N)分成A1-A4 (N/2 * N/2)的四分之一。为此，我使用周期并为矩阵的每四分之一分配内存。

    int r;
    double[,] A = new double[r, r]; 
    double[,] A1 = new double[r / 2, r / 2];
    double[,] A2 = new double[r / 2, r / 2];
    double[,] A3 = new double[r / 2, r / 2];
    double[,] A4 = new double[r / 2, r / 2];
    for (int i = 0; i < r / 2; i++)
    for (int j = 0; j < r / 2; j++)
    {
    A1[i, j] = A[i, j];
    }
    for (int i = 0; i < r / 2; i++)
    for (int j = r / 2; j < r; j++)
    {
    A2[i, j - r / 2] = A[i, j];
    }
    for (int i = r / 2; i < r; i++)
    for (int j = 0; j < r / 2; j++)
    {
    A3[i - r / 2, j] = A[i, j];
    }
    for (int i = r / 2; i < r; i++)
    for (int j = r / 2; j < r; j++)
    {
    A4[i - r / 2, j - r / 2] = A[i, j];
    }

有没有更简单的方法来做到这一点，没有额外的矩阵?(a1 = a[0…](n/2)- 1,0…(n/2)-1]例如)?

如何在不额外使用内存的情况下将矩阵分成四等分

我强烈建议使用所谓的Morton顺序，而不是矩阵的主要行或主要列布局内存布局。数据访问将变得容易得多(提供适合索引计算的函数)。此外，可以预先为较小的矩阵分配空间，因此在每次递归调用中不需要分配和释放。请注意，对于每个较小的矩阵大小，只需要使用一组矩阵，因为实际计算只允许结果从较小的矩阵流向较大的矩阵。

参见这里(3.3数据布局)获得更全面的解释。通常，当Strassen算法在课程中教授时，不会提到合适的内存布局，这显然会导致对这种实现思想的永久重新发现。

相关文章：