A new algorithm and worst case complexity for Feynman-Kac path integration

Leszek Plaskota, Grzegorz W. Wasilkowski, Henryk Woźniakowski

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


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 ε-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 special weights. This precomputation is difficult and limits the application of the new algorithm. We report the results of the precomputation for specific cases.

Original languageEnglish
Pages (from-to)335-353
Number of pages19
JournalJournal of Computational Physics
Issue number2
StatePublished - Nov 1 2000

Bibliographical note

Funding Information:
We are grateful to Joseph F. Traub for valuable comments. We also thank Anargyros Papageorgiou for providing us the FINDER package for multivariate integration. Finally, we thank an anonymous referee who found an error in the proof of the original version of Lemma 1. The first author was partially supported by the State Committee for Scientific Research of Poland under Grant 2 P03A 00913, and the second and third authors were supported by the National Science Foundation under Grants CCR-9729971 and CCR-9731858, respectively.


  • Feynman-Kac path integration
  • Multivariate approximation
  • Wiener measure
  • Worst case complexity

ASJC Scopus subject areas

  • Numerical Analysis
  • Modeling and Simulation
  • Physics and Astronomy (miscellaneous)
  • Physics and Astronomy (all)
  • Computer Science Applications
  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'A new algorithm and worst case complexity for Feynman-Kac path integration'. Together they form a unique fingerprint.

Cite this