## Directions for computing truncated multivariate Taylor series

HTML articles powered by AMS MathViewer

- by Richard D. Neidinger PDF
- Math. Comp.
**74**(2005), 321-340 Request permission

## 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

- Martin Berz,
*Differential algebraic description of beam dynamics to very high orders*, Particle Accelerators**24**(1989), 109-124. - 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. - Mariano Gasca and Thomas Sauer,
*Polynomial interpolation in several variables*, Adv. Comput. Math.**12**(2000), no. 4, 377–410. Multivariate polynomial interpolation. MR**1768957**, DOI 10.1023/A:1018981505752 - Andreas Griewank,
*Evaluating derivatives*, Frontiers in Applied Mathematics, vol. 19, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000. Principles and techniques of algorithmic differentiation. MR**1753583** - 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 - R. B. Guenther and E. L. Roetman,
*Some observations on interpolation in higher dimensions*, Math. Comp.**24**(1970), 517–522. MR**275631**, DOI 10.1090/S0025-5718-1970-0275631-1 - Eugene Isaacson and Herbert Bishop Keller,
*Analysis of numerical methods*, John Wiley & Sons, Inc., New York-London-Sydney, 1966. MR**0201039** - Saunders MacLane and O. F. G. Schilling,
*Infinite number fields with Noether ideal theories*, Amer. J. Math.**61**(1939), 771–782. MR**19**, DOI 10.2307/2371335 - David Kincaid and Ward Cheney,
*Numerical analysis*, 2nd ed., Brooks/Cole Publishing Co., Pacific Grove, CA, 1996. Mathematics of scientific computing. MR**1388777** - Ramon E. Moore,
*Methods and applications of interval analysis*, SIAM Studies in Applied Mathematics, vol. 2, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa., 1979. MR**551212** - Richard D. Neidinger,
*An efficient method for the numerical evaluation of partial derivatives of arbitrary order*, ACM Trans. Math. Software**18**(1992), no. 2, 159–173. MR**1167887**, DOI 10.1145/146847.146924 - Richard D. Neidinger,
*Computing Multivariable Taylor Series to Arbitrary Order*, APL Quote Quad**25**(1995), 134-144. - Louis B. Rall,
*Point and interval differentiation arithmetics*, Automatic differentiation of algorithms (Breckenridge, CO, 1991) SIAM, Philadelphia, PA, 1991, pp. 17–24. MR**1143786** - Thomas Sauer,
*Computational aspects of multivariate polynomial interpolation*, Adv. Comput. Math.**3**(1995), no. 3, 219–237. MR**1325032**, DOI 10.1007/BF02432000 - A. N. Shevchenko and V. N. Rokityanskaya,
*On the automatic differentiation of functions of several variables*, Kibernet. Sistem. Anal.**5**(1996), 139–158, 189 (Russian, with English and Ukrainian summaries); English transl., Cybernet. Systems Anal.**32**(1996), no. 5, 709–724 (1997). MR**1434935**, DOI 10.1007/BF02367774 - Charles Hopkins,
*Rings with minimal condition for left ideals*, Ann. of Math. (2)**40**(1939), 712–730. MR**12**, DOI 10.2307/1968951 - Thomas Sauer and Yuan Xu,
*On multivariate Lagrange interpolation*, Math. Comp.**64**(1995), no. 211, 1147–1170. MR**1297477**, DOI 10.1090/S0025-5718-1995-1297477-5 - I. Tsukanov and M. Hall,
*Data Structure and Algorithms for Fast Automatic Differentiation*, Preliminary Draft (2001).

## Additional Information

**Richard D. Neidinger**- Affiliation: Department of Mathematics, Davidson College, Box 7002, Davidson, North Carolina 28035
- Email: rineidinger@davidson.edu
- Received by editor(s): May 28, 2002
- Received by editor(s) in revised form: June 10, 2003
- Published electronically: May 17, 2004
- © Copyright 2004 American Mathematical Society
- Journal: Math. Comp.
**74**(2005), 321-340 - MSC (2000): Primary 65D25, 65D05, 41A05, 41A63, 65Y20
- DOI: https://doi.org/10.1090/S0025-5718-04-01657-6
- MathSciNet review: 2085414