Multi-point evaluation in higher dimensions

In this paper, we propose efficient new algorithms for multi-dimensional multi-point evaluation and interpolation on certain subsets of so called tensor product grids. These point-sets naturally occur in the design of efficient multiplication algorithms for finite-dimensional C -algebras of the form A = C [x₁, ..., x_n]/I, where I is generated by monomials of the form x₁i₁⋯x_ni_n one particularly important example is the algebra of truncated power series C[x ₁, ..., x_n]/(x₁, ..., x_n)d. Similarly to what is known for multi-point evaluation and interpolation in the univariate case, our algorithms have quasi-linear time complexity. As a known consequence Schost (ISSAC'05, ACM, New York, NY, pp 293-300, 2005), we obtain fast multiplication algorithms for algebras A of the above form.