We study the epsilon-approximation of linear multivariate problems defined
over weighted tensor product Hilbert spaces of functions f of d variables.
A class of weighted tensor product (WTP) algorithms is defined which depend
s on a number of parameters. Two classes of permissible information are stu
died..Lambda(all) consists of all linear functionals while...Lambda(std) co
nsists of evaluations of f or its derivatives. We show that these multivari
ate problems are sometimes tractable even with a worst-case assurance. We s
tudy problem tractability by investigating when a WTP algorithm is a polyno
mial-time algorithm. that is. when the minimal number of information evalua
tions is a polynomial in 1/epsilon and d. For Lambda(all) we construct an o
ptimal WTP algorithm and provide a necessary and sufficient condition for t
ractability in terms of the sequence of wrights and the sequence of singula
r values for d = 1. For Lambda(std) we obtain a weaker result by constructi
ng a WTP algorithm which is optimal only for some weight sequences. (C) 199
9 Academic Press.