1995 Reports

On tractability of path integration

Wasilkowski, Grzegorz W.; Wozniakowski, Henryk

Do we really need to use randomized algorithms for path integrals? Perhaps we can find a deterministic algorithm that is more effective even in the worst case setting. To answer this question we study the worst case complexity of path integration which roughly speaking is defined as the minimal number of the integrand evaluations needed to compute an approximation with error at most e. We consider path integration with respect to a Gaussian measure and for various classes of integrands.