Parallel Algorithms for Adaptive Quadrature. III. Program Correctness

This is the third in a sequence of papers on parallel algorithms for adaptive quadrature. The primary aim is to study the rate of convergence achieved by such algorithms. Here we prove that a specific algorithm (computer program) achieves the optimal rate of convergence which has been established by the previous papers. More specifically, under certain reasonable hypotheses, it is proved that this program terminates with a quadrature estimate within the prescribed input accuracy requirement and that this estimate is computed with a number of integrand evaluations of a specified order as the accuracy requirement goes to zero. Since operational parallel computers are still rare, the program is given in a pseudo-Fortran for a hypothetical true (multiple instruction stream, multiple data stream) parallel computer. A simulation shows that this algorithm has a reasonable speed-up, although it is not optimal in this paper.