Academic Commons

Reports

Tractability of the Fredholm problem of the second kind

Werschulz, Arthur G.; Wozniakowski, Henryk

We study the tractability of computing ε-approximations of the Fredholm problem of the second kind: given f ∈ Fd and q ∈ Q2d, find u ∈ L2(Id) satisfying
u(x)− q(x,y)u(y)dy=f(x) ∀x∈Id =[0,1]d. Id
Here, Fd and Q2d are spaces of d-variate right hand functions and 2d-variate kernels that are continuously embedded in L2(Id) and L2(I2d), respectively. We consider the worst case setting, measuring the approximation error for the solution u in the L2 (I d )-sense. We say that a problem is tractable if the minimal number of information operations of f and q needed to obtain an ε- approximation is sub-exponential in ε−1 and d. One information operation corresponds to the evaluation of one linear functional or one function value. The lack of sub-exponential behavior may be defined in various ways, and so we have various kinds of tractability. In particular, the problem is strongly polynomially tractable if the minimal number of information operations is bounded by a polynomial in ε−1 for all d. We show that tractability (of any kind whatsoever) for the Fredholm problem is equivalent to tractability of the L2-approximation problems over the spaces of right-hand sides and kernel functions. So (for example) if both these approximation problems are strongly polynomially tractable, so is the Fredholm problem. In general, the upper bound provided by this proof is essentially non-constructive, since it involves an interpolator algorithm that exactly solves the Fredholm problem (albeit for finite-rank approximations of f and q). However, if linear functionals are permissible and that Fd and Q2d are tensor product spaces, we are able to surmount this obstacle; that is, we provide a fully-constructive algorithm that provides an approximation with nearly-optimal cost, i.e., one whose cost is within a factor ln ε−1 of being optimal.

Subjects

Files

More About This Work

Academic Units
Computer Science
Publisher
Department of Computer Science, Columbia University
Series
Columbia University Computer Science Technical Reports, CUCS-021-10
Published Here
June 9, 2011
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.