Efficient integration over polytopes

摘要

An exact algorithm for integration over regions bounded by N-dimensional hyperplanes is presented. Integrands include arbitrary multinomials in the N variables xN = (x1,…,xN). Thus the technique can be used to evaluate all integrals of the form IP = ∫RP(xN) dxN where P is a multinomial in xN in EN and R is a convex region bounded by hyperplanes in EN. The algorithm is more efficient than methods that involve the partitioning of the region of integration into simplices. Methods of pruning the combinatorial tree the algorithm produces and extensions to provide approximations to integrals bounded by curved surfaces are provided. An analysis of the complexity of the algorithm and an empiritical comparison of the efficiency of the algorithm with others is presented.