6
$\begingroup$

I'm trying to implement a numerical integrator that should have the minimum relative error and is not slow. So I was looking for the best accepted state-of-the-art algorithm to do so but there seems to be so many approaches that I could not understand which one should I choose. So I'm turning to you for a recommendation.

Thank you for your attention,

  • 0
    I suggest you try [adaptive quadrature](http://en.wikipedia.org/wiki/Adaptive_quadrature).2012-04-17
  • 4
    There is no such thing as "one algorithm to evaluate them all". Methods for "nice integrals" are quite different from methods for, say, infinite oscillatory integrals, or Cauchy principal value integrals. That's why there are a lot of algorithms, since families of integrals might carry their own unique set of difficulties.2012-04-17
  • 0
    So your recommendation would be to have a set of solvers that would vary accordingly from some sort of integral previous analysis?2012-04-17
  • 0
    @Reonarudo : I believe in more traditional hyphenation conventions, and changed this to "best state-of-the-art numerical integral algorithm", _with_ hyphens. If it had said "What is the state of the art?", I'd have left it without hyphens. But change it back if you disagree.2012-04-17
  • 2
    Yes, and that is precisely the route taken by packages like QUADPACK...2012-04-17
  • 0
    This is a complete deviation from the original question but what kind of previous analysis should be performed then?2012-04-17
  • 2
    Offhand: check for singularities. Improper integrals often require special methods. Functions with rapidly decaying or very oscillatory factors also need special treatment. Discontinuous functions require splitting at discontinuities. Everything else is fair game for adaptive quadrature.2012-04-17
  • 0
    @J.M.but QUADPACK is one dimensional, I didn't specify in the question but my goal is something that can compute at least 3 dimension integrals. But a good example anyway. I think I'll start of from your suggestion and see where I get. Thank you.2012-04-17
  • 2
    Well, not my fault that you weren't specific at the outset, no? Efficient cubature methods remain an active area of research, and unless you have the expertise, I caution against rolling out your own implementation. You will want to look at the work already done by Ronald Cools and Terje Espelid.2012-04-17

1 Answers 1

5

As @J.M noted, there are many methods, each suited for a certain purpose. If you don't know what the function are in advance, then for low-dimensional ($d < 3$) integrals a adaptive Gauss–Kronrod rule quadrature is probably the fastest.

In higher dimensions, you can really only use Monte-Carlo methods.

If know apriori that the functions have a very large range, you can use a weighted Monte-Carlo approach, in which you select more points in the "large" regions, than in the "smaller" ones.

  • 1
    [Double-exponential quadrature](http://www.kurims.kyoto-u.ac.jp/~ooura/intde.html) is claimed to be competitive with adaptive Gauss-Kronrod for "smooth enough" integrals, or integrals with endpoint singularities that aren't too "wild". I haven't done tests myself to confirm this, but I'm putting it out here in case somebody's inclined to play around a bit.2012-04-17
  • 0
    @J.M - Thanks for the info, I wasn't familiar with that method. The [Wiki article](http://en.wikipedia.org/wiki/Tanh-sinh_quadrature) claims that "Tanh-sinh quadrature is less efficient than Gaussian quadrature for smooth integrands, but unlike Gaussian quadrature tends to work equally well with integrands having singularities or infinite derivatives at one or both endpoints of the integration interval."2012-04-17
  • 0
    In any case, if the OP wants $d > 3$, neither of these will work.2012-04-17
  • 0
    Right, cubature is a different can of worms. There is Genz-Malik and a number of other multidimensional methods for a very restricted class of multiple integrals, but indeed as you say, (quasi-)Monte Carlo is something to be contented with for most problems.2012-04-17