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 variables by fixing a direction in . 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 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.

**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).

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

Email:
rineidinger@davidson.edu

DOI:
http://dx.doi.org/10.1090/S0025-5718-04-01657-6

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