how can I transpose a 2D matrix in place in C?

Question

I'm trying to transpose a 2D matrix (10x10) in place:

for (a = 0; a < 10; a++) {
    for (b = 0; b < 10; b++) {
        tmp = matrix[a][b];
        matrix[b][a] = matrix[a][b];
        matrix[a][b] = tmp;
    }
}

If I can increase the starting value 'b' of the inner for statement by 1, it works fine.

However, when one loop is turned, the value of the variable is set to 0. It is very natural.

Is there a way to increase the starting value 'b' of the inner for loop after running around a loop?

I really want to solve this problem.

Can you use global variables or any other way to solve this problem?

Answer 1

Your swapping code is incorrect: you should overwrite the saved value first.

Furthermore, you must stop the inner loop when b == a, otherwise the values would be swapped twice, and the transposition would fail.

Here is a corrected version:

/* swap values on either side of the first diagonal */
for (a = 1; a < 10; a++) {
    /* stop the inner loop when b == a */
    for (b = 0; b < a; b++) {
        int tmp = matrix[a][b];
        matrix[a][b] = matrix[b][a];
        matrix[b][a] = tmp;
    }
}

This simple algorithm is not cache optimal for large matrices, especially for power of 2 sizes. More elaborate algorithms have been developed for in place matrix transpostion.

For example, here is a benchmark for 1024x1024 matrices comparing the naive algorithm with an advanced recursive approach:

#include <stdio.h>
#include <time.h>

#define SIZE 1024

static int mat[SIZE][SIZE];

void initialize_matrix(int matrix[SIZE][SIZE]) {
    int a, b, x = 0;
    for (a = 0; a < SIZE; a++) {
        for (b = 0; b < SIZE; b++) {
            mat[a][b] = x++;
        }
    }
}

int check_transpose_matrix(int matrix[SIZE][SIZE]) {
    int a, b, x = 0;
    for (a = 0; a < SIZE; a++) {
        for (b = 0; b < SIZE; b++) {
            if (mat[b][a] != x++)
                return 1;
        }
    }
    return 0;
}

void naive_transpose(int matrix[SIZE][SIZE]) {
    /* swap values on either side of the first diagonal */
    for (int a = 1; a < SIZE; a++) {
        /* stop the inner loop when b == a */
        for (int b = 0; b < a; b++) {
            int tmp = matrix[a][b];
            matrix[a][b] = matrix[b][a];
            matrix[b][a] = tmp;
        }
    }
}

#define THRESHOLD  4

void transpose_tile(int row, int col, int size, int matrix[SIZE][SIZE]) {
    if (size > THRESHOLD) {
        transpose_tile(row, col, size / 2, matrix);
        transpose_tile(row, col + size / 2, size / 2, matrix);
        transpose_tile(row + size / 2, col, size / 2, matrix);
        transpose_tile(row + size / 2, col + size / 2, size / 2, matrix);
    } else {
        for (int a = 0; a < size; a++) {
            for (int b = 0; b < size; b++) {
                int tmp = matrix[row + a][col + b];
                matrix[row + a][col + b] = matrix[col + b][row + a];
                matrix[col + b][row + a] = tmp;
            }
        }
    }
}

void transpose_tile_diag(int pos, int size, int matrix[SIZE][SIZE]) {
    if (size > THRESHOLD) {
        transpose_tile_diag(pos, size / 2, matrix);
        transpose_tile(pos, pos + size / 2, size / 2, matrix);
        transpose_tile_diag(pos + size / 2, size / 2, matrix);
    } else {
        /* swap values on either side of the first diagonal */
        for (int a = 1; a < size; a++) {
            /* stop the inner loop when b == a */
            for (int b = 0; b < a; b++) {
                int tmp = matrix[pos + a][pos + b];
                matrix[pos + a][pos + b] = matrix[pos + b][pos + a];
                matrix[pos + b][pos + a] = tmp;
            }
        }
    }
}

void advanced_transpose(int matrix[SIZE][SIZE]) {
    transpose_tile_diag(0, SIZE, matrix);
}

int main(int argc, char *argv[]) {
    clock_t t_min;

    initialize_matrix(mat);
    naive_transpose(mat);
    if (check_transpose_matrix(mat)) {
        printf("naive_transpose failed!\n");
        return 1;
    }
    /* benchmark naive algorithm */
    t_min = 0;
    for (int i = 0; i < 100; i++) {
        clock_t t = clock();
        naive_transpose(mat);
        t = clock() - t;
        if (i == 0 || t_min > t)
            t_min = t;
    }
    printf("naive: %.3fms\n", t_min * 1000.0 / CLOCKS_PER_SEC);

    initialize_matrix(mat);
    advanced_transpose(mat);
    if (check_transpose_matrix(mat)) {
        printf("advanced_transpose failed!\n");
        return 1;
    }
    /* benchmark advanced algorithm */
    t_min = 0;
    for (int i = 0; i < 100; i++) {
        clock_t t = clock();
        advanced_transpose(mat);
        t = clock() - t;
        if (i == 0 || t_min > t)
            t_min = t;
    }
    printf("advanced: %.3fms\n", t_min * 1000.0 / CLOCKS_PER_SEC);

    return 0;
}

Output on my 5 year old macbook:

naive: 7.299ms
advanced: 1.157ms