On the complexity of parabolic initial-value problems with variable drift (Q2489153)

The authors study the complexity of parabolic initial-value problems with variable drift using either deterministic or stochastic (Monte Carlo type) algorithms. A worst-case approach for the analysis and a comparison of the algorithms are presented assuming that the drift coefficients and the potential vary in given function spaces. Asymptotic upper and lower bounds of the minimal errors are given and algorithms with errors close to the corresponding minimal error and with a linear computational cost (with respect to the number of unknowns) are described. The analysis relies on the construction of fundamental solutions under mild regularity assumptions. The results are applied to equations with coefficients belonging to Hölder classes, and it is shown that in many cases the algorithms are almost optimal.