An Experimental Algorithm for N -Dimensional Adaptive Quadrature

Publisher Website
Google Scholar
Abstract
/A working experimental program for n-dimensional adaptive quadrature is discussed. The program uses the simplex rather than the cube as the basic "cell." Symmetric interpolatory quadratures of variable order are derived during execution and used as basic integrators Integrand values are stored into a table via a double hashing technique for efficient retrieval. Iterated calls are allowed with the dimension of the region factored arbitrarily. Restarting the calculation for greater precision costs no more than if the user had requested the higher accuracy in the first place The vast majority of one-dimensional quadrature calculations are presently being done by "adaptive" algorithms. By this we mean an algorithm in which the integrand evaluation points (quadrature nodes) are not fixed in advance but depend in some usually complicated way on the integrand. Thus some of these algorithms select nodes in a way which makes their density proportional to a high derivative of the integrand function. Experience has convinced most users that these algorithms are very efficient, and enough theory has been developed to show that within large problem families they are in some sense optimal [14]. Nevertheless, there are many variations in strategy and implementation and the field is an active research area. Relatively little has been attempted for multidimensional quadrature even though such problems exist and need to be solved. There are very few certified programs. However, many local programs in various stages of testing are available and have b een used successfully. These programs either use local polynomial approximation, or Monte Carlo (pseudorandom) sampling, based on the desire to place evaluation points where they are most needed. Some programs use both methods. The polynomial techniques have higher convergence rates (in principle) and can reuse function values in an efficient way if the integrand can be locally approximated by a polynomial. The sampling methods can be used over more general regions, are easier to implement, and make no explicit assumptions about the local nature of the integrand.

This publication has 8 references indexed in Scilit: