Numerical integration - optimisation of code

[mikeph]

Hello

I have a function which is very similar in shape to a Gaussian, except it is not a distribution and it is not analytic, so I can at best calculate a single point on the curve at a time. (In general it is a convolution of different distributions but this is not important).

I need to find the area under this curve accurately, using the least amount of calculations (I need to find the area under ~1,000 curves and right now it is taking about 5 seconds per curve to get within about 1% accuracy, ideally the code needs to perform this in real time! ).My first try was to use a regular grid, eg. -10:0.01:10 for 2001 points, then the area (under)approximated by the sum of the values/100, the resolution. Varying the range and resolution of integration get me close to the "true" value but it takes too long, and I think I am wasting high resolution on the tail.
My next idea for optimisation is to have a grid which has more resolution at the areas of highest slope (does this make mathematical sense? I think...). I am having trouble justifying this and do not really know where to begin to implement it.

If anyone could point me to the right direction, I am sure this has been done before.

Regards,
Mike

 

[D H]

Some suggestions:

• Don't use a regular grid. Look into something like Gaussian quadrature.
• Is the function symmetric? If so, find the center and integrate half of the domain.
• That you said "-10:0.01:10" suggests you are doing this in Matlab. Matlab is 10-100 times slower than C or Fortran.

 

[Mark44]

Added clarification to 2nd bullet in case it wasn't obvious to the OP.

Some suggestions:

• Don't use a regular grid. Look into something like Gaussian quadrature.
• Is the function symmetric? If so, find the center and integrate half of the domain, and then double the result.
• That you said "-10:0.01:10" suggests you are doing this in Matlab. Matlab is 10-100 times slower than C or Fortran.

 

[mikeph]

Thanks for the replies. I'll look into Gaussian quadrature.

I feel silly not having thought of the symmetry of the curve, since I know exactly where the centre is already. Unfortunately I don't have access to C or Fortran, and my code needs to integrate with a lot of other code I have already written in MATLAB.

I didn't realize it was so slow though? How can it be so slow?

 

[D H]

You most certainly do have access to C. C/C++ comes bundled with the system if you are working on a Linux machine or a Mac. If you are working on a Windows machine, there are plenty of free C/C++ compilers available, some directly from Microsoft.

Matlab is a nice tool for developing an initial solution to some problem. It's graphics are phenomenal. It has huge libraries of tools and techniques. However, it is slow. It is an interpreted language.

Since you are using Matlab, learn to use the huge set of tools and techniques that are an integral part of Matlab. Look into Matlab's numerical quadrature routines. Matlab supplies a Gaussian quadrature function, and it is rather smart (adaptive). You do not need to reinvent the wheel here; besides, your wheel won't look as nice as Matlab's wheel. All you need to supply is the function and the integration interval to Matlab's Gaussian quadrature function -- and this can be an infinite interval with that function.