

Preprint 2/2006
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.