FFT of a matrix and its square.

Question

I am doing something computationally intensive that requires that I compute the fast fourier transform of a matrix, let's say $A$, and also compute the FFT of its square, $A^2$.

I am wondering if there is some property of the FFT of $A$ that relates to the FFT of $A^2$ that would be less computationally intensive than doing two FFTs.

Answer 1

Assuming nothing about the structure of the input, you can always save yourself at last one FFT operation along the columns (or rows). Assume $\mathbf{A}\in \mathbb{C}^{M\times N}$, and let $\mathbf{R} \in \mathbb{C}^{M \times M}$ be the column transform and $\mathbf{C} \in \mathbb{C}^{N \times N}$ be the row transform. Then

$$ \begin{array}{rcl} \mathcal{F}(\mathbf{A})&=&\mathbf{RAC} \\ \mathcal{F}(\mathbf{A}^2)&=&\mathbf{RAAC} \end{array} $$

If you store $\mathbf{RA}$ (or $\mathbf{AC}$), you can then reuse it when finding $\mathcal{F}(\mathbf{A}^2)$:

tmp   = fft(A,[],1);
Afft  = fft(tmp,[],2);
A2fft = tmp * fft(A,[],2);