Question : What is Fast Fourier Transform ?
Answer : Fast Fourier Transform is widely used in many application ranging from engineering , science and mathematics. The algorithm was in 1994 described as the “most important numerical algorithm” by Gilbert strang and was included in the top 10 Algorithms of the 20th century by IEEE.
Question : What does it do ? Where is it used ?
Answer : FFT computes Fourier Transform at the speed of O (n * log N ) from O (N^2) . It is used in solving digital differential equation to algorithms for multiplication of large integers in an fast way. This fast multiplication is specially important in data mining for large data sets and especially in deep learning where we might have large weight matrix