An efficient method for the numerical evaluation of partial derivatives of arbitrary order

ABSTRACT

For any typical multivariable expression f, point a in the domain of f, and positive integer maxorder, this method produces the numerical values of all partial derivatives at a up through order maxorder. By the technique known as automatic differentiation, theoretically exact results are obtained using numerical (as opposed to symbolic) manipulation. The key ideas are a hyperpyramid data structure and a generalized Leibniz's rule. Any expression in n variables corresponds to a hyperpyramid array, in n-dimensional space, containing the numerical values of all unique partial derivatives (not wasting space on different permutations of derivatives). The arrays for simple expressions are combined by hyperpyramid operators to form the arrays for more complicated expressions. These operators are facilitated by a generalized Leibniz's rule which, given a product of multivariable functions, produces any partial derivative by forming the minimum number of products (between two lower partials) together with a product of binomial coefficients. The algorithms are described in abstract pseudo-code. A section on implementation shows how these ideas can be converted into practical and efficient programs in a typical computing environment. For any specific problem, only the expression itself would require recoding.

REFERENCES

• 1: BERZ, M. Differential algebraic description of beam dynamics to very high orders. Particle Accelerators 24, 2 (1989), 109-124.
• 2: CHRmT~A~SON, B. Automatic hessians by reverse accumulation. IMA g Numer. Anal. To appear.
• 3: J. A. Gerth , D. L. Orth, Indexing and merging in APL, ACM SIGAPL APL Quote Quad, v.18 n.2, p.156-161, Dec. 1987
• 4: GRIEWANK, A. On automatic differentiation. In Mathematical Programming: Recent Developments and Applications, M. Iri, and K. Tanabe, Eds. Kluwer, Amsterdam, 1989, 83-108.
• 5: IRI, M. Simultaneous computation of functions, partial derivatives and estimates of rounding errors--Complexity and practicality. Japan J. Appl. Math. 1, 2 (1984), 223-252.
• 6: R H F Jackson , G P McCormick, The polyadic structure of factorable function tensors with applications to high-order minimization techniques, Journal of Optimization Theory and Applications, v.51 n.1, p.63-94, Oct. 1986 [doi>10.1007/BF00938603]
• 7: H Kagiwada, Numerical derivatives and nonlinear analysis, Plenum Press, New York, NY, 1986
• 8: KALABA, R., TESFATSION, L., AND WAN~, J.-L. A finite algorithm for the exact evaluation of higher order partial derivatives of functions of many variables. J. Math. Anal. Appl. 92, 2 (1983), 552-563.
• 9: Gershon Kedem, Automatic Differentiation of Computer Programs, ACM Transactions on Mathematical Software (TOMS), v.6 n.2, p.150-165, June 1980 [doi>10.1145/355887.355890]
• 10: 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
• 11: NEmIN~ER, R.D. Automatic differentiation and APL. College Math. J. 20, 3 (May 1989), 238-251.
• 12: RALL, L.B. The arithmetic of differentiation. Math. Mag. 59, 5 (Dec. 1986), 275-282.
• 13: RALL, L. B. Automatic Differentiation: Techniques and Applications. Lecture Notes in Computer Science 120, Springer-Verlag, New York, 1981.
• 14: L B. Rall, Differentiation in PASCAL-SC: type GRADIENT, ACM Transactions on Mathematical Software (TOMS), v.10 n.2, p.161-184, June 1984 [doi>10.1145/399.418]
• 15: R. E. Wengert, A simple automatic derivative evaluation program, Communications of the ACM, v.7 n.8, p.463-464, Aug. 1964 [doi>10.1145/355586.364791]
• 16: Anthony S. Wexler, An algorithm for exact evaluation of multivariate functions and their derivatives to any order, Computational Statistics & Data Analysis, v.6 n.1, p.1-6, Jan. 1988 [doi>10.1016/0167-9473(88)90058-8]
• 17: Anthony S. Wexler, Automatic evaluation of derivatives, Applied Mathematics and Computation, v.24 n.1, p.19-46, Oct. 1987 [doi>10.1016/0096-3003(87)90028-2]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis; Efficiency

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Nonalgebraic algorithms

General Terms:
Algorithms, Performance

Keywords:
automatic differentiation, data structure, high order derivatives, partial derivatives