## FFT - gauss and fourier

### FFT - gauss and fourier

Did this happen after fourier discovered fourier transform ?

Or did gauss discover  "fourier theorem" but did not publish ?

( I find both were contemporaries. )

thanks
shankar

### FFT - gauss and fourier

i heard it was Cooley and Tukey.

J.W. Cooley and J.W. Tukey, "An algorithm for machine calculation of complex
Fourier series,"  Mathematical Computation, 19 (1965), 297-301.

http://eamusic.dartmouth.edu/~book/MATCpages/chap.3/chap3.pops/3.4.po...
tml

Quote:> Did this happen after fourier discovered fourier transform ?

Gauss observed that you could break up the calculation of the Discrete
Fourier Transform into two parts, making it more manageable.  but taking
that idea far enough to the Radix-2 FFT to reduce the complexity to
O(n*log2(N)) was Cooley's and Tukey's idea.

Quote:> Or did gauss discover  "fourier theorem" but did not publish ?

> ( I find both were contemporaries. )

i think that Gauss was on the committee that originally rejected Fourier's
discovery because it lacked proof.  indeed Fourier did not show that the
Fourier Series actually did add up to the original periodic function (except
where there are discontinuities) but that *if* it did, the coefficients had
to be as Fourier suggested.

r b-j

### FFT - gauss and fourier

>Gauss observed that you could break up the calculation of the Discrete
>Fourier Transform into two parts, making it more manageable.  but taking
>that idea far enough to the Radix-2 FFT to reduce the complexity to
>O(n*log2(N)) was Cooley's and Tukey's idea.

According to Cooley himself (Cooley, Lewis and Welch, "Historical
notes on the fast Fourier transform," IEEE Trans. Audio and
Electroacoustics, June 1967), Runge and Konig in 1924 had described
Lanczos in 1942.  The Cooley-Tukey FFT algorithm was a generalized
version of the Runge-Konig idea in that it could also be used when
N was composite but not necessarily a power of 2.

--
.-.     .-.     .-.     .-.     .-.     .-.     .-.
/ D \ I / L \ I / P \   / S \ A / R \ W / A \ T / E \
`-'     `-'     `-'     `-'     `-'     `-'

### FFT - gauss and fourier

How did gauss become interested in sampled-domain Fourier transform ?

Did he understand its relation to analog Fourier transform ?
--
Posted via http://web2news.com the faster web2news on the web
To contact in private, remove nno9spp4a+2mm

### FFT - gauss and fourier

> How did gauss become interested in sampled-domain Fourier transform ?

> Did he understand its relation to analog Fourier transform ?
> --
> Posted via http://web2news.com the faster web2news on the web
> To contact in private, remove nno9spp4a+2mm

That's a matter of practicality. We plot curves by measuring or
calculating an ordinate for each of several values of abscissa, laying
down the points and then connecting them by eye, with a French curve, a
limber batten, a spline, or what have you. If you want to express such a
curve as a series of sines and cosine pairs, you will certainly not try
to calculate an infinite number of them. Truncating the frequencies is
the same as making the "curve" a set of discrete points. But then, I
guess you knew that.

Jerry
--
Engineering is the art of making what you want from things you can get.

### FFT - gauss and fourier

>> How did gauss become interested in sampled-domain Fourier
>> transform ?

>> Did he understand its relation to analog Fourier transform ?
>That's a matter of practicality. We plot curves by measuring or
>calculating an ordinate for each of several values of abscissa, laying
>down the points and then connecting them by eye, with a French curve, a
>limber batten, a spline, or what have you. If you want to express such
a
>curve as a series of sines and cosine pairs, you will certainly not try
>to calculate an infinite number of them. Truncating the frequencies is
>the same as making the "curve" a set of discrete points. But then, I
>guess you knew that.
>Jerry

IIRC, the "curve" that Gauss was trying to "fit" was the orbit of
a planet.  Hopefully someone else can name the planet and give more
detail.

