Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Automatic evaluations of cross-derivatives


Authors: Andreas Griewank, Lutz Lehmann, Hernan Leovey and Marat Zilberman
Journal: Math. Comp. 83 (2014), 251-274
MSC (2010): Primary 65D25, 68W30, 65D30, 65C05
Published electronically: May 22, 2013
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65D25, 68W30, 65D30, 65C05

Retrieve articles in all journals with MSC (2010): 65D25, 68W30, 65D30, 65C05


Additional Information

Andreas Griewank
Affiliation: Department of Mathematics, Humboldt-Universität zu Berlin, Unter den Linden, 610099 Berlin
Email: griewank@math.hu-berlin.de

Lutz Lehmann
Affiliation: Department of Mathematics, Humboldt-Universität zu Berlin, Unter den Linden, 610099 Berlin
Email: llehmann@math.hu-berlin.de

Hernan Leovey
Affiliation: Department of Mathematics, Humboldt-Universität zu Berlin, Unter den Linden, 610099 Berlin
Email: leovey@math.hu-berlin.de

Marat Zilberman
Affiliation: Haifa
Email: marat.zilberman@gmail.com

DOI: http://dx.doi.org/10.1090/S0025-5718-2013-02717-2
PII: S 0025-5718(2013)02717-2
Received by editor(s): October 11, 2009
Received by editor(s) in revised form: June 3, 2011, January 2, 2012, and May 11, 2012
Published electronically: May 22, 2013
Additional Notes: The first author’s work was partially supported by the DFG research center “MATHEON, Mathematics for the key technologies” in Berlin
The fourth author’s IAESTE internship was supported by grant of DAAD
Article copyright: © Copyright 2013 American Mathematical Society