I’m not sure if I understand what you are trying to do, i.e. it makes no sense to me.

I don’t understand your reduction functions, see Reducing a matrix for how to reduce a matrix.

On the subject of transposing matrices books have been written. There are many algorithms around, also parallel algorithms exist. But why do you have to transpose the matrix?

What problem are you trying to solve, how do you end up with the matrix in the first place?

Update

Wiki is an excellent starter, it sort of reanimated my knowledge on the subject.