[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Gauss and the history of the fast Fourier transform

  • Published:
Archive for History of Exact Sciences Aims and scope Submit manuscript

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

References

  1. J. W. Cooley & J. W. Tukey, “An Algorithm for the Machine Calculation of Complex Fourier Series,” Math. Comput., Vol. 19, no. 2, pp. 297–301, Reprinted in Digital Signal Processing, ed. L. R. Rabiner & C. M. Rader, pp. 223–227, New York: IEEE Press, 1972, Apr. 1965.

    Google Scholar 

  2. E. O. Brigham, The Fast Fourier Transform. Englewood, NJ: Prentice-Hall, Inc., 1974.

    Google Scholar 

  3. I. J. Good, “The Interaction Algorithm and Practical Fourier Analysis,” J. R. Statist. Soc. B, Vol. 20, no. 2, pp. 361–372, 1958, Addendum in J. R. Statist. Soc. B, vol. 22, no. 2, pp. 372–375, 1960.

    Google Scholar 

  4. P. Rudnick, “Note on the Calculation of Fourier Series,” Math. Comput., Vol. 20, no. 3, pp. 429–430, Jul. 1966.

    Google Scholar 

  5. G. C. Danielson & C. Lanczos, “Some Improvements in Practical Fourier Analysis and Their Application to X-ray Scattering From Liquids,” J. Franklin Inst., Vol. 233, no. 4 and 5, pp. 365–380 and 435–452, Apr. and May 1942.

    Google Scholar 

  6. J. W. Cooley, P. A. W. Lewis & P. D. Welch, “Historical Notes on the Fast Fourier Transform,” IEEE Trans. Audio Electroacoust., Vol. AU-15, no. 2, pp. 76–79, Jun. 1967, Reprinted in Proc. IEEE, vol. 55, no. 10, pp. 1675–1677, Oct. 1967. Also reprinted in Digital Signal Processing, ed. L. R. Rabiner & C. M. Rader, pp. 260–262, New York: IEEE Press 1972.

    Google Scholar 

  7. C. Runge, “Über die Zerlegung empirisch gegebener Periodischer Funktionen in Sinuswellen,” Z. Math. Phys., Vol. 48, pp. 443–456, 1903.

    Google Scholar 

  8. C. Runge, “Über die Zerlegung einer empirischen Funktion in Sinuswellen,” Z. Math. Phys., Vol. 52, pp. 117–123, 1905.

    Google Scholar 

  9. H. H. Goldstine, A History of Numerical Analysis from the 16th Through the 19th Century. Berlin, Heidelberg, and New York: Springer-Verlag, 1977.

    Google Scholar 

  10. C. F. Gauss, “Nachlass, Theoria Interpolationis Methodo Nova Tractata,” in Carl Friedrich Gauss Werke, Band 3, Königlichen Gesellschaft der Wissenschaften: Göttingen, pp. 265–330, 1866.

    Google Scholar 

  11. H. Burkhardt, “Trigonometrische Interpolation,” in Chapter 9, Encyklopädie der Mathematischen Wissenschaften, vol. 2, part 1, 1st half, 1899–1916.

  12. M. T. Heideman & C. S. Burrus, “A Bibliography of Fast Transform and Convolution Algorithms II,” Technical Report Number 8402, Electrical Engineering Dept., Rice University, Houston, TX 77251–1892, Feb. 1984.

    Google Scholar 

  13. L. H. Thomas, “Using a computer to Solve Problem in Physics,” in Applications of Digital Computers, Boston: Ginn, 1963.

    Google Scholar 

  14. S. Winograd, “On Computing the Discrete Fourier Transform,” Proc. Nat. Acad. Sci. USA, Vol. 73, no. 4, pp. 1005–1006, Apr. 1976.

    Google Scholar 

  15. C. Runge & H. König, “Vorlesungen über Numerisches Rechnen,” Die Grundlehren der Mathematischen Wissenschaften, Vol. 11, pp. 211–237, Berlin: Julius Springer, 1924.

    Google Scholar 

  16. K. Stumpff, Tafeln und Aufgaben zur Harmonischen Analyse und Periodogramm-rechnung. Berlin: Julius Springer, 1939.

    Google Scholar 

  17. E. T. Whittaker & G. Robinson, The Calculus of Observations. London: Blackie and Sons, Limited, 1924.

    Google Scholar 

  18. S. P. Thompson, “A New Method of Approximate Harmonic Analysis by Selected Ordinates,” Proc. Phys. Soc. London, Vol. 23, pp. 334–343, 1911.

    Google Scholar 

  19. S. P. Thompson, “Note on a Rapid Method of Harmonic Analysis,” Proc. Phys. Soc. London, Vol. 19, pp. 443–453, 1904.

    Google Scholar 

  20. G. H. Darwin & J. C. Adams, “The Harmonic Analysis of Tidal Observations,” Brit. Assoc. Report, pp. 49–118, 1883, Reprinted in G. H. Darwin: Scientific Papers Volume I: Oceanic Tides and Lunar Disturbances of Gravity, pp. 1–69, Cambridge: University Press, 1907.

  21. A. Smith, Admiralty Scientific Mannal on ‘Deviations of the Compass’, 5th Edition. London: Hydrographic Office, Admiralty, 1874.

    Google Scholar 

  22. R. Strachey, “On the Computation of the Harmonic Components of a Series Representing a Phenomenon Recurring in Daily and Yearly Periods,” Proc. Roy. Soc. London, Vol. 42, no. 251, pp. 61–79, 1887.

    Google Scholar 

  23. J. D. Everett, “On a Method of Reducing Observations of Underground Temperature, With its Application to the Monthly Mean Temperatures of Underground Thermometers at the Royal Edinburgh Observatory,” Trans. Roy. Soc. Edin., Vol. 22, no. 2, pp. 429–439, 1860.

    Google Scholar 

  24. W. Thomson, “On the Reduction of Observations of Underground Temperature; With Application to Professor Forbes' Edinburgh Observations, and the Continued Carlton Hill Series,” Trans. Roy. Soc. Edin., Vol. 22, no. 2, pp. 405–427, Reprinted in Mathematical and Physical Papers, Vol. 3 of William Thomson, Lord Kelvin, pp. 261–290, London: C. J. Clay and Sons, Cambridge Univ. Press, 1890, 1860.

  25. A. Smith & E. Sabine, “Contributions to Terrestrial Magnetism No. VIII, Memorandum on Elements of Reduction,” Phil. Trans. Roy. Soc. London, Vol. 136, no. 3, pp. 347–355, 1846.

    Google Scholar 

  26. A. Smith, Instructions for the Computation of a Table of the Deviations of a Ship's Compass, From Deviations Observed on 4, 8, 16, and 32 Points, and for the Adjustment of the Table on a Change of Magnetic Latitude. London: Gt. Brit. Hydrographic Office, 1850.

    Google Scholar 

  27. A. Smith, Supplement to the Practical Rules for Ascertaining the Deviations of the Ship's Compass Caused by the Ship's Iron, Being Instructions for the Computation of a Table of the Deviation of the Ship's Compass from Observations Made on 4, 8, 16, or 32 Points (Second Edition) and a Graphic Method of Correcting the Deviations of a Ship's Compass. London: J. D. Potter, 1855.

    Google Scholar 

  28. F. Carlini, Sulla Legge Delle Variazioni Orarie del Barometro. Modena: Presso la Tipographia Camerale, 1828. Also in Società Italiana della Scienze, Rome, Memorie di Matematica e di Fisica, vol. 20, p. 198, 1828.

    Google Scholar 

  29. P. A. Hansen, Mémoire Sur la Détermination des Perturbations Absolues dans des Ellipses d'une Excentricité et d'une Inclinaison Quelconques. Paris: Bachelier, 1835.

    Google Scholar 

  30. J. D. Markel, “FFT Pruning,” IEEE Trans. Audio Electroacoust., Vol. AU-19, no. 4, pp. 305–311, Dec. 1971.

    Google Scholar 

  31. L. Euler, Introductio in Analysin Infinitorum. Lausanne: Marc-Michel Bousquet et Comp., 1748. Reprinted in Leonhardi Euleri Opera Omnia, Series I, Volume 8.

    Google Scholar 

  32. L. Euler, “Observationes Generales Circa Series Quarum Termini Secundum Sinus vel Cosinus Angulorum Multiplorum Progrediuntur,” Nova Acta Academiae Scientiarum Petropolitanae, Vol. 7, pp. 87–98, 1793, Reprinted in Leonhardi Euleri Opera Omnia, Series I, Volume 16, pp. 163–177.

    Google Scholar 

  33. L. Euler, “Methodus Facilis Inveniendi Series per Sinus Cosinusve Angulorum Multiplorum Procedentes Quarum Usus in Universa Theoria Astronomiae est Amplissimus,” Nova Acta Academiae Scientiarum Petropolitanae, Vol. 11, pp. 94–113, 1798, Reprinted in Leonhardi Euleri Opera Omnia, Series I, Volume 16, pp. 311–332.

    Google Scholar 

  34. L. Euler, “De Propagatione Pulsuum per Medium Elasticum,” Novi Commentarii academiae scientiarum Petropolitanae, Vol. 1, pp. 67–105, 1750, Reprinted in Leonhardi Euleri Opera Omnia, Series II, Volume 10, pp. 98–131.

    Google Scholar 

  35. L. Euler, “De Serierum Determinatione seu Nova Methodus Inveniendi Terminos Generales Serierum,” Novi Commentarii academiae scientiarium Petropolitanae, Vol. 3, pp. 36–85, 1753, Reprinted in Leonhardi Euleri Opera Omnia, Series I, Volume 14 pp. 463–515.

    Google Scholar 

  36. C. Truesdell, “The Rational Mechanics of Flexible or Elastic Bodies,” in Leonhardi Euleri Opera Omnia, pp. 229–234, Series II, Volume 11, Section 2, 1960.

    Google Scholar 

  37. A.-C. Clairaut, “Mémoire sur l'Orbite Apparente du Soleil Autour de la Terre, en Ayant égard aux Perturbations Produites par les Actions de la Lune et des Planètes Principales,” Mémoires de Mathématique et de Physique de l'Académie Royale des Sciences, no. 9, pp. 801–870, 1754.

  38. D. Bernoulli, “Réflexions et éclaircissemens sur les Nouvelles Vibrations des Cordes,” Mémoires de l'Académie Royale des Sciences et Belles Lettres, Berlin, 1753.

    Google Scholar 

  39. J. L. Lagrange, “Recherches sur la Nature et la Propagation du Son,” Miscellanea Taurinensia (Mélanges de Turin), Vol. I, no. I-X, pp. 1–112, 1759, Reprinted in Œuvres de Lagrange, Volume 1, ed. J. A. Serret, pp. 39–148, Paris: Gauthier-Villars, 1867.

    Google Scholar 

  40. J. L. Lagrange, “Solution de Différents Problèmes de Calcul Intégral,” Miscellanea Taurinensia (Mélanges de Turin), Vol. III, Reprinted in Œuvres de Lagrange, Volume 1, ed. J. A. Serret, pp. 469–668, Paris: Gauthier-Villars, 1867, 1762–1765.

    Google Scholar 

  41. H. Burkhardt, “Trigonometrische Reihen und Integrale (bis etwa 1850),” in Chapter 12, Encyklopädie der Mathematischen Wissenschaften, vol. 2, part 1, 2nd half, 1904–1916.

  42. G. W. Dunnington, Carl Friedrich Gauss: Titan of Science. New York: Exposition Press, 1955.

    Google Scholar 

  43. R. N. Bracewell, The Fourier Transform and Its Applications. New York: McGraw-Hill, 1978.

    Google Scholar 

  44. C. S. Burrus, “Index Mappings for Multidimensional Formulation of the DFT and Convolution,” IEEE Trans. on ASSP, Vol. ASSP-25, no. 3, pp. 239–242, Jun. 1977.

    Google Scholar 

  45. U. C. Merzbach, Carl Friedrich Gauss: A Bibliography. Wilmington, DE: Scholarly Resources Inc., 1984.

    Google Scholar 

  46. J. B. J. Fourier, Théorie Analytique de la Chaleur. Paris: F. Didot, 1822. English translation in The Analytical Theory of Heat, translated by Alexander Freeman, Cambridge: University Press, 1878.

    Google Scholar 

  47. J. Herivel, Joseph Fourier: The Man and the Physicist. Oxford: Clarendon Press, 1975.

    Google Scholar 

  48. L. L. Hope, “A Fast Gaussian Method for Fourier Transform Evaluation,” Proc. IEEE, Vol. 63, no. 9, pp. 1353–1354, Sep. 1975.

    Google Scholar 

  49. I. J. Good, “Inversion of the Discrete Gauss Transform,” Applic. Anal., Vol. 9, no. 3 pp. 205–218, Oct. 1979.

    Google Scholar 

  50. T. S. Huang, “How the Fast Fourier Transform Got Its Name,” Computer, Vol. 4, no. 3, p. 15, May–Jun. 1971.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electrical & Computer Engineering, Rice University, Houston, Texas

    Michael T. Heideman, Don H. Johnson & C. Sidney Burrus

Authors
  1. Michael T. Heideman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Don H. Johnson
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. C. Sidney Burrus
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by C. Truesdell

Rights and permissions

Reprints and permissions

About this article

Cite this article

Heideman, M.T., Johnson, D.H. & Burrus, C.S. Gauss and the history of the fast Fourier transform. Arch. Hist. Exact Sci. 34, 265–277 (1985). https://doi.org/10.1007/BF00348431

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00348431

Keywords

Search

Navigation