Rearranging Matrix elements

[pietro_vinettigmail_]

Hi all,

i need to perform a 2D FFT on a matrix u(i,j). Unfortunately, in my model FFT has a symmetric summation from -N to N, while the MKL FFT routine has a biased summation (from 0 to 2N). Hence, I need to rearrange the input matrix, swapping sub-bocks (quadrants), in order to achieve the correctposition for u elements.

At the moment I implemented a code with for cycles to rearrangeu-elements and I also need a temp matrix to store them. But, I think that this is not the best way to implement the manipulation and I'm wondering if there is a more effective way to do it, maybe exploiting MKL functions or a compiler directive..

Does anyone has any clue about it?

Thanks,

Pietro

[Dmitry_B_Intel]

Hi Pietro,
You could preprocess the data before FFT to get the result arranged as you need. The preprocessing is multiplication by twiddle factors that you can derive by using the definition of FFT (you can find the formula in the MKL Reference Manual). For example, 1D FFT of size 2N+1 is defined as

y = sum(i=0,2N) x*w^(i*k) where k=0,2N

If I understand you correctly, you need to map y for k=0,2N to y[k'] for k'=-N,N.Substituting k'=k-N into the formula above yields:

y[k'] = sum(i=0,2N) x'*w^(i*k), where x' = x*w^(-i*N).

Similar processing can be done for 2D data.
I hope this idea might be helpful to you.

Thanks,
Dima

[pietro_vinettigmail_]

Thanks Dima for your answer. Let me exploit your competence once again.

I have considered to pre-process data in order to get the correct formula. But my conclusion is that it does not improve performance of my code. My goal is to optimize at the most my code.

Hence,if I well understand your strategy and correctly implement it,pre-procesing leads to use a matrix-matrix multiplication (u(i,j) matrix and the exponential matrix of corrective terms, say ExpMat(i,j)). The fast Mat-Mat multiplication of MKL performs for sure better than a double for cycle but I still need a second matrix, and moreover I need a double indices FOR cycle to initialize the Exp(i,j) values.

So pre-processing yelds: 1 more matrix ExpMat(i,j), 1 MMM, 1 Double indices FOR cycle.
While re-arrangment needs: 1 more matrix TempMat(i,j), 1 double indices FOR cycle.

Do you agree with me ordo you have in mind a better way to implement the pre-processing, that I couldn't see?

Thanks again,

Pietro

[Dmitry_B_Intel]

Hi Pietro,

First of all, the preprocessing doesn't refer to matrix-matrix-multiply. It is element-wise multiplication of two matrices, that is O(n^2) operation, not O(n^3).

Preprocessing adds computations, but it might happen that the opposite computation is done at the other stages of your model, so that if merged they may cancel each other.

Preprocessing may have, depending on data size, an advantage over rearrangement because it has more uniform memory access. For fast computation of the ExpMat you might consider using VML functions from MKL.

Thanks,
Dima

[pietro_vinettigmail_]

Thanks Dima.

It was an overwiev....you're completely right computational trend is lower than I was considering and rearrangmentprovides a lot ofcache misses that make the code perform worse.

Bye,

Pietro