Regresar

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 2n cross-derivatives at a given point. The computational complexity is, respectively, 3n and n22n 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. © 2013 American Mathematical Society.