Block Matrix Transpose

Question

I wanted to implement transposition of a matrix by dividing the input matrix into blocks and then transposing them. I referred to the corresponding post A Cache Efficient Matrix Transpose Program? and wrote my code like this:

#include<iostream>
#include<stdlib.h>
#define m 4
#include<sys/time.h>
#include<time.h>
#include<malloc.h>

using namespace std;

int **a, **b, **c;
int count = 0;
clock_t t1, t2;    
int blocksize = 2;

int main(){
    a = (int **)malloc(m*sizeof(int *));
    for(int i = 0;i<m;i++){
            a[i] = (int *)malloc(m*sizeof(int));
    }
    b = (int **)malloc(m*sizeof(int *));
    for(int i = 0;i<m;i++){
            b[i] = (int *)malloc(m*sizeof(int));
    }
    for(int i=0; i<m; i++){
            for(int j =0; j<m; j++){
                    a[i][j]=(2*i)+(3*j);
            }
    }
    for(int i=0; i<m; i++){
            for(int j =0; j<m; j++){
                    cout << a[i][j] << "\t";
            }
            cout << "\n";
     }
    cout << "\n";
    t1 = clock();
    // MAIN BLOCK TRANSPOSE CODE
    for (int i = 0; i < m; i += blocksize) {
        for (int j = 0; j < m; j += blocksize) {
                    for (int k = i; k < i + blocksize; ++k) {
                            for (int l = j; l < j + blocksize; ++l) {
                                    b[k + l*m] = a[l + k*m];
                            }
                    }
            }
    }
    t2 = clock();
    for(int i=0; i<m; i++){
            for(int j =0; j<m; j++){
                    cout << b[i][j] << "\t";
            }
            cout << "\n";
     }
    free(a);
    free(b);
    cout << "\n";
    cout << (double)(t2-t1)/CLOCKS_PER_SEC << "\n";
return 0;
}

However, the code is not working as expected. I implemented the code that is said to be working in the corresponding post. Please help if possible.

Input Array:

0       3       6       9
2       5       8       11
4       7       10      13
6       9       12      15

Expected Output Array:

0       2       4       6
3       5       7       9  
6       8       10      12  
9       11      13      15

Obtained Result:

0       3       6       9
Segmentation fault

What do you mean by "the code is not working as expected". What is it doing? What were you expecting? — Matthew Strawbridge, Apr 21 '13 at 18:23
It is displaying the first row of orignal matrix and gives segmentation fault — Justin Carrey, Apr 21 '13 at 18:24
I think your matrix is supposed to be encoded in a single array, not in an array of arrays. See the `Edit 2` of the linked question. — didierc, Apr 21 '13 at 18:25
"not working as expected" is not good enough. Explain what you expect, and how the program fails to meet those expectations. And edit the question rather than adding comments to supply missing detail. — David Heffernan, Apr 21 '13 at 18:27

score 2 · Accepted Answer · answered Apr 21 '13 at 18:32

I think your matrix is supposed to be encoded in a single array, not in an array of arrays (See the Edit 2 of the linked question).

You might want to try that instead:

int *a, *b, *c;

a = (int *)malloc(m*m*sizeof(int));
b = (int *)malloc(m*m*sizeof(int));
for(int i=0; i<m; i++){
        for(int j =0; j<m; j++){
                a[i*m+j]=(2*i)+(3*j);
        }
}
for(int i=0; i<m; i++){
        for(int j =0; j<m; j++){
                cout << a[i*m+j] << "\t";
        }
        cout << "\n";
 }
cout << "\n";

Awesome man! Thanks. That simple modification made my program work correctly :) — Justin Carrey, Apr 21 '13 at 18:39

Block Matrix Transpose

1 Answers1