Mathematics of Computation

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



Directions for computing truncated multivariate Taylor series

Author: Richard D. Neidinger
Journal: Math. Comp. 74 (2005), 321-340
MSC (2000): Primary 65D25, 65D05, 41A05, 41A63, 65Y20
Published electronically: May 17, 2004
MathSciNet review: 2085414
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Efficient recurrence relations for computing arbitrary-order Taylor coefficients for any univariate function can be directly applied to a function of $n$ variables by fixing a direction in $\mathbb{R} ^{n}$. After a sequence of directions, the multivariate Taylor coefficients or partial derivatives can be reconstructed or ``interpolated''. The sequence of univariate calculations is more efficient than multivariate methods, although previous work indicates a space cost for this savings and significant cost for the reconstruction. We completely eliminate this space cost and develop a much more efficient algorithm to perform the reconstruction. By appropriate choice of directions, the reconstruction reduces to a sequence of Lagrange polynomial interpolation problems in $\mathbb{R} ^{n-1}$ for which a divided difference algorithm computes the coefficients of a Newton form. Another algorithm collects like terms from the Newton form and returns the desired multivariate coefficients.

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

  • 1. Martin Berz, Differential algebraic description of beam dynamics to very high orders, Particle Accelerators 24 (1989), 109-124.
  • 2. Christian H. Bischof, George F. Corliss, and Andreas Griewank, Structured second- and higher-order derivatives through univariate Taylor series, Optimization Methods and Software 2 (1993), 211-232.
  • 3. Mariano Gasca and Thomas Sauer, Polynomial interpolation in several variables, Advances in Computational Math. 12 (2000), 377-410. MR 2001d:41010
  • 4. Andreas Griewank, Evaluating Derivatives, SIAM, Philadelphia, 2000. MR 2001b:65003
  • 5. Andreas Griewank, Jean Utke, and Andrea Walther, Evaluating higher derivative tensors by forward propagation of univariate Taylor series, Mathematics of Computation 69 (2000), 1117-1130. MR 2000j:65033
  • 6. R.B. Guenther and E.L. Roetman, Some observations on interpolation in higher dimensions, Mathematics of Computation 24 (1970), 517-522. MR 43:1384
  • 7. Eugene Isaacson and Herbert B. Keller, Analysis of Numerical Methods, Wiley, New York, 1966. MR 34:924
  • 8. Kaiser S. Kunz, Numerical Analysis, McGraw-Hill, New York, 1957. MR 19:460c
  • 9. David Kincaid and Ward Cheney, Numerical Analysis, Second Edition, Brooks/Cole, Pacific Grove, CA, 1996. MR 97g:65003
  • 10. Ramon E. Moore, Methods and Applications of Interval Analysis, SIAM, Philadelphia, 1979. MR 81b:65040
  • 11. Richard D. Neidinger, An efficient method for the numerical evaluation of partial derivatives of arbitrary order, ACM Trans. Math. Software 18 (1992), 159-173. MR 93b:65040
  • 12. Richard D. Neidinger, Computing Multivariable Taylor Series to Arbitrary Order, APL Quote Quad 25 (1995), 134-144.
  • 13. Louis B. Rall, Point and interval differentiation arithmetics, in Automatic Differentiation of Algorithms, A. Griewank and G. F. Corliss, editors, SIAM, Philadelphia, 1991, 17-24. MR 92k:65031
  • 14. Thomas Sauer, Computational aspects of multivariate polynomial interpolation, Advances in Computational Math. 3 (1995), 219-237. MR 95k:65012
  • 15. A.N. Shevchenko and V.N. Rokityanskaya, Automatic differentiation of functions of many variables, Cybernetics and Systems Analysis 32 (1996), 709-724. MR 98f:65004
  • 16. J.F. Steffensen, Interpolation, Second Edition, Chelsea Publishing, New York, 1950 (First Edition, 1927). MR 12:164d
  • 17. Thomas Sauer and Yuan Xu, On multivariate Lagrange interpolation, Mathematics of Computation 64 (1995), 1147-1170. MR 95j:41051
  • 18. I. Tsukanov and M. Hall, Data Structure and Algorithms for Fast Automatic Differentiation, Preliminary Draft (2001).

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65D25, 65D05, 41A05, 41A63, 65Y20

Retrieve articles in all journals with MSC (2000): 65D25, 65D05, 41A05, 41A63, 65Y20

Additional Information

Richard D. Neidinger
Affiliation: Department of Mathematics, Davidson College, Box 7002, Davidson, North Carolina 28035

Keywords: Automatic differentiation, multivariate, polynomial interpolation, higher-order derivatives, divided difference
Received by editor(s): May 28, 2002
Received by editor(s) in revised form: June 10, 2003
Published electronically: May 17, 2004
Article copyright: © Copyright 2004 American Mathematical Society