Is there a good way to compute indefinite integral numerically? How does FFT compare to numerical integration?

Hi all,

I want to take Foureir transform of f(t), which is F(v),

and a continuous-time Foureir transform needs to integrate from -infinity to 
+infinity.

It's too complicated, and there is no closed-form solution. So I need to 
compute the Foureir transform numerically...

How to do that? I have some past experience with FFT but now I need to renew 
my memory.

Please give me some pointers about how to convert the infinite range 
integration to finite sums in FFT?

Moreover, the Foureir transform can also be computed by numerical 
integration, what's the disadvantage and advantage of both approaches? 
Before I begin the work, I would like to hear your expert opinions and 
comments about these approaches.

Thanks a lot! 

On 18 May, 08:27, "Mike" <meathea...@gmail.com> wrote:
> Hi all,
>
> I want to take Foureir transform of f(t), which is F(v),
>
> and a continuous-time Foureir transform needs to integrate from -infinity to
> +infinity.
>
> It's too complicated, and there is no closed-form solution. So I need to
> compute the Foureir transform numerically...
>
> How to do that? I have some past experience with FFT but now I need to renew
> my memory.
>
> Please give me some pointers about how to convert the infinite range
> integration to finite sums in FFT?
>
> Moreover, the Foureir transform can also be computed by numerical
> integration, what's the disadvantage and advantage of both approaches?
> Before I begin the work, I would like to hear your expert opinions and
> comments about these approaches.
>
> Thanks a lot!

All methods of numerical integration involve making an approximation
and assuming the curve to be smooth. FFT has the advantage of being a
Log(2)N method. It is as valid as any spline method. The disadvantage
of FFT and the advantage of splines is that you don't have to have
uniform spacing of points.

As far as infinity is concerned, you need to look at your function and
decide how it behaves with large v. Are you certain BTW that the
integral is finite? If you are you need to integrate by some non
numerical method from your cut off point to infinity. At large v an
integral must either be 1/x^n or be infinite.


  - Ian Parker

As far

"Ian Parker" <ianparker2@gmail.com> wrote in message 
news:1179485500.108252.79330@w5g2000hsg.googlegroups.com...
> On 18 May, 08:27, "Mike" <meathea...@gmail.com> wrote:
>> Hi all,
>>
>> I want to take Foureir transform of f(t), which is F(v),
>>
>> and a continuous-time Foureir transform needs to integrate from -infinity 
>> to
>> +infinity.
>>
>> It's too complicated, and there is no closed-form solution. So I need to
>> compute the Foureir transform numerically...
>>
>> How to do that? I have some past experience with FFT but now I need to 
>> renew
>> my memory.
>>
>> Please give me some pointers about how to convert the infinite range
>> integration to finite sums in FFT?
>>
>> Moreover, the Foureir transform can also be computed by numerical
>> integration, what's the disadvantage and advantage of both approaches?
>> Before I begin the work, I would like to hear your expert opinions and
>> comments about these approaches.
>>
>> Thanks a lot!
>
> All methods of numerical integration involve making an approximation
> and assuming the curve to be smooth. FFT has the advantage of being a
> Log(2)N method. It is as valid as any spline method. The disadvantage
> of FFT and the advantage of splines is that you don't have to have
> uniform spacing of points.
>
> As far as infinity is concerned, you need to look at your function and
> decide how it behaves with large v. Are you certain BTW that the
> integral is finite? If you are you need to integrate by some non
> numerical method from your cut off point to infinity. At large v an
> integral must either be 1/x^n or be infinite.
>
>
>  - Ian Parker
>
> As far
>

I just don't understand in practice how people use FFT to do Foureir 
transform, because it is almost always an infinite integral. We know that if 
a signal is finite support in time domain, then it is infinite support in 
spectrum domain; vice versa. So anyway people will have to face the infinite 
support problem, no matter if they use FFT or numerical integration. How do 
they handle this nicely?

FFT is highly optimized throughout the years, but it uses uniform samplings; 
of course I can imagine over the years people invented non-uniform sampling 
FFT, but less efficient since they are less popular. But on the other hand, 
numerical integration such as Gaussian Quardrature method etc. are also 
highly optimized and they are supposed to use "smart" and "adaptive" 
sampling points. Does anybody have a comparison between them?

