Multiple point evaluation on combined tensor product supports

We consider the multiple point evaluation problem for an n-dimensional space of functions [ − 1,1[ d ↦ℝ spanned by d-variate basis functions that are the restrictions of simple (say linear) functions to tensor product domains. For arbitrary evaluation points this task is faced in the context of (semi-)Lagrangian schemes using adaptive sparse tensor approximation spaces for boundary value problems in moderately high dimensions. We devise a fast algorithm for performing m ≥ n point evaluations of a function in this space with computational cost O(mlog d n). We resort to nested segment tree data structures built in a preprocessing stage with an asymptotic effort of O(nlog d − 1 n)