Efficient convolution with the Newton potential in d dimensions

The paper is concerned with the evaluation of the convolution integral $${\int_{\mathbb{R}^d}\frac{1}{\left\Vert x-y\right\Vert} f(y){\rm d}y}$$ in d dimensions (usually d = 3), when f is given as piecewise polynomial of possibly large degree, i.e., f may be considered as an hp-finite element function. The underlying grid is locally refined using various levels of dyadically organised grids. The result of the convolution is approximated in the same kind of mesh. If f is given in tensor product form, the d-dimensional convolution can be reduced to one-dimensional convolutions. Although the details are given for the kernel $${{1 / \left \Vert x \right\Vert,}}$$ the basis techniques can be generalised to homogeneous kernels, e.g., the fundamental solution $${{const\cdot\left\Vert x\right\Vert ^{2-d}}}$$ of the d-dimensional Poisson equation.