pythonmatrixcache-oblivious

# Recursive Matrix Transposition in python

I am implementing a recursive approach for Matrix transposition as cache-oblivious algorithm. I have a problem when doing transpose and swap, the problem is when the matrix has odd number of columns:
1 2 3
4 5 6
7 8 9

The number 5 is in 2 smaller matrices that are created by recursive calls

2 3
5 6
&
4 5
7 8

This makes it double swap during recursive calls. I do not want to use any structure to store swapped items.

Is there a way to handle this double swapping problem?

Here is the implementation of mentioned methods.

``````class Matrix:

def __init__(self, N):
self.N = N

def transpose(self):
self._transpose(0, 0, self.N)

def _transpose(self, start_row, start_col, size):
if size == 1:
return  # Base case: do nothing for a 1x1 matrix

first_half_size = size // 2
second_half_size = size - first_half_size

self._transpose(start_row, start_col, first_half_size)
self._transpose(start_row + second_half_size, start_col + second_half_size, first_half_size)

# Transpose swap the off-diagonal quadrants
self._transpose_swap(start_row, start_col + first_half_size, start_row + first_half_size, start_col, second_half_size)

def _transpose_swap(self, start_row1, start_col1, start_row2, start_col2, size):
if size == 1:
# Base case: swap items
self.swap(start_row1, start_col1, start_row2, start_col2)
else:
first_half_size = size // 2
second_half_size = size - first_half_size

self._transpose_swap(start_row1, start_col1, start_row2, start_col2, first_half_size)
self._transpose_swap(start_row1, start_col1 + first_half_size, start_row2 + first_half_size, start_col2, second_half_size)
self._transpose_swap(start_row1 + first_half_size, start_col1, start_row2, start_col2 + first_half_size, second_half_size)
self._transpose_swap(start_row1 + second_half_size, start_col1 + second_half_size, start_row2 + second_half_size, start_col2 + second_half_size, first_half_size)
``````

Solution

• This worked. If two matrices will share a item, swap it.

``````def _transpose_swap(self, start_row1, start_col1, start_row2, start_col2, size):
if size == 1:
# Base case: swap items
self.swap(start_row1, start_col1, start_row2, start_col2)
else:
## ADDED --- Swap if two matrices share item
if size // 2 != (size+1) // 2:
self.swap(start_row1 + size // 2, start_col1 + size // 2, start_row2 + size // 2, start_col2 + size // 2)
# ---------------
first_half_size = size // 2
second_half_size = size - first_half_size

self._transpose_swap(start_row1, start_col1, start_row2, start_col2, first_half_size)
self._transpose_swap(start_row1, start_col1 + first_half_size, start_row2 + first_half_size, start_col2, second_half_size)
self._transpose_swap(start_row1 + first_half_size, start_col1, start_row2, start_col2 + first_half_size, second_half_size)
self._transpose_swap(start_row1 + second_half_size, start_col1 + second_half_size, start_row2 + second_half_size, start_col2 + second_half_size, first_half_size)
``````