Here's the name Row-Column Decomposition.

First, we take one dimension of the FFTs of the

rows, followed by one one dimension of the FFTs columns.

So let's see how many computations we need of this Row-Column

Decomposition if I direct the compute the one dimension the FFTs.

So what we've done is to first take N1 and 2.1dimensional

FFTs and if again directly computed I need N2 squared multiplications.

And then we take N2 and N 1.0

DFTs, and for that I need N1 squared multiplications.

This is clearly equal to this.

[BLANK_AUDIO]

So again for N1 equals N2 equals N, I

see that I need 2N to the third multiplications.

So, by just exploiting this decomposability

structure of the DFT, I see

I can bring the number of multiplications down by an order of magnitude.

I can do even better than that since I have fast Fourier transforms

to compute one dimension of the FFTs and this transfers date back to the mid60s.

So 1965, Couley [SOUND]

and Turkey were the first people to invent such

fast Fourier transforms and by enlarge they developed meant gave a big push to

the whole field of DFT since now we were able to

efficiently maybe real time in some cases, implement algorithms that were very

hard to implement before that.

So, using one of those, FFTs, I can compute them N1.1

dimensional DFT by using N 2 over 2, locg 2, N2 multiplications.

And then for computing the n1 point

DFTs I need n1 over 2 [SOUND] log n1.

And this is clearly equal to n1 n2 over 2 [SOUND] log n1 n2.