MiS Preprint Repository

There are many papers studying polynomial tractability for multivariate problems. Polynomial tractability means that the minimal number $n(\epsilon ,d)$ of information evaluations needed to reduce the initial error by a factor of $\epsilon$ for a multivariate problem defined on a space of $d$-variate functions may be bounded by a polynomial in ${\epsilon }^{-1}$ and $d$ and this holds for all $({\epsilon }^{-1},d)\in [1,\mathrm{\infty })\times \mathbb{N}$.

We propose to study {\it generalized} tractability by verifying when $n(\epsilon ,d)$ can be bounded by a power of $T({\epsilon }^{-1},d)$ for all $({\epsilon }^{-1},d)\in \mathrm{\Omega }$, where $\mathrm{\Omega }$ can be a proper subset of $[1,\mathrm{\infty })\times \mathbb{N}$. Here $T$ is a tractability function which is non-decreasing in both variables and grows slower than exponentially to infinity.

In this paper we study the set $\mathrm{\Omega }=[1,\mathrm{\infty })\times \{1,2,\dots ,d^{\ast }\}\cup [1,{\epsilon }_0^{-1})\times \mathbb{N}$ for some $d^{\ast }\ge 1$ and ${\epsilon }_0\in (0,1)$. We study linear tensor product problems for which we can compute arbitrary linear functionals as information evaluations. We present necessary and sufficient conditions on $T$ such that generalized tractability holds for linear tensor product problems. We show a number of examples for which polynomial tractability does not hold but generalized tractability does hold.