I am still not sure about the points you made about the infinite integral 
part. Do you mean I have to truncate at some large range, and then use other 
ways to compute tail integral?

> I want to take Foureir transform of f(t), which is F(v),

Fourier transform

> and a continuous-time Foureir transform needs to integrate from -infinity to
> +infinity.

no, you only need to look at the frequency range you need for a
result, otherwise the fft isn't viable

> It's too complicated, and there is no closed-form solution. So I need to
> compute the Foureir transform numerically...
>
> How to do that? I have some past experience with FFT but now I need to renew
> my memory.

the fft algorithms are widely availably, any C compiler or math
package has them

> Please give me some pointers about how to convert the infinite range
> integration to finite sums in FFT?

people use the fft (fast fourier transform) simply because it is
computationaly more efficient than doing all the matrix multiplication
that a finite elements fourier transform requires. for instance, if
you want to minimise badwidth for realtime voice transmission, you
take the audio signal, put it into the frequency domain, and keep only
the useful frequencies (20hz - 8 Khz) send that to the reciever, who
can do the ifft (inverse fast fourier transform) which outputs the
voice, and little else. the fft was discovered by accident and solved
a lot of problems in realtime spectral analysis at a time when
computer speed was limited. the same thing can be acheived by the
fourier transorm, it just takes much longer for each packet.

the other thing about the fft is that it is fairly accurate, there is
always a small loss with numerical methods, but the fft is quite
reliable.

> Moreover, the Foureir transform can also be computed by numerical
> integration, what's the disadvantage and advantage of both approaches?
> Before I begin the work, I would like to hear your expert opinions and
> comments about these approaches.

if you want an infinite range you have to do the maths. if you want to
convert discreet samples into the frequency domain, use the fft.


> Thanks a lot!

derek

Mike wrote:
> Hi all,
> 
> I want to take Foureir transform of f(t), which is F(v),
> 
> and a continuous-time Foureir transform needs to integrate from -infinity to 
> +infinity.
> 
> It's too complicated, and there is no closed-form solution. So I need to 
> compute the Foureir transform numerically...
> 
> How to do that? I have some past experience with FFT but now I need to renew 
> my memory.
> 
> Please give me some pointers about how to convert the infinite range 
> integration to finite sums in FFT?
> 
> Moreover, the Foureir transform can also be computed by numerical 
> integration, what's the disadvantage and advantage of both approaches? 
> Before I begin the work, I would like to hear your expert opinions and 
> comments about these approaches.
> 
> Thanks a lot! 
> 
> 

A document accessible from http://mathalacarte.com/c/math77_head.html
(then go to item 10.0 for the link to the document) may be of some use
to you.
Fred

Mike wrote:

> I just don't understand in practice how people use FFT to do Foureir 
> transform, because it is almost always an infinite integral. We know that if 
> a signal is finite support in time domain, then it is infinite support in 
> spectrum domain; vice versa. So anyway people will have to face the infinite 
> support problem, no matter if they use FFT or numerical integration. How do 
> they handle this nicely?

The FFT is misnamed, it is actually a Fourier series.  But then much
of computing deals with approximations, including Fortran's REAL
variables which include only a small subset of the real line.

> FFT is highly optimized throughout the years, but it uses uniform samplings; 
> of course I can imagine over the years people invented non-uniform sampling 
> FFT, but less efficient since they are less popular. But on the other hand, 
> numerical integration such as Gaussian Quardrature method etc. are also 
> highly optimized and they are supposed to use "smart" and "adaptive" 
> sampling points. Does anybody have a comparison between them?

Gaussian quadrature is not adaptive, but takes advantage of the 2N
degrees of freedom available choosing the position and magnitude
of each sample point.  With the assumption that the integrand
is a polynomial, it works well.

http://mathworld.wolfram.com/GaussianQuadrature.html

> I am still not sure about the points you made about the infinite integral 
> part. Do you mean I have to truncate at some large range, and then use other 
> ways to compute tail integral?

An indefinite integral doesn't have a numerical value.
That is what the +C indicates.

-- glen

Mike wrote:
> 
> FFT is highly optimized throughout the years, but it uses uniform samplings;
> of course I can imagine over the years people invented non-uniform sampling
> FFT, but less efficient since they are less popular. But on the other hand,
> numerical integration such as Gaussian Quardrature method etc. are also
> highly optimized and they are supposed to use "smart" and "adaptive"
> sampling points. 

Even so, there's a usual caveat - use at your own risk and *ymmv*, and
particularly so when dealing with infinite intervals. Case in point,
integrate sinc(t) from zero to inf with quadpack code for such matters, 
 
	http://netlib.org/quadpack/qagi.f 
 
a globally adaptive quadrature integrator for infinite intervals. Since
the integral is known - pi/2 - it is less than comforting how poor the
result turns out to be.

---
sdx - modeling, simulation.
http://www.sdynamix.com

"glen herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message 
news:1tWdnfuwYPN6uNPbnZ2dnUVZ_rTinZ2d@comcast.com...
: Mike wrote:
:
: > I just don't understand in practice how people use FFT to do Foureir
: > transform, because it is almost always an infinite integral. We know 
that if
: > a signal is finite support in time domain, then it is infinite support 
in
: > spectrum domain; vice versa. So anyway people will have to face the 
infinite
: > support problem, no matter if they use FFT or numerical integration. How 
do
: > they handle this nicely?
:
: The FFT is misnamed, it is actually a Fourier series.

Correct, and  FFT means Fast Fourier Transform.
"Fast" depends on the computer used, so it's doubly misnomered.

:  But then much
: of computing deals with approximations, including Fortran's REAL
: variables which include only a small subset of the real line.

There is a target value and a tolerance. In the case of Fourier, there is
also a limit to the number of frequencies to be considered.
Computers are as exact as we want them to be.

When a mathematician writes "pi" he means an exact quantity.
When a computer produces 3.1415926535897932384626433832795
then that's as exact as I want it to be, but it's not pi.


: > FFT is highly optimized throughout the years, but it uses uniform 
samplings;
: > of course I can imagine over the years people invented non-uniform 
sampling
: > FFT, but less efficient since they are less popular. But on the other 
hand,
: > numerical integration such as Gaussian Quardrature method etc. are also
: > highly optimized and they are supposed to use "smart" and "adaptive"
: > sampling points. Does anybody have a comparison between them?
:
: Gaussian quadrature is not adaptive, but takes advantage of the 2N
: degrees of freedom available choosing the position and magnitude
: of each sample point.  With the assumption that the integrand
: is a polynomial, it works well.
:
: http://mathworld.wolfram.com/GaussianQuadrature.html
:
: > I am still not sure about the points you made about the infinite 
integral
: > part. Do you mean I have to truncate at some large range, and then use 
other
: > ways to compute tail integral?
:
: An indefinite integral doesn't have a numerical value.

Correct.

: That is what the +C indicates.

Huh?
An indefinite integral is analytical; it has no predefined limits
and is expressed as a function.
A definite integral has a value, the limits are known.
Explain, please.

robert wrote:
>> I want to take Foureir transform of f(t), which is F(v),
> 
> Fourier transform

> ... discreet samples ...

Discrete samples. :-)

-- 
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet

"widmar" <jrw@sdynamix.com> wrote in message 
news:464E2B7D.26CB3D98@sdynamix.com...
> Mike wrote:
>>
>> FFT is highly optimized throughout the years, but it uses uniform 
>> samplings;
>> of course I can imagine over the years people invented non-uniform 
>> sampling
>> FFT, but less efficient since they are less popular. But on the other 
>> hand,
>> numerical integration such as Gaussian Quardrature method etc. are also
>> highly optimized and they are supposed to use "smart" and "adaptive"
>> sampling points.
>
> Even so, there's a usual caveat - use at your own risk and *ymmv*, and
> particularly so when dealing with infinite intervals. Case in point,
> integrate sinc(t) from zero to inf with quadpack code for such matters,
>
> http://netlib.org/quadpack/qagi.f
>
> a globally adaptive quadrature integrator for infinite intervals. Since
> the integral is known - pi/2 - it is less than comforting how poor the
> result turns out to be.
>
> ---

I don't understand your reply. Are you saying that the numerical integration 
and FFT both fail when the integrand is "wierd"? I came to seek help because 
exactly the same problem -- I have met with a lot numerical difficulties in 
integration with infinite support... Any thoughts?
> sdx - modeling, simulation.
> http://www.sdynamix.com
>