1 [made Community Wiki]

Gauss essentially invented the Fast Fourier Transform in 1805, but the importance of his work was not understood for a century.

"A 1965 paper by John Tukey and John Cooley [2] is generally credited as the starting point for modern usage of the FFT. However, a paper by Gauss published posthumously in 1866 [3] (and dated to 1805) contains indisputable use of the splitting technique that forms the basis of modern FFT algorithms.

"Gauss was interested in the problem of computing accurate asteroid orbits from observations of their positions. His paper contains 12 data points on the position of the asteroid Pallas, through which he wished to interpolate a trigonometric polynomial with 12 coefficients. Instead of solving the resulting 12-by-12 system of linear equations by hand, Gauss looked for a shortcut. He discovered how to separate the equations into three subproblems that were much easier to solve, and then how to recombine the solutions to obtain the desired result. The solution is equivalent to estimating the DFT of the data with an FFT algorithm."

http://www.mathworks.com/access/helpdesk/help/techdoc/math/brentm1-1.html

"Recent studies of the history of the fast Fourier transform (FFT) algorithm, going back to Gauss[1], provide an example of exactly the opposite situation. After having been published and used over a period of 150 years without being regarded as having any particular importance, the FFT was re-discovered, developed extensively, and applied on electronic computers in 1965, creating a revolutionary change in the scale and types of problems amenable to digital processes."