Why are fourier transforms so powerful?

[KimB]

I know I always thought so.

 

[K.I.L.E.R]

At OCAU people actually hijacked many threads about whether I was male or female. No one ever came to a solid conclusion.

Chalz you mentioned "fourier space", can you tell me what you meant by that?
Thanks.

 

[KimB]

When you do a Fourier transform on data, you're now in Fourier space, where instead of the array elements representing positions, they now represent frequency. Do an inverse Fourier transform, and you're back to real space.

 

[K.I.L.E.R]

So I convert a problem to fourier, then accomplish what I need to and then convert it back into real space?

When you do a Fourier transform on data, you're now in Fourier space, where instead of the array elements representing positions, they now represent frequency. Do an inverse Fourier transform, and you're back to real space.

 

[_xxx_]

oh the joy of being in EE...

Hehe

 

[StefanS]

So I convert a problem to fourier, then accomplish what I need to and then convert it back into real space?

Often a differential equation is simpler in k-Space, so as you said you transform your equation to Fourier space, solve it and then retransform the solution.

 

[K.I.L.E.R]

K-space is what exactly?

 

[[maven]]

My experience with simulating water was a very simple kernel done in 'real' space, not frequency. It perhaps is not completely accurate, but is good enough.

http://freespace.virgin.net/hugo.elias/graphics/x_water.htm has a reasonable discussion of that (its where I cribbed my code from)

And if you want to look at a version of this done on the GPU, you can take a look at my B3D Shader Competition entry...

 

[KimB]

So I convert a problem to fourier, then accomplish what I need to and then convert it back into real space?

Yes. The advantage of converting to Fourier space is that linear differential equations become ordinary equations (the derivatives evaluate trivially).

 

[drspangle]

Yes. The advantage of converting to Fourier space is that linear differential equations become ordinary equations (the derivatives evaluate trivially).

Yeah, the idea is to make an insolvable problem solvable.

/Edit

Or a more difficult one

 

[KimB]

Analytically, you mean

Any differential equation is solvable numerically.

 

[K.I.L.E.R]

Why don't you guys give me an example.

Solve this problem with fourier transforms.

A man travels 500Km on a bus. He gets trapped in a black hole which is solar massive.
What's the force he's ripped apart?

 

[drspangle]

Analytically, you mean

Any differential equation is solvable numerically.

I mean solved as in a perfect solution

 

[K.I.L.E.R]

Can you guys show me a practical example?
I am going to learn this stuff one way or another.
In my course I'm specialising in maths + programming.

 

[Rodéric]

Can you guys show me a practical example?
I am going to learn this stuff one way or another.
In my course I'm specialising in maths + programming.

If it's for water rendering see (not using FFT, but NSE) : http://www.andyc.org/lecture/viewlog.php?log=Realistic Water Rendering, by Yann L
Yann Lombard talking about that, using Navier-Stokes Equations (simplified).

[Edit : Typo]

 

[KimB]

Can you guys show me a practical example?

Sure, take an LRC circuit.

In this circuit, we have a resistor, a capacitor, and an inductor connected in series. This circuit is connected to some power supply which supplies V(t).

Now, the voltage across the resistor is simple: deltaV = IR.

The voltage across the capacitor is also simple. Since capacitance is just the ratio of charge to voltage, deltaV = qC.

Finally, we have the inductor. This circuit is a little bit different, in that it resists changes in current. So, the voltage is: deltaV = -L(dI/dt).

Now we have to consider how q in capacitance relates to the currents in the other equations. It turns out it's very simple: current is just flow of charge, so I = dq/dt.

From this, we can develop an equation. Since all of the above are in series, the total voltage drop across all three must equal the voltage of the source: V(t) = -L(d^2q/dt^2) + R(dq/dt) + C(q).

The above is an ordinary second-order differential equation, and as such if we consider the equation: -L(d^2q/dt^2) + R(dq/dt) + C(q) = 0, we know right away that the solution is complex exponentials. So, an obvious tactic is just to take q(t) = integral(dw a(w) e^iwt). This is a Fourier transform, where we can now define everything about our function q(t) instead by talking about the function a(w), which is a function of the angular frequency w.

If we make the above change, we find that we can factor out the integral, and take the time derivatives explicitly. This can be seen by virtue that since our functions are well-behaved, one can take the time derivatives inside the integral. And since integrals are linear operators, a sum of integrals is just the integral of the sum. Finally consider that the time derivative of e^(iwt) = iw e^(iwt). Thus, we have:

integral(dw a(w) ( Lw^2 + iwR + C ) e^(iwt)) = 0

Now, we want the above equation to be true for all functions a(w). The only way for this to be true is if (Lw^2 + iwR + C = 0). Here I'd like to point out that I did something a little bit different than what is usually done: I put everything in terms of the Fourier transform of the charge as a function of time. What is usually done is to put everything in terms of the Fourier transform of the current. This leads to the same result, but it's written a little bit differently:

-iwL + R + C/(iw) = 0

Finally, if we go back to the full equation, where the right hand side was V(t) to start with, and also take the Fourier transform of the right hand side, we find pretty quickly that we can express the above equation as:

(-iwL + R + C/(iw))I(w) = V(w)

...where I(w) is the Fourier transform of the current, and V(w) is the Fourier transform of the voltage. Thus, if you give me a voltage as a function of time, I can take its Fourier transform, stick it on the right hand side of the above equation, and easily find current as a function of time.

 

[K.I.L.E.R]

So basically this will allow you to construct ANY formula you need simply based on any number of variables?
What about 3+ order equations?

 

[[maven]]

... using Navier Strokes Equations (simplified).

If it was a typo, I apologize, but they're the Navier-Stokes Equations; and I simply couldn't let that stand (as we're solving them for a living).

 

[WhiningKhan]

So basically this will allow you to construct ANY formula you need simply based on any number of variables?
What about 3+ order equations?

Well...How about you sign up on a maths class on Fourier methods? Pretty much every university with maths department runs such classes. No offense, but you don't really strike to me as a fellow who would grasp the whole issue from BBS postings anyway (being the self-proclaimed "Retarded Moron" and all)...

 

[K.I.L.E.R]

I get what's being done but I don't get why it's being done only on specific problems and not all.

Well...How about you sign up on a maths class on Fourier methods? Pretty much every university with maths department runs such classes. No offense, but you don't really strike to me as a fellow who would grasp the whole issue from BBS postings anyway (being the self-proclaimed "Retarded Moron" and all)...