Transforms


By Yatir Halevi on Monday, October 15, 2001 - 05:26 pm:

What are 'Transforms' in mathematics?
(Such as Fourier Transforms, Or Laplace's)
What do they do, and what are their functions?

Thnx,
Yatir


By David Loeffler on Friday, October 19, 2001 - 08:17 pm:
The term ''transform'' is very general and I don't think it has any formal meaning.

However, these examples are all integral transforms. (In fact they are by far the most usual ones - the three my book mentions are the Laplace, the Fourier and the Mellin.) These are operations that take one function and return another.

Anyway, the general definition is that one takes a function K(x,y) of two variables, called the kernel, and defines the transform g(y) of a function f(x) by

g(y)= a b K(x,y)f(x)dx

where a and b are fixed for that transform; normally a is either 0 or -, and b is .

For example, in the Laplace transform, we take K(x,y)= e-xy , a=0, b=.

As for what they're useful for, their main use (as far as I know) is for differential equations. This is because if g(y)=L(f(x)) is the Laplace transform of f,

L(df/dx)=yg(y)-f(0)

and

L( d2 f/ dx2 )= y2 g(y)-yf(0)-f'(0)

and so on.

So if we are given a differential equation such as

f''(x)+4f(x)=sin(2x), f(0)=10, f'(0)=0

we take the Laplace transform of both sides. If L(f(x))=g(y) as before, then L( the left hand side )= y2 g(y)-yf(0)-f'(0)+4g(y)=( y2 +4)g(y)-10y

whhile L(righthand side )=L(sin2x)=2/( y2 +4) (this is from evaluating the integral- it's tedious, but not hard).

so we have g(y)=10y/( y2 +4)+2/( y2 +4 )2 .

Having found g(y), we find a table of Laplace transforms, and find that this is the Laplace transform of

f(x)=10cos2x+1/8(sin2x-2xcos2x)

which is the solution of the above equation. So this is the sort of thing Laplace transforms are good for.

David


By Yatir Halevi on Saturday, October 20, 2001 - 01:41 pm:

Hmm..Thanks, sounds pretty cool,
I've heard somewhere that they use the fourier transform to ease in the multiplication of large numbers, you know anything about that?


By David Loeffler on Saturday, October 20, 2001 - 05:24 pm:

To be honest, no.


By Yatir Halevi on Sunday, October 21, 2001 - 04:09 pm:

Anyway...Thnx


By Dan Goodman on Sunday, October 21, 2001 - 06:10 pm:

The following website might help. http://numbers.computation.free.fr/Constants/Algorithms/fft.html .


By Yatir Halevi on Monday, October 22, 2001 - 03:20 pm:

Thnx for the website.
in the website they say: "Multiplication of large numbers of n digits can be done in time O(nlog(n)) (instead of O(n2 ) with the classic algorithm) thanks to the Fast Fourier Transform (FFT)."

What is the 'O' function?, as in: O(n2 )


By Kerwin Hui on Monday, October 22, 2001 - 04:04 pm:

The 'O'-notation is one of the most frequently used notation. We write f(x)=O(g(x)) for functions f(x), g(x) with f(x)/g(x) tending to a finite limit in the appropriate limit of x. (We don't care what that limit is, it could be zero, or a million or more.... just that fact that it is a finite rather than infinite.)

Kerwin


By Dan Goodman on Monday, October 22, 2001 - 05:43 pm:

Another way of thinking about the 'O' notation which is equivalent to what Kerwin said but slightly more intuitive is this: an algorithm is O(f(n)) if there is a constant C such that the algorithm completes in less than C.f(n) steps. In other words, the algorithm takes "about f(n)" steps to complete.

FFT multiplication is good because n.log(n) is a lot less than n2 .