fourierr at fastermail dot com
--
Posted via http://web2news.com the faster web2news on the web

### FFT - gauss and fourier

> Did this happen after fourier discovered fourier transform ?

> Or did gauss discover  "fourier theorem" but did not publish ?

> ( I find both were contemporaries. )

>                 thanks
>                      shankar

Most probably  the name  "FFT" is not coined by Gauss(1777-1855). His
works on orbit are concentrated arround 1801. He published the famous
number theory book "Disquisitioues Arithmeticae" in the same year. The
efficient interpolation on the orbits of asteroid(CERES!)on which FFT
is related is arround that time(Logically I think!). Fourier published
his work on heat propagation arround 1807 which is later known to his
name.

Hence Gauss's FFT  may not be related to Fourier's work.!!

So I doubt any of your above speculations!!

Secondly, J.W.Cooley(Tukey!) in his "The re-discovery of the fast
fouier transform algorithm",1987,PP33-35 did not avoid Gauss's
original work. But Gauss's purpose was different from Tukey/Cooley.
Nobody denies that DSP lies in the 17-19th century rich mathematics.
We should not also deny  classic intutive work by the two scientists
which revolutioned DSP in a bigger way.

Regards,
Santosh

### FFT - gauss and fourier

> Did this happen after fourier discovered fourier transform ?

> Or did gauss discover  "fourier theorem" but did not publish ?

> ( I find both were contemporaries. )

>                 thanks
>                      shankar

Cooley and Tukey introduced the FFT in the paper

Cooley, J. W. and Tukey, O. W. "An Algorithm for the Machine
Calculation of Complex Fourier Series." Math. Comput. 19, 297-301,
1965.

which is the most-cited paper of all time.

Later, someone noticed that Gauss, "Mr. Few-But-Ripe", had worked out
the same algorithm but did not publish it.  Credit really belongs to
Cooley and Tukey because they launched the FFT revolution.

Fourier himself did not find the Fast Fourier Transform.  Fourier
found Fourier series when he was studying the conduction of heat.
Fourier used to sit in his overheated room wrapped in layers of
clothing.

### FFT - gauss and fourier

>i heard it was Cooley and Tukey.
>J.W. Cooley and J.W. Tukey, "An algorithm for machine calculation of complex
>Fourier series,"  Mathematical Computation, 19 (1965), 297-301.
>http://eamusic.dartmouth.edu/~book/MATCpages/chap.3/chap3.pops/3.4.po...
>tml
>> Did this happen after fourier discovered fourier transform ?
>Gauss observed that you could break up the calculation of the Discrete
>Fourier Transform into two parts, making it more manageable.  but taking
>that idea far enough to the Radix-2 FFT to reduce the complexity to
>O(n*log2(N)) was Cooley's and Tukey's idea.

Cooley and Tukey came up with this, not knowing what Gauss had
done.  In fact, it was after many papers had been written using
more general decompositions than powers of 2 that the paper of
Gauss was found and attached to this.
--
This address is for information only.  I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Deptartment of Statistics, Purdue University

### FFT - gauss and fourier

>>> Gauss observed that you could break up the calculation of the Discrete
>>> Fourier Transform into two parts, making it more manageable.  but taking
>>> that idea far enough to the Radix-2 FFT to reduce the complexity to
>>> O(n*log2(N)) was Cooley's and Tukey's idea.

>> According to Cooley himself (Cooley, Lewis and Welch, "Historical
>> notes on the fast Fourier transform," IEEE Trans. Audio and
>> Electroacoustics, June 1967), Runge and Konig in 1924 had described
>> the radix-2 FFT, and this had been implemented by Danielson and
>> Lanczos in 1942.  The Cooley-Tukey FFT algorithm was a generalized
>> version of the Runge-Konig idea in that it could also be used when
>> N was composite but not necessarily a power of 2.

> Actually, you're all a little bit off.

