mardi 29 novembre 2016

"Splitting" a matrix in constant time

I am trying to implement Strassen's algorithm for matrix multiplication in C++, and I want to find a way to split two matrices into four parts each in constant time. Here is the current way I am doing so:

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        A11[i][j] = a[i][j];
        A12[i][j] = a[i][j+n];
        A21[i][j] = a[i+n][j];
        A22[i][j] = a[i+n][j+n];
        B11[i][j] = b[i][j];
        B12[i][j] = b[i][j+n];
        B21[i][j] = b[i+n][j];
        B22[i][j] = b[i+n][j+n];
    }
}

This approach is obviously O(n^2), and it adds n^2*log(n) to the runtime, as it is called for each recursive call.

It seems that the way to do this in constant time is to create pointers to the four sub-matrices, rather than copy over the values, but I am having a difficult time figuring out how to create those pointers. Any help would be appreciated.

Aucun commentaire:

Enregistrer un commentaire