Chapter 11.05 Fast Fourier Transform Factorized Matrix & Operation Count Part 2 of 4

Informal Development of Fourier Series (CHAPTER 11.05)

Factorized Matrix & Operation Count: Part 2 of 4

Topic Description

Using the property of the defined function W=e^{-i \frac{2 \pi}{N}}, the matrix times vector operations can be efficiently computed by the “inner” and then “outer” product (matrix times vector) operations with substantially less numbers of operation counts. For the matrix times vector (inner) product operations, it only requires 2 complex multiplications and 4 complex additions. For the matrix times vector (outer) product operations, it also only requires 2 complex multiplications and 4 complex additions. Thus, by decomposing the “matrix times vector” operations into the matrix times vector inner and outer product operations, the total number of operations involved will only be 4 complex multiplications, and 8 complex additions (instead of the usual 16 complex multiplications, and 12 complex additions). Graphical representations of matrix times vector “inner and outer” product operations. Examples for cases N=2^{2}=4, and N=2^{4}=16. Through matrix times vector “inner and outer” product operations, and through the provided example (with N=2^{4}=16), it can be demonstrated that: (i) computer memory can be efficiently utilized. (ii) Lots of computational efforts can be skipped.

All Videos for this Topic

Informal Development of Fast Fourier Transform: Part 1 of 3 [YOUTUBE 09:59]

Informal Development of Fast Fourier Transform: Part 2 of 3 [YOUTUBE 12:39]

Informal Development of Fast Fourier Transform: Part 3 of 3 [YOUTUBE 09:46]

Fast Fourier Transform: Factorized Matrix & Operation Count: Part 1 of 4 [YOUTUBE 14:08]

Fast Fourier Transform: Factorized Matrix & Operation Count: Part 2 of 4 [YOUTUBE 14:48]

Fast Fourier Transform: Factorized Matrix & Operation Count: Part 3 of 4 [YOUTUBE 13:45]

Fast Fourier Transform: Factorized Matrix & Operation Count: Part 4 of 4 [YOUTUBE 11:49]

Fast Fourier Transform: Companion Node Observation: Part 1 of 3 [YOUTUBE 11:22]

Fast Fourier Transform: Companion Node Observation: Part 2 of 3 [YOUTUBE 12:56]

Fast Fourier Transform: Companion Node Observation: Part 3 of 3 [YOUTUBE 09:01]

Fast Fourier Transform: Determination of W^P: Part 1 of 4 [YOUTUBE 13:34]

Fast Fourier Transform: Determination of W^P: Part 2 of 4 [YOUTUBE 09:31]

Fast Fourier Transform: Determination of W^P: Part 3 of 4 [YOUTUBE 07:36]

Fast Fourier Transform: Determination of W^P: Part 4 of 4 [YOUTUBE 09:41]

Fast Fourier Transform: Unscrambling the FFT: Determination of W^P: Part 1 of 3 [YOUTUBE 15:07]

Fast Fourier Transform: Unscrambling the FFT: Determination of W^P: Part 2 of 3 [YOUTUBE 15:14]

Fast Fourier Transform: Unscrambling the FFT: Determination of W^P: Part 3 of 3 [YOUTUBE 14:32]

Complete Resources

Get in one place the following: Development of Fast Fourier Transform