# Who pioneered the use of the Fast Fourier Transform (FFT) for efficient multiplication?

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.

• The Schonhage-Strassen algorithm does not make straightforward use of the FFT. The usual FFT based multiplication algorithm(geeksforgeeks.org/…) presented in algorithm introductory books is usually simpler and less efficient than the Schonhage-Strassen algorithm which I suppose came later or at around the same time as the former.
– GEP
Commented Sep 1 at 20:10
• Actually, Schönhage and Strassen in their paper (doi.org/10.1007%2FBF02242355) describe two algorithms in their paper. The first is the straightforward FFT algorithm with FFT in complex numbers, and the second is the more complicated algebraic version which is now known as Schönhage-Strassen algorithm. Commented Sep 2 at 10:53