Tensor-product approximation to operators and functions in high dimensions

In recent papers tensor-product structured Nystrom and Galerkin-type approximations of certain multidimensional integral operators have been introduced and analysed. In the present paper, we focus on the analysis of the collocation-type schemes with respect to the tensor-product basis in a high spatial dimension d. Approximations up to an accuracy O(N-alpha/d) are proven to have the storage complexity O(dN(1/d) log(q) N) with q independent of d, where N is the discrete problem size. In particular, we apply the theory to a collocation discretisation of the Newton potential with the kernel 1/vertical bar x-y vertical bar, x, y is an element of R-d, d >= 3. Numerical illustrations are given in the case of d = 3. (c) 2007 Published by Elsevier Inc.