Efficient integration over polytopes (Q1079329)

The integral of a multinomial P(\(\vec x)\) over an N-dimensional polytope is, in principle, an elementary but tedious task. The authors have constructed an algorithm for this. The input comprises the \(K\times (N+1)\) coefficients of K linear constraints, which define the polytope together with the coefficients and corresponding exponent sets which define P(\(\vec x)\). An elegant derivation, using a classical generating function of the recursion on which their algorithm is based, is presented. The authors also show how to reformulate problems in which the constraints are multinomial in such a way that their algorithm may be used. A detailed description of the algorithm is given, together with an analysis of its complexity and an empirical comparison of its efficiency with others. Implementations in FORTRAN and PASCAL are available from the first author.