Directions for computing truncated multivariate Taylor series

Efficient recurrence relations for computing arbitrary-order Taylor coefficients for any univariate function can be directly applied to a function of $n$ variables by fixing a direction in $\mathbb{R} ^{n}$. After a sequence of directions, the multivariate Taylor coefficients or partial derivatives can be reconstructed or ``interpolated''. The sequence of univariate calculations is more efficient than multivariate methods, although previous work indicates a space cost for this savings and significant cost for the reconstruction. We completely eliminate this space cost and develop a much more efficient algorithm to perform the reconstruction. By appropriate choice of directions, the reconstruction reduces to a sequence of Lagrange polynomial interpolation problems in $\mathbb{R} ^{n-1}$ for which a divided difference algorithm computes the coefficients of a Newton form. Another algorithm collects like terms from the Newton form and returns the desired multivariate coefficients.