A NEARLY-OPTIMAL ALGORITHM FOR THE FREDHOLM PROBLEM OF THE SECOND KIND OVER A NON-TENSOR PRODUCT SOBOLEV SPACE

摘要

In a previous paper, the authors showed that the information complexity of the Fredholm problem of the second kind is essentially the same as that of the approximation problems over the spaces of kernels and right-hand sides. This allowed us to give necessary and sufficient conditions for the Fredholm problem to exhibit a particular level of tractability (for information complexity) over weighted tensor product (WTP) spaces, as well as over an important class of not necessarily tensor product weighted Sobolev spaces. Furthermore, we addressed the overall complexity of this Fredholm problem for the case in which the kernels and right-hand sides belong to a WTP space. For this case, we showed that a nearly-minimal-error interpolatory algorithm is easily implementable, with cost very close (to within a logarithmic factor) to the information cost. As a result, tractability results, which had previously only held for the information complexity, now hold for the overall complexity-provided that our kernels and right-hand sides belong to WTP spaces. This result does not hold for the weighted Sobolev spaces mentioned above, since they are not necessarily tensor product spaces.