Computing multivariable Taylor series to arbitrary order

ABSTRACT

Automatic differentiation, manipulating numerical vectors of coefficients, is the efficient way to compute multivariable Taylor series. This does not require symbolic differentiation or numerical approximation but uses exact formulas applied to numerical arrays. Arrays of Taylor series coefficients of any elementary function can be built-up, as the array for each component (combination or function) is a combination of its argument arrays. The functions TIMES and EXP display the algorithmic ideas that enable all of the other standard functions. We study the interesting recursive formulas for these combinations, the resulting algorithms, and the implementation in APL. To handle all coefficients in n variables up to order m, the arrays are hyper-pyramid data structures, considered conceptually as n-dimensional but implemented as one-dimensional arrays. Unlike previous work, this implementation does not require huge arrays for binomial coefficients and indirect referencing. This APL*PLUS III implementation loops through one nested reference array and takes sub-arrays from another for a practical solution to this problem that can make tremendous demands on time and space.

REFERENCES

• 1: Berz, M. Differential algebraic description of beam dynamics to very high orders. Particle Accelerators, 24 (2), 1989, 109-124.
• 2: Bischof, C., Corliss, G., and Griewank, A. Structured second- and higher-order derivatives through univariate Taylor series. Optimization Methods and Software, 2, 1993, 211-232.
• 3: Christianson, B. Reverse accumulation and accurate rounding error estimates for Taylor series coefficients. Optimization Methods and Software, 1 (1), 1992, 81-94.
• 4: Juedes, D.W. A taxonomy of automatic differentiation tools. Automatic Differentiation of A Igorithms, Edited by Griewank and Corliss, SIAM, Philadelphia, 1991.
• 5: Kalman, D. and Lindell, R. A recursive approach to multivariate automatic differentiation. Preprint.
• 6: Ramon E. Moore , Fritz Bierbaum, Methods and Applications of Interval Analysis (SIAM Studies in Applied and Numerical Mathematics) (Siam Studies in Applied Mathematics, 2.), Soc for Industrial & Applied Math, 1979
• 7: Neidinger, R.D. Automatic differentiation and APL. College Mathematics J., 20 (3), May 1989, 238-251.
• 8: R. D. Neidinger, An APL approach to differential calculus yields a powerful tool, Conference proceedings on APL as a tool of thought, p.285-288, July 1989, New York City, New York, United States
• 9: Richard D. Neidinger, Differential equations are recurrence relations in APL, ACM SIGAPL APL Quote Quad, v.23 n.1, p.165-174, July 1992
• 10: Richard D. Neidinger, An efficient method for the numerical evaluation of partial derivatives of arbitrary order, ACM Transactions on Mathematical Software (TOMS), v.18 n.2, p.159-173, June 1992 [doi>10.1145/146847.146924]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: APL

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Functional constructs

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Languages, Theory

Keywords:
Taylor series, automatic differentiation, data structure, nested arrays, numerical method, partial derivatives