Discrete Fourier transform in two dimensions

To compute the discrete Fourier transform of a two-dimensional array, first compute the one-dimensional discrete Fourier transform of each row, replacing the contents of the row with the result, and then do the same for the columns. ¹

TODO: Can this be generalized to higher dimensions?

Problems

• Figurine Figures
• Just A Few More Triangles!
• A+B Problem
• Tile Cutting
• Another Fibonacci
• Cipher Message 3
• Matchings
• Fuzzy Search
• K-Inversions
• Power sets of power sets

See also

• Number theoretic transform
• Fast Hadamard transform
• Divide and conquer

External links

• Integer and polynomial multiplication
• Avoiding FFT precision issues (Russian)
• FFT and overflows
• MIPT fall training camp 2013, FFT contest
• Polynomial Algorithms