matrix blocking gives a segmentation fault

Question

I am trying to implement the Strassen algorithm in C++. I want to partition the square matrix 'hA' into 4 equal blocks.

// Initialize matrices on the host
float hA[N][N],ha11[N / 2][N / 2], ha12[N / 2][N / 2], ha21[N / 2][N / 2],
        ha22[N / 2][N / 2];
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        hA[i][j] = i;
        //hB[i][j] = i;
    }
}
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        printf("\n%d,%d\n", i, j);
        if (i < N / 2 & j < N / 2) {
            ha11[i][j] = hA[i][j];
        } else if (i < N / 2 & j >= N / 2) {
            ha12[i][j] = hA[i][j];
        } else if (i >= N / 2 & j < N / 2) {
            ha21[i][j] = hA[i][j];
        } else if (i >= N / 2 & j >= N / 2) {
            ha22[i][j] = hA[i][j];    //faulty!
        }
    }
}

I used above method for partitioning and it gets faulty as shown in the output below. But it works fine when I remove the last comparison in the 'if else' ladder.

Why does 'i' have a wrong value that is even outside the loop condition? Is there a more convenient way to do the partitioning than this way?

Answer 1

Your arrays should be N x N, not N/2 x N/2.

Your use of the bitwise operator & is unusual but works. I mistakenly thought you need a logical and ( && ) instead. Still, for readability I'd suggest the &&. You get the short circuiting with too.

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("\n%d,%d\n", i, j);
            if (i < N / 2 & j < N / 2) {
                ha11[i][j] = hA[i][j];
            } else if (i < N / 2 & j >= N / 2) {
                ha12[i][j] = hA[i][j];
            } else if (i >= N / 2 & j < N / 2) {
                ha21[i][j] = hA[i][j];
            } else if (i >= N / 2 & j >= N / 2) {
                ha22[i][j] = hA[i][j];    //faulty!
            }
        }
    }

Answer 2

To work with code as written, your sub arrays need to be NxN each, not N/2 by N/2, but I dont think this is actually the "error".

You are chopping the array into 4 equal parts, so they should be able to be smaller than the original. That leaves with two issues.

Your assignments are wrong, h11 is fine, but h12, h21 and h22 all need adjusting like this:

ha12[i-N/2][j-N/2] = hA[i][j];
ha21[i-N/2][j] = hA[i][j];
ha22[i-N/2][j-N/2] = hA[i][j];

instead of what you have, (though keep them where that are).

btw, it may be easier to read if you removes the if statements altogether, iterating over just one quarter, but doing 4 assignments per quarter.

A second, potential issue is of course what happens when N isn't divisible by 2. You code seems to ignore this, which maybe it can. I expect you need to think about where you want the odd values to go, and make the sub arrays each large enough for teh rounded up parts.