×

Gauss and the history of the fast Fourier transform. (English) Zbl 0577.01027

The fast Fourier transform algorithm as a means of calculating the discrete Fourier transform was published in 1965 by J. W. Cooley and J. W. Tukey in the paper ”An algorithm for the machine calculation of complex Fourier series” [Math. Comput. 19, 297-301 (1965; Zbl 0127.090)]. It is considered to be a turning point in digital signal processing and in certain areas of numerical analysis. After its publication, some similar algorithms were discovered in older literature of the 20th century, until in 1977 H. H. Goldstine, in his ”History of numerical analysis from the 16th through the 19th century” (1977; Zbl 0402.01005), attributed an algorithm of this kind to C. F. Gauss. This caused the authors to trace the history of Fourier series coefficient calculation back into the 18th and 19th centuries. Their findings are summarized in the following paragraph (p. 272); ”This investigation has once again demonstrated the virtuosity of Carl Friedrich Gauss. In addition, it has shown how certain problems can be timeless, but that their solution can be rediscovered again and again. Burkhardt pointed out this algorithm in 1904 and Goldstine suggested the connection between Gauss and the FFT in 1977, but both of these went largely unnoticed, presumably because they were published in books dealing primarily with history. It was shown that various attempts at efficient algorithms were used in Great Britain and elsewhere in the 19th century, but were unrelated to the work of Gauss and were, in fact, not as general or well- formulated as Gauss’ work. Almost one hundred years passed between the publication of Gauss’ algorithm and the modern rediscovery of this approach by Cooley and Tukey”.
Reviewer: C.J.Scriba

MSC:

01A55 History of mathematics in the 19th century
01A60 History of mathematics in the 20th century
42-03 History of harmonic analysis on Euclidean spaces

Biographic References:

Gauss, C. F.
PDFBibTeX XMLCite
Full Text: DOI

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. · Zbl 0127.09002
[2] E. O. Brigham, The Fast Fourier Transform. Englewood, NJ: Prentice-Hall, Inc., 1974. · Zbl 0375.65052
[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. · Zbl 0086.12403
[4] P. Rudnick, ?Note on the Calculation of Fourier Series,? Math. Comput., Vol. 20, no. 3, pp. 429-430, Jul. 1966. · Zbl 0141.33705 · doi:10.1090/S0025-5718-66-99926-1
[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. · Zbl 0063.01036 · doi:10.1016/S0016-0032(42)90767-1
[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. · doi:10.1109/TAU.1967.1161903
[7] C. Runge, ?Über die Zerlegung empirisch gegebener Periodischer Funktionen in Sinuswellen,? Z. Math. Phys., Vol. 48, pp. 443-456, 1903. · JFM 34.0292.01
[8] C. Runge, ?Über die Zerlegung einer empirischen Funktion in Sinuswellen,? Z. Math. Phys., Vol. 52, pp. 117-123, 1905. · JFM 36.0333.01
[9] H. H. Goldstine, A History of Numerical Analysis from the 16th Through the 19th Century. Berlin, Heidelberg, and New York: Springer-Verlag, 1977. · Zbl 0402.01005
[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.
[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.
[13] L. H. Thomas, ?Using a computer to Solve Problem in Physics,? in Applications of Digital Computers, Boston: Ginn, 1963.
[14] S. Winograd, ?On Computing the Discrete Fourier Transform,? Proc. Nat. Acad. Sci. USA, Vol. 73, no. 4, pp. 1005-1006, Apr. 1976. · Zbl 0323.65050 · doi:10.1073/pnas.73.4.1005
[15] C. Runge & H. König, ?Vorlesungen über Numerisches Rechnen,? Die Grundlehren der Mathematischen Wissenschaften, Vol. 11, pp. 211-237, Berlin: Julius Springer, 1924. · JFM 50.0361.05
[16] K. Stumpff, Tafeln und Aufgaben zur Harmonischen Analyse und Periodogramm-rechnung. Berlin: Julius Springer, 1939. · JFM 65.0542.03
[17] E. T. Whittaker & G. Robinson, The Calculus of Observations. London: Blackie and Sons, Limited, 1924. · JFM 50.0348.04
[18] S. P. Thompson, ?A New Method of Approximate Harmonic Analysis by Selected Ordinates,? Proc. Phys. Soc. London, Vol. 23, pp. 334-343, 1911. · doi:10.1088/1478-7814/23/1/332
[19] S. P. Thompson, ?Note on a Rapid Method of Harmonic Analysis,? Proc. Phys. Soc. London, Vol. 19, pp. 443-453, 1904. · doi:10.1088/1478-7814/19/1/337
[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.
[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. · JFM 19.0243.01 · doi:10.1098/rspl.1887.0016
[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.
[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.
[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.
[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.
[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.
[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.
[30] J. D. Markel, ?FFT Pruning,? IEEE Trans. Audio Electroacoust., Vol. AU-19, no. 4, pp. 305-311, Dec. 1971. · doi:10.1109/TAU.1971.1162205
[31] L. Euler, Introductio in Analysin Infinitorum. Lausanne: Marc-Michel Bousquet et Comp., 1748. Reprinted in Leonhardi Euleri Opera Omnia, Series I, Volume 8.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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. · JFM 45.0374.02
[42] G. W. Dunnington, Carl Friedrich Gauss: Titan of Science. New York: Exposition Press, 1955. · Zbl 0067.24602
[43] R. N. Bracewell, The Fourier Transform and Its Applications. New York: McGraw-Hill, 1978. · Zbl 0502.42001
[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. · Zbl 0384.65066 · doi:10.1109/TASSP.1977.1162938
[45] U. C. Merzbach, Carl Friedrich Gauss: A Bibliography. Wilmington, DE: Scholarly Resources Inc., 1984.
[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.
[47] J. Herivel, Joseph Fourier: The Man and the Physicist. Oxford: Clarendon Press, 1975.
[48] L. L. Hope, ?A Fast Gaussian Method for Fourier Transform Evaluation,? Proc. IEEE, Vol. 63, no. 9, pp. 1353-1354, Sep. 1975. · doi:10.1109/PROC.1975.9942
[49] I. J. Good, ?Inversion of the Discrete Gauss Transform,? Applic. Anal., Vol. 9, no. 3 pp. 205-218, Oct. 1979. · Zbl 0452.65016 · doi:10.1080/00036817908839268
[50] T. S. Huang, ?How the Fast Fourier Transform Got Its Name,? Computer, Vol. 4, no. 3, p. 15, May?Jun. 1971. · Zbl 05331796 · doi:10.1109/C-M.1971.216789
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.