Multiple point evaluation on combined tensor product supports (Q2376366)

Let \(f_1,f_2,\dots,f_n\) (\(n\) large, \(n\in\mathbb{N}\)) be a sequence of functions belonging to a vector space \(V\)V of real-valued functions defined on the \(d\)-dimensional hypercube \([-1,1[^d\), \(d\in\mathbb{N}\) and \(a_k,b_k\in[-1, 1[^d\) \((k= 1,2,\dots,n\)) two given arbitrary sequences of points with \(a_k< b_k\) (in a componentwise sense). Denote by \(\chi_{a_k,b_k}\) the characteristic function of a non-degenerate tensor product box with corners \(a_k,b_k\in\mathbb{R}^d\) and consider the linear combination of basis functions with tensor product support \[ \psi(x)= \sum_{k=1,\dots,n} f_k(x)\chi_{a_k,b_k}(x),\;x\in [-1,1[^d. \] The paper concerns the problem of the computation of the \(m\) values of \(\psi\) in \(m>n\) given points \(x_k\) and proposes data structures and an algorithm that allows to perform the evaluations with computational cost \(O(m\log^d n)\) for \(n,m\to\infty\).