Explicit cost bounds of algorithms for multivariate tensor product problems (Q1346592)

The authors study multivariate tensor product problems in the worst case and average case settings. These are defined as computing an \(\varepsilon\)-approximation to a linear operator acting on functions \(f\) of \(d\) variables. For arbitrary \(d\), explicit upper bounds on the costs of algorithms which compute an \(\varepsilon\)-approximation to the solution are provided. The cost bound are of the form \[ \bigl( C(d) + 2 \bigr) \beta_ 1 (\beta_ 2 + \beta_ 3) \log (1/ \varepsilon)/(d - 1)^{\beta_ 4 (d - 1)} (1/t)^{\beta_ 5}, \] where \(C(d)\) is the cost of one function evaluation, and the \(\beta_ i\)'s do not depend on \(d\). These bounds are determined by the properties of the problems, and these cost bounds do not exceed \(C(d) ke^{-p}\) for some numbers \(k\) and \(p\), both independent of \(d\) and \(p\) too large. These general estimates are applied to certain integration and approximation problems in the worst and average case settings. Finally an upper bound which is independent of \(d\), for the number \(n(\varepsilon,d)\), of points for which discrepancy (with unequal weights) is at most \(\varepsilon\), \(n(\varepsilon,d) \leq 7.26 \varepsilon^{-2.45d}\) for all \(d, \varepsilon \leq 1\) is obtained also.