How to divide a matrix into quarters without additional use of memory?

Question

I am making the Strassen algorithm for matrix multiplication. The basis of this algorithm is division of the matrix A (N * N) into quarters A1-A4 (N / 2 * N / 2). To do this I use cycles and allocate the memory for each quarter of the matrix.

    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];
    }

Is there any simpler way to do this, without additional matrices? (A1=A [0 ... (n / 2)-1, 0 ... (n / 2)-1] for example)?

Answer 1

I would strongly suggest using the so-called Morton order instead of row-major or column-majopr layout memory layout for matrices here. The data access would become much easier (provided suitable functions for index calculation). Furthermore, space for the smaller matrices could be allocated beforehand, so that no allocation and deallocation is necessary in each recursive call. Note that for each smaller matrix size, only one set of matrices needs to be used, as actual calculation lets results flow only from smaller to bigger matrices.

See here (3.3 Data Layout) for a more comprehensive explanation. Usually, when Strassen's algorithm is taught in a curriculum, the suitable memory layout is not mentioned, which apparently leads to permanent rediscovery of this implementation idea.