4
$\begingroup$

I am looking to numerically solve many different integrals where the integrand is simply the indicator function for a region (i.e. 1 on the region, 0 outside. This is for measuring areas). The dimensions range from 1 to 5.

What is an efficient quadrature method solving this? It seems like the standard methods which utilize polynomial approximations and derivatives wouldn't help in this case because the function is constant (and then discontinuous). You can think of the problem as having a simple integrand, but a complex region (with a continuous maybe even smoother boundary).

Do you think that adaptive Monte Carlo methods like VEGAS or MISER integration will help out? Or is it just best to take a fine grid, sum up the function values at the grid points, and multiply by a constant (area of grid / number of points)?

Improve this question
$\endgroup$
3
  • $\begingroup$ Do you know if the region has any special properties? Or is it just an arbitrary Lebesgue-measurable set? $\endgroup$
    – Kirill
    Feb 3 '16 at 13:08
  • $\begingroup$ The region can be described as the set where a ~12 degree complex polynomial in 2 variables is greater than 1 in magnitude. So the boundary should be smooth in some sense. $\endgroup$
    – Chris Rackauckas
    Feb 3 '16 at 16:50
  • $\begingroup$ Possibly relevant, but not at all efficient, involving an infinite-dimensional SDP problem: Approximate Volume and Integration for Basic Semialgebraic Sets $\endgroup$
    – Kirill
    Mar 21 '16 at 16:35
3
$\begingroup$

I found that the grid summing method beat out both the Cubature package and the adaptive Monte Carlo schemes from the GSL package (standard, VEGAS, and MISER) when it came to both speed an accuracy (in fact, Cubature's hcubature adaptive methods wouldn't converge for abstol<1e-1, showing that it really cannot handle these kinds of problems). For future reference, I found a paper on a method called adaptive geometric integration that someone might wish to try, but for now simply summing over the grid (which is easy to parallelize) seems to be the best option for the effort.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.