Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 


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
MathSciNet review: 3120589
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?)

  • [BGLS10] Torsten Bosse, Andreas Griewank, Lutz Lehmann, and Volker Schloßhauer, On Hessian- and Jacobian-free SQP methods - a total quasi-Newton scheme with compact storage, Recent Advances in Optimization and its Applications in Engineering (Moritz Diehl, Francois Glineur, Elias Jarlebring, and Wim Michiels, eds.), Springer Berlin Heidelberg, 2010, pp. 63-72.
  • [BHKK07] Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto, Fourier meets Möbius: fast subset convolution, Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC '07, ACM, 2007, pp. 67-74. MR 2402429 (2010e:68220)
  • [CU09] Isabelle Charpentier and Jean Utke, Fast higher-order derivative tensors with Rapsodia, Optimization Methods Software 24 (2009), no. 1, 1-14.
  • [DP10] Josef Dick and Friedrich Pillichshammer, Digital nets and sequences, Cambridge University Press, Cambridge, 2010, Discrepancy theory and quasi-Monte Carlo integration. MR 2683394
  • [GJ79] M. R. Garey and D. S. Johnson, Computer and Intractability. A Guide to the Theory of NP-Completeness, Freeman & Co., New York, 1979. MR 519066 (80g:68056)
  • [GKS10] Michael Griebel, Frances Y. Kuo, and Ian H. Sloan, The smoothing effect of the ANOVA decomposition, J. Complexity 26 (2010), no. 5, 523-551. MR 2719646
  • [Gla04] Paul Glasserman, Monte Carlo methods in financial engineering, Applications of Mathematics (New York), vol. 53, Springer-Verlag, New York, 2004, Stochastic Modelling and Applied Probability. MR 1999614 (2004g:65005)
  • [Gri06] Michael Griebel, Sparse grids and related approximation schemes for higher dimensional problems, Foundations of computational mathematics, Santander 2005, London Math. Soc. Lecture Note Ser., vol. 331, Cambridge Univ. Press, Cambridge, 2006, pp. 106-161. MR 2277104 (2007k:65206)
  • [GUW00] Andreas Griewank, Jean Utke, and Andrea Walther, Evaluating higher derivative tensors by forward propagation of univariate Taylor series., Math. Comp. 69 (2000), no. 231, 1117-1130 (English). MR 1651755 (2000j:65033)
  • [GW02] Andreas Griewank and Andrea Walther, On constrained optimization by adjoint based quasi-Newton methods, Optimization Methods and Software 17 (2002), no. 5, 869-889. MR 1953823 (2003m:90162)
  • [GW08a] -, Evaluating derivatives, second ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2008, Principles and techniques of algorithmic differentiation. MR 2454953
  • [GW08b] Andreas Griewank and Andrea Walther, Evaluating derivatives: Principles and techniques of algorithmic differentiation, 2nd ed., Other Titles in Applied Mathematics, no. 105, SIAM, Philadelphia, PA, 2008. MR 2454953 (2011a:65053)
  • [GWK07] Andreas Griewank, Andrea Walther, and Maciek Korzec, Maintaining factorized KKT systems subject to rank-one updates of Hessians and Jacobians, Optim. Methods Softw. 22 (2007), no. 2, 279-295. MR 2288765 (2007i:90109)
  • [Hic98] Fred J. Hickernell, Lattice rules: How well do they measure up?, Random and quasi-random point sets, Lecture Notes in Statist., vol. 138, Springer, New York, 1998, pp. 109-166. MR 1662841 (2000b:65007)
  • [JK08] Stephen Joe and Frances Y. Kuo, Constructing Sobol' sequences with better two-dimensional projections, SIAM J. Sci. Comput. 30 (2008), no. 5, 2635-2654. MR 2429482 (2009j:65066)
  • [Knu69] Donald E. Knuth, The art of computer programming, volume ii: Seminumerical algorithms, Addison-Wesley, Reading, MA, 1969. MR 0378456 (51:14624)
  • [KS05] Frances Y. Kuo and Ian H. Sloan, Lifting the curse of dimensionality, Notices Amer. Math. Soc. 52 (2005), no. 11, 1320-1329. MR 2183869 (2006j:65061)
  • [Kub08] Koichi Kubota, Combinatorial computation with automatic differentiation, Advances in Automatic Differentiation (Christian H. Bischof, H. Martin Bücker, Paul D. Hovland, Uwe Naumann, and Jean Utke, eds.), Lecture Notes in Computational Science and Engineering, vol. 64, Springer, Berlin, 2008, pp. 315-325. MR 2531693 (2010g:05205)
  • [LG12] Hernan Leovey and Andreas Griewank, Computation of optimal weights for quasi-Monte Carlo via algorithmic differentiation, In preparation (2012).
  • [Mar04] George Marsaglia, Evaluating the normal distribution, Journal of Statistical Software 11 (2004), no. 5, 1-11.
  • [MN98] Makoto Matsumoto and Takuji Nishimura, Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Trans. Model. Comput. Simul. 8 (1998), 3-30.
  • [NC06] Dirk Nuyens and Ronald Cools, Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces, Math. Comp. 75 (2006), no. 254, 903-920 (electronic). MR 2196999 (2007a:65032)
  • [Nie92] Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997 (93h:65008)
  • [Nuy07] D. Nuyens, Fast construction of good lattice rules, PhD. Thesis, Katholieke Universiteit Leuven (2007), 903-920.
  • [NW08] Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Volume i: Linear information, EMS Tracts in Mathematics, vol. 6, European Mathematical Society (EMS), Zürich, 2008. MR 2455266 (2009m:46037)
  • [NW10] -, Tractability of multivariate problems. Volume II: Standard information for functionals, EMS Tracts in Mathematics, vol. 12, European Mathematical Society (EMS), Zürich, 2010. MR 2676032 (2011h:46093)
  • [ORO05] Takeshi Ogita, Siegfried M. Rump, and Shin'ichi Oishi, Accurate Sum and Dot Product, SIAM J. Sci. Comput 26 (2005), no. 6, 1955-1988. MR 2196584 (2006i:65077)
  • [Rys63] H. J. Ryser, Combinatorial mathematics, Carus Mathematical Monographs, no. 14, Mathematical Association of America, 1963. MR 0150048 (27:51)
  • [WF03] Xiaoqun Wang and Kai-Tai Fang, The effective dimension and quasi-Monte Carlo integration, J. Complexity 19 (2003), no. 2, 101-124. MR 1966664 (2003m:62016)
  • [WS07] Xiaoqun Wang and Ian H. Sloan, Brownian bridge and principal component analysis: towards removing the curse of dimensionality, IMA J. Numer. Anal. 27 (2007), no. 4, 631-654. MR 2371825 (2009a:62248)

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

Lutz Lehmann
Affiliation: Department of Mathematics, Humboldt-Universität zu Berlin, Unter den Linden, 610099 Berlin

Hernan Leovey
Affiliation: Department of Mathematics, Humboldt-Universität zu Berlin, Unter den Linden, 610099 Berlin

Marat Zilberman
Affiliation: Haifa

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

American Mathematical Society