The Fast Fourier Transform (FFT) is an efficient algorithm used in the computation of the discrete Fourier transform. While it's well-known for its applications in signal processing, it has also been employed in various other domains. One such application is multiplication.
Who pioneered the use of the Fast Fourier Transform (FFT) for efficient multiplication?
The Fast Fourier Transform became known as such with Cooley-Tukey in 1965. Its use for fast multiplication was noted very soon after:
The story here is, however, complicated in two ways. The duality between convolution and multiplication of continuous and discrete Fourier transforms was well known at the time (compare for example Steiglitz (1963)), and this is in some sense a rather obvious application of the FFT.
The other is that the history of the relationship of matrix multiplication and discrete Fourier transforms precedes Cooley-Tukey. In fact they themselves note:
Good [2] generalized these methods and gave elegant algorithms for which one class of applications is the calculation of Fourier series. In their full generality, Good's methods are applicable to certain problems in which one must multiply an $N$-vector by an $N$ X $N$ matrix which can be factored into m sparse matrices, where m is proportional to $\log N$. This results in a procedure requiring a number of operations proportional to $N \log N$ rather than $N^2$.
In other words, finding efficiency in matrix multiplication and its relationship to Fourier transform was known before the FFT. This then is further complicated by the FFT being a case of repeat (partial) rediscovery, see:
and
The algorithm based on the Fast Fourier transform is called Schonhage-Strassen algorithm for multiplication. It replaced earlier versions which (by Karatsuba and Toom-Cook) which used somewhat similar general idea, though did not explicitly refer to Fourier transform.
