Generalized Tractability for Multivariate Problems

Michael Gnewuch and Henryk Woźniakowski

Contact the author: Please use for correspondence this email.
Submission date: 09. Jan. 2006
Pages: 47
published in: Journal of complexity, 23 (2007) 2, p. 262-295 
DOI number (of the published article): 10.1016/j.jco.2006.06.006
Bibtex
with the following different title: Generalized tractability for multivariate problems. Pt. 1 : Linear tensor product problems and linear information
Download full preprint: PDF (375 kB), PS ziped (262 kB)

Abstract:
There are many papers studying polynomial tractability for multivariate problems. Polynomial tractability means that the minimal number of information evaluations needed to reduce the initial error by a factor of for a multivariate problem defined on a space of d-variate functions may be bounded by a polynomial in and d and this holds for all .

We propose to study generalized tractability by verifying when can be bounded by a power of for all , where can be a proper subset of . 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 for some and . 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.