Asymptotic behavior of automatic quadrature

The computational cost of automatic quadrature programs is analyzed under the hypothesis of exactness (or asymptotic consistence) of local error estimates. The complexity measure used, in this work, is the number N of function evaluations in real exact arithmetic seen as a function of :he number E of exact decimal digits in the result. The methods of integration reviewed are m-panel rules, Clenshaw-Curtis quadrature, global adaptive quadrature, double exponential quadrature. For m-panel and global adaptive quadrature, based on a local rule of degree r - 1 the constants hidden by the "O" notation are determined in terms of the derivatives of the integrand and of the numerical properties of the local rule. Two new algorithms are introduced, called double-adaptive quadrature and triple-adaptive quadrature, which achieve outstanding performances on several classes of integrands.