December 15, 1996
This paper is concerned with the worst case setting
of approximating multivariate tensor product linear operators
defined over Hilbert spaces.
Approximations are obtained by computing a number of linear
functionals from a given class of information.
We consider the three classes of information: the class of all linear
functionals, the Fourier class of inner products with respect to
given orthonormal elements, and the standard class of function values.
We analyze which problems are tractable and which strongly tractable.
The complete analysis is provided for approximating operators of
rank two or more. The problem of
approximating linear functionals is fully analyzed in the first two classes
of information. For the third class of standard information
we show that the possibilities are very rich. We prove that
tractability of linear functionals depends on the given space
of functions. For some spaces all nontrivial normed
linear functionals are intractable, whereas for other spaces
all linear functionals are tractable.
In ``typical'' function spaces some linear functionals are tractable
and some others are not.