Row-Column Method:

Computation of the 2D-FFT, using classic row-column method is based on either of the basic decompositions:

a.

${\bf Y} = [I_N \otimes F_M][F_N \otimes I_M]~{\bf X}$
which first computes Fourier transforms of columns followed by transforms of rows,

b.

${\bf Y} = [F_N \otimes I_M][I_N \otimes F_M]~{\bf X}$,
which performs transformation on rows followed by that of columns.

In both forms, for architectures that doesn't have shared memory, data matrix X is not residing at a single processor's memory, and it is inevitable to transpose the data twice, in one or another form, which involves data communication among processors' memories. Matrix transpose of a $M \times N$ matrix A can be represented using permuations: ${\bf A}^t = P(MN,M)~{\bf A}$. Hence, for decompositions (a) and (b), matrix transposes occur at different stages as:

$${\bf Y} = [I_N \otimes F_M]~P(MN,N)~[I_M \otimes F_N]~P(MN,M)~{\bf X}$$

and

$${\bf Y} = P(MN,N)~[I_M \otimes F_N]~P(MN,M)~[I_N \otimes F_M]~{\bf X},$$

respectively. Note that in the above equations, sequence of operations to be performed are read from right to left. The choice method depends upon the machine architecture and initial structure of data matrix X. Structure of the available data varies with application which would be a permutation, $P_{in}$, of original matrix X,where $P_{in}$ stands for input permutation. If the requirement has to meet the transformed data to be in the same structure of the original data matrix, then input matrix would be ${\bf X_1} = P_{in}~{\bf X}$ and output matrix wouldbe ${\bf Y_1} = P_{in}~{\bf Y}$. In this case, methods (a) and (b) can be written as:

$${\bf Y_1} = P_{in}~[I_N \otimes F_M]~P(MN,N)~[I_M \otimes F_N]~[P(MN,M)~P_{in}^{ -1}]~{\bf X_1}$$

and

$${\bf Y_1} = [P_{in}~P(MN,N)]~[I_M \otimes F_N]~P(MN,M)~[I_N \otimes F_M]~P_{in}^ {-1}~{\bf X_1}.$$