well, coming from Mr. Fastest Friggin' FT in the West (wait until he hooks
up with Comrade Igor in the East at high noon), i will take this as
authoritative.

r b-j

### FFT - gauss and fourier

> Most probably  the name  "FFT" is not coined by Gauss(1777-1855). His
> works on orbit are concentrated arround 1801.

(1805 is considered the likely date for his FFT work, in the
references I've seen.)

Quote:> He published the famous
> number theory book "Disquisitioues Arithmeticae" in the same year. The
> efficient interpolation on the orbits of asteroid(CERES!)on which FFT
> is related is arround that time(Logically I think!).

Are you sure it's Ceres?

In his notes, Gauss analyzes two examples.  The first, a 12-point DFT
by radix-3 DIT, is of the declination vs. ascension angles of the
asteroid Pallas .  In the second example, he analyzes the path of
the asteroid Juno (what he calls "the new planet Juno:" "aequatio
centri pro novo planeta Iunone") via a radix-6 DIT decomposition of an
18-point DFT.

The only other data I can find in his FFT work ("Theoria
interpolationis methodo novo tractata") is on the sun and moon ("solis
et luna"), but he looks at this in the sections before developing the
FFT.

(My high-school Latin teacher would be so happy to read this
discussion...although Gauss' Latin is a bastardized form called
"neo-Latin.")

Cordially,
Steven G. Johnson

 "In commercio literario a clar. barone de Zach edito, vol. X p.
188 invenitur tabula, limitem borealem et australem zodiaci Palladis
exhibens." = "[In such-and-such reference] you find a table exhibiting
the northern and southern limits of the path [zodiac] of Pallas."
(This is followed by a 12-point excerpt from the table, which he
proceeds to analyze.)

### FFT - gauss and fourier

> In the second example, he analyzes the path of
> the asteroid Juno (what he calls "the new planet Juno:" "aequatio
> centri pro novo planeta Iunone") via a radix-6 DIT decomposition of an
> 18-point DFT.

Correction: a radix-6 DIT decomposition of a 36-point DFT.

### FFT - gauss and fourier

>>Gauss observed that you could break up the calculation of the Discrete
>>Fourier Transform into two parts, making it more manageable.  but taking
>>that idea far enough to the Radix-2 FFT to reduce the complexity to
>>O(n*log2(N)) was Cooley's and Tukey's idea.

> According to Cooley himself (Cooley, Lewis and Welch, "Historical
> notes on the fast Fourier transform," IEEE Trans. Audio and
> Electroacoustics, June 1967), Runge and Konig in 1924 had described
> the radix-2 FFT, and this had been implemented by Danielson and
> Lanczos in 1942.  The Cooley-Tukey FFT algorithm was a generalized
> version of the Runge-Konig idea in that it could also be used when
> N was composite but not necessarily a power of 2.

What exactly does "implemented" imply in this context? Was it some kind
electromechanical affair? A real Babbage style FFT box sounds kind of fun.

Regards,
Steve

### FFT - gauss and fourier

Quote:>  "In commercio literario a clar. barone de Zach edito, vol. X p.
> 188 invenitur tabula, limitem borealem et australem zodiaci Palladis
> exhibens." = "[In such-and-such reference] you find a table exhibiting
> the northern and southern limits of the path [zodiac] of Pallas."
> (This is followed by a 12-point excerpt from the table, which he
> proceeds to analyze.)

Ahem, for the *retentive: "invenitur tabula" is "a table is
found," not "you find a table" ("invenis tabulam," if I remember
correctly).  My Latin is a bit rusty.  =)

Hi,

When a solution for a set of equations must be found, Gauss reduction
can be used.  Where can I find an algorithm that explains the reduction
process?

I have implemented my own algorithm in Matlab where the elements of the
matrix is manipulated to be in an upper triangular form, and the
equations solved from there.  I have only one question, in my first or
second year's maths, we were taught that the first element of the matrix
have to be one (by dividing the whole row with the first element).  Is
this necesarry?

Thanks,
Jaco