L. Plaskota, G.W. Wasilkowski, and H. Wozniakowski
A new algorithm and worst case complexity
for Feynman-Kac path integration
Abstract.
We study algorithms for approximation of Feynman-Kac path integrals
in the worst case setting. The algorithms use a finite number of samples
of the initial condition and potential functions. We present a new algorithm
and an explicit bound on its cost to compute an $\varepsilon$-approximation
to the Feynman-Kac path integral.
We also establish bounds on the worst case complexity of Feynman-Kac path
integration. The upper bound is equal to the cost of the new algorithm, and
is given in terms of the complexity of a certain function approximation
problem. The lower bound is given in terms of the complexity of a certain
weighted integration problem. For some classes of functions, these two
bounds coincide modulo a multiplicative factor. In this case, the new
algorithm is almost optimal.
The new algorithm requires precomputation of some real coefficients that
are combinations of multivariate integrals with specific weights.
This precomputation is difficult and limits the application of the new
algorithm. We report the results of the precomputation for specific cases.