Automatic evaluations of cross-derivatives

Abstract:

Cross-derivatives are mixed partial derivatives involving at most one differentiation in each one of $n$ coordinate directions. They are a computational tool in combinatorics and of potential use in high-dimensional integration. Here we present two methods that evaluate all $2^n$ cross-derivatives at a given point. The computational complexity is, respectively, $3^n$ and $n^2 2^n$ times that of the underlying function. The asymptotically faster method involves a final interpolation step, which can easily be carried out using extra-accurate subtractions to reduce the effect of numerical round-off. Further complexity reductions for large $n$ can be obtained through faster polynomial multiplications, e.g., Karatsuba’s method or FFT.