Question 5.E.8.7: Let a and b be n ×1 vectors, where n is a power of 2 (a) Sho......
Let a and b be n ×1 vectors, where n is a power of 2.
(a) Show that the number of multiplications required to form a \odot b by using the definition of convolution is n².
Hint: 1 + 2 + · · · + k = k(k + 1)/2.
(b) Show that the number of multiplications required to form a \odot b by using the FFT in conjunction with the convolution theorem is 3n log_2 n + 7n. Sketch a graph of 3n log_2 n (the 7n factor is dropped because it is not significant), and compare it with the graph of n² to illustrate why the FFT in conjunction with the convolution theorem provides such a big advantage.
(a) The number of multiplications required by the definition is
1 + 2 + · · · + (n − 1) + n + (n − 1) + · · · + 2 + 1
= 2 (1 + 2 + · · · + (n − 1)) + n
= (n − 1)n + n = n².
(b) In the formula a_{n×1} \odot b_{n×1} = F^{−1}_{2n}[(F_{2n}\hat{a}) × (F_{2n}\hat{b})], using the FFT to compute F_{2n}\hat{a} and F_{2n}\hat{b} requires (2n/2) log_2 2n = n(1 + log_2 n) multiplications for each term, and an additional 2n multiplications are needed to form the product (F_{2n}\hat{a}) × (F_{2n}\hat{b}). Using the FFT in conjunction with the procedure described in Example 5.8.2 to apply F^{−1} to (F_{2n}\hat{a}) × (F_{2n}\hat{b}) requires another (2n/2) log_2 2n = n(1 + log_2 n) multiplications to compute \overline{F_{2n}\overline{x}} followed by 2n more multiplications to produce (1/2n)\overline{F_{2n}\overline{x}} = F^{−1}_{2n}x. Therefore, the total count is 3n(1 + log_2 n) + 4n = 3n log_2 n + 7n.