Automatic evaluations of cross-derivatives
HTML articles powered by AMS MathViewer
- by Andreas Griewank, Lutz Lehmann, Hernan Leovey and Marat Zilberman PDF
- Math. Comp. 83 (2014), 251-274 Request permission
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
- 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.
- Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto, Fourier meets Möbius: fast subset convolution, STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 67–74. MR 2402429, DOI 10.1145/1250790.1250801
- Isabelle Charpentier and Jean Utke, Fast higher-order derivative tensors with Rapsodia, Optimization Methods Software 24 (2009), no. 1, 1–14.
- Josef Dick and Friedrich Pillichshammer, Digital nets and sequences, Cambridge University Press, Cambridge, 2010. Discrepancy theory and quasi-Monte Carlo integration. MR 2683394, DOI 10.1017/CBO9780511761188
- Michael R. Garey and David S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness. MR 519066
- 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, DOI 10.1016/j.jco.2010.04.003
- 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
- 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, DOI 10.1017/CBO9780511721571.004
- 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. MR 1651755, DOI 10.1090/S0025-5718-00-01120-0
- Andreas Griewank and Andrea Walther, On constrained optimization by adjoint based quasi-Newton methods, Optim. Methods Softw. 17 (2002), no. 5, 869–889. MR 1953823, DOI 10.1080/1055678021000060829
- —, Evaluating derivatives, second ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2008, Principles and techniques of algorithmic differentiation. MR 2454953
- Andreas Griewank and Andrea Walther, Evaluating derivatives, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2008. Principles and techniques of algorithmic differentiation. MR 2454953, DOI 10.1137/1.9780898717761
- 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)
- Fred J. Hickernell, Lattice rules: how well do they measure up?, Random and quasi-random point sets, Lect. Notes Stat., vol. 138, Springer, New York, 1998, pp. 109–166. MR 1662841, DOI 10.1007/978-1-4612-1702-2_{3}
- 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, DOI 10.1137/070709359
- Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
- Frances Y. Kuo and Ian H. Sloan, Lifting the curse of dimensionality, Notices Amer. Math. Soc. 52 (2005), no. 11, 1320–1329. MR 2183869
- Koichi Kubota, Combinatorial computation with automatic differentiation, Advances in automatic differentiation, Lect. Notes Comput. Sci. Eng., vol. 64, Springer, Berlin, 2008, pp. 315–325. MR 2531693, DOI 10.1007/978-3-540-68942-3_{2}8
- Hernan Leovey and Andreas Griewank, Computation of optimal weights for quasi–Monte Carlo via algorithmic differentiation, In preparation (2012).
- George Marsaglia, Evaluating the normal distribution, Journal of Statistical Software 11 (2004), no. 5, 1–11.
- 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.
- 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. MR 2196999, DOI 10.1090/S0025-5718-06-01785-6
- 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, DOI 10.1137/1.9781611970081
- D. Nuyens, Fast construction of good lattice rules, PhD. Thesis, Katholieke Universiteit Leuven (2007), 903–920.
- Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Vol. 1: Linear information, EMS Tracts in Mathematics, vol. 6, European Mathematical Society (EMS), Zürich, 2008. MR 2455266, DOI 10.4171/026
- Erich Novak and Henryk Woźniakowski, 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, DOI 10.4171/084
- 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, DOI 10.1137/030601818
- Herbert John Ryser, Combinatorial mathematics, The Carus Mathematical Monographs, No. 14, Mathematical Association of America; distributed by John Wiley and Sons, Inc., New York, 1963. MR 0150048
- Xiaoqun Wang and Kai-Tai Fang, The effective dimension and quasi-Monte Carlo integration, J. Complexity 19 (2003), no. 2, 101–124. MR 1966664, DOI 10.1016/S0885-064X(03)00003-7
- 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, DOI 10.1093/imanum/drl044
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
- 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 - © Copyright 2013 American Mathematical Society
- Journal: Math. Comp. 83 (2014), 251-274
- MSC (2010): Primary 65D25, 68W30, 65D30, 65C05
- DOI: https://doi.org/10.1090/S0025-5718-2013-02717-2
- MathSciNet review: 3120589