The randomized information complexity of elliptic PDE (Q2489143)

The author considers information complexity in the randomized setting of solving a general elliptic partial differential equations (PDEs) of order \(2m\) in a smooth, bounded domain \(Q \subset \mathbb R^d\) with smooth coefficients and homogeneous boundary conditions. The information complexity is characterised by the minimal number of function value calls any algorithm has to invoke in order to reach a certain error. Equivalently, the minimal error among all possible algorithms making not more than a given number (\(n\)) of function calls is studied. Adaptive randomized algorithms are considered. The solution is sought on a smooth submanifold \(M \subseteq Q\) of dimension \(0 \leq d_1 \leq d\), the right-hand side is supposed to be in \(C^r(Q)\), the error is measured in the \(L_{\infty}(M)\) norm. It is shown that the \(n\)\textit{th} minimal error is (up to logarithmic factors) of order \[ n^{-\min((r+2m)/d_1,r/d+1/2)}. \] For comparison, it is of order \(n^{-r/d}\) for all \(d_1\) in the deterministic setting.