Reordering block matrix

Question

I have a multi-level indexed square matrix, that needs to be reordered. Say I have a two-level indexing system x and y and the square matrix M has the shape (len(x)*len(y), len(x)*len(y)). M is sorted by the x index and I want to transform it to be sorted by the y index. Here is an example to contruct an arbitary square matrix M:

import numpy as np
nx = 4  # equal to len(x), arbitary
ny = 3  # equal to len(y), arbitary
A=np.ones(ny*ny).reshape(ny,ny) #arbitary
B=np.ones(ny*ny).reshape(ny,ny)*2 #arbitary
C=np.ones(ny*ny).reshape(ny,ny)*3 #arbitary
D=np.ones(ny*ny).reshape(ny,ny)*4 #arbitary
E=np.arange(ny*ny).reshape(ny,ny) #arbitary
M = np.block([[A, np.zeros((ny,ny)), E, np.zeros((ny,ny))],
              [np.zeros((ny,ny)), B, np.zeros((ny,ny)),np.zeros((ny,ny))], 
              [np.zeros((ny,ny)),np.zeros((ny,ny)),C, np.zeros((ny,ny))],
              [np.zeros((ny,ny)), np.zeros((ny,ny)), np.zeros((ny,ny)), D]])

and the resulting matrix M may look like this

array([[1., 1., 1., 0., 0., 0., 0., 1., 2., 0., 0., 0.],
       [1., 1., 1., 0., 0., 0., 3., 4., 5., 0., 0., 0.],
       [1., 1., 1., 0., 0., 0., 6., 7., 8., 0., 0., 0.],
       [0., 0., 0., 2., 2., 2., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 2., 2., 2., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 2., 2., 2., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 3., 3., 3., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 3., 3., 3., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 3., 3., 3., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 4., 4., 4.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 4., 4., 4.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 4., 4., 4.]])

Now I want to transform the M into M_transformed that looks like this

array([[1., 0., 0., 0., 1., 0., 1., 0., 1., 0., 2., 0.],
       [0., 2., 0., 0., 0., 2., 0., 0., 0., 2., 0., 0.],
       [0., 0., 3., 0., 0., 0., 3., 0., 0., 0., 3., 0.],
       [0., 0., 0., 4., 0., 0., 0., 4., 0., 0., 0., 4.],
       [1., 0., 3., 0., 1., 0., 4., 0., 1., 0., 5., 0.],
       [0., 2., 0., 0., 0., 2., 0., 0., 0., 2., 0., 0.],
       [0., 0., 3., 0., 0., 0., 3., 0., 0., 0., 3., 0.],
       [0., 0., 0., 4., 0., 0., 0., 4., 0., 0., 0., 4.],
       [1., 0., 6., 0., 1., 0., 7., 0., 1., 0., 8., 0.],
       [0., 2., 0., 0., 0., 2., 0., 0., 0., 2., 0., 0.],
       [0., 0., 3., 0., 0., 0., 3., 0., 0., 0., 3., 0.],
       [0., 0., 0., 4., 0., 0., 0., 4., 0., 0., 0., 4.]])

I use a very elementary, 4 layers of for loops to solve this problem and I believe there must be a more straight forward way (like a library) to solve this issue, as the matrix M can grow very large depending on the length of x and y (nx and ny)

M_transformed = np.zeros(M.shape)

for i in range(nx):
    for j in range(nx):
        for k in range(ny):
            for l in range(ny):
                M_transformed[k * nx + i,l * nx + j] = M[i * ny + k, j * ny + l]

I haven't tried to follow all of your logic, but sticking with a 2d array like this may be making things harder than they need to be. If the array was 4d, which could be thought of as a 2d array of 2d blocks, reordering the subblocks is easier. And for some reorderings, a transpose (or axis swap) might be in order. — hpaulj, Oct 30 '20 at 19:56

score 0 · Accepted Answer · answered Oct 30 '20 at 22:14

I did it with no calculations, just borrowing some ideas from how to do maxpooling and experimenting a lot with swaps of axes.

I came to solution with this plan:

And this is my solution:

w = (3, 3)
initial_shape = M.shape
M = M.reshape((M.shape[0]//w[0], w[0], M.shape[1]//w[1], w[1]))
M = M.swapaxes(0, 1)
M = M.swapaxes(2, 3)
M = M.reshape(initial_shape)

Reordering block matrix

1 Answers1