Fast algorithms for multivariate interpolation and evaluation at special points

In this paper we present explicit formulae for the multivariate Lagrange–Newton transformation T:Kn1×n2×⋯×nd→Kn1×n2×⋯×ndT:Kn1×n2×⋯×nd→Kn1×n2×⋯×nd and its inverse T−1T−1 with respect to points xi,j=λixi,j−1+δixi,j=λixi,j−1+δi  (i=1,2,…,d,j=1,2,…,ni−1)(i=1,2,…,d,j=1,2,…,ni−1), where λi≠0λi≠0, δiδi and xi,0=ϰixi,0=ϰi belong to the field KK. Moreover, we derive fast algorithms for computing these transformations. The running time of them is O(∏j=1dnj⋅log∏j=1dnj)+O(d∏j=1dnj) base operations from KK.