Automatic
Differentiation: Origin and References

By Harley Flanders

Feb. 2002

Feb. 2002

A) Pre-History

1) Arbogast, Loius Francois Antoine, Du Calcul des De'rivations, Strasbourg, 1800, xxiv + 404

The book is wordy, and has long, drawn-out formulas, because of the style, notation, and printing conventions of that time. Each topic has a preliminary discussion, statement of a specific problem, and its solution. The problems ask for the power series expansion of a function given in terms of other functions with known expansions.

The following list of problems will give the flavor (my notation):

Sect. 12, pp.6... Log[F(x)]

Sect. 14, pp. 10... Exp[F(x)]

Sect. 16, pp. 11... Sin[F(x)]

Sect. 19, pp 13... First mention of the general case G[F(x)]

Sect. 31, pp. 26... [F(x)]

Sect. 32, pp. 27... Cos[F(x)]

Sect. 34, pp. 28... Tan[F(x)], Cot[F(x)], ArcSin[F(x)], ArcCos[F(x)], Log Sin[F(x)], Log Cos[F(x)], and working towards the general case.

Sect. 52, pp. 43... The general Faa de Bruno formula!

Sect. 131, pp. 105... P(x, y) a polynomial. Expand F[P(x, y)].

Sect. 169, pp. 130... F[P(x, y, z)]

Sect. 173, pp 142... P(x, y)*Q(x, y)

Sect. 182, pp. 146... F[P(x, y)]*G[Q(x, y)]

Sect. 190, pp. 152... F[P(x), Q(x)]

Sect. 193, pp. 154... F[P(x, y), Q(x, y)]

Here F, P, Q are polynomials, but clearly Arbogast knows that to do the general function, it suffices to do polynomials.

Arbogast leaves no stone unturned. The latter sections of the book deal with Taylor series whose coefficients satisfy a linear difference equation.

2) (Quote from Constantine and Savits, below; see also Lukacs.)

"According to Lukacs ... the need for such a formula was explicitly mentioned as early as 1810 in Lacroix's treatise on calculus." How could Lacroix not know in 1810 about Argbast's book of 1800? Forgotten so soon? I think the explanation is that Arbogast was published in Strasbourg, whereas Lacroix was published in Paris. Distances were longer in those days!

3) Faa de Bruno, Note sur une nouvelle formule de calcul differentiel, Quart. J. Pure Appl. Math. 1 (1857) 359-360.

B) Recent history: Faa Di Bruno formula

4) G. M. Constantine and T. R. Savits, A multivariate Faa di Bruno formula with applications, Trans. Amer. Math. Soc. 348 (1966) 503-520.

5) J. Dieudonne, Foundations of Modern Analysis, Academic Press, 1969, 149, 429. (I have not checked this.)

6) I. Hernandez Encinas and J. Munoz Masque, A short proof of Faa di Bruno's formula, to appear.

7) G. Falqui, C. Reina, and A. Zampa, Krichever maps, Faà di Bruno polynomials, and cohomology in KP theories, Lett. Math. Phys. 42 (1997) no. 4, 349-361.

8) H. Flanders, Automatic differentiation of composite functions, Automatic Differentiation of Algorithms, SIAM, Philadelphia,

1991, pp. 95-99.

9) H. Flanders, From Ford to Faa, Amer Math Monthly 108 (2001) 559-561.

10) L. E. Fraenkel, Formulas for high derivatives of composite functions, Math. Proc. Cambridge Philos. Soc, 83 (1978), 159-165.

Fraenkel treats the multvariable Faa for sevarel cases. First, in considerable generality, for mappings between Banach spaces. Second, for

F G

R

(domains open subsets actually)

Third, the special case where N = M + 1 and U(x) = G(x, φ(x)), where

φ

R

Fraenkel attributes the genesis of the second case (which is to subject of the paper under review) to Dieudonne [7], but says that Dieudonne does not give the Faa formula explicitly.

Fraenkel's notation is somewhat cumbersome, and his proof is unduly complicated and hard to follow.

11) I. J. Good, Annals of Math. Stat. 32 (1961). The Faa formula for several variables in stated in a concise notation at the top of the page, and a very brief proof is sketched. I think it would take a lot of work to fill in the details, although Good mentions the essential ingredients: Taylor's formula and the multinomial theorem.

Good mentions that Riordan [21] points out that the generalization of the one variable Faa formula to several variables "is purely a matter of notation."

12) Goursat and E. Hedrick, A Course in Mathematical Analysis, I. Ginn, Boston, 1902, p. 34, Ex. 19.

13) C. Hespel, Iterated derivatives of the output of a nonlinear dynamic system and Faa di Bruno formula, Math. Comput. Simulation 42 (1996), 641-657.

14) R. Horn and C. Johnson, Topics in Matrix Analysis, Cambridge Univ. Press, Cambridge, 1991, p. 421.

15) W. P. Johnson, A q-analogue of Faa di Bruno's formula, J. Combin. Theory, Ser. A, 76 (1996), pp. 305-314.

16) C. Jordan, Calculus of Finite Differences, Chelsea, New York, 1950, pp. 33-34.

17) M. Kawagishi, The multi-dimensional Faa di Bruno formula, Rep. Res. Inst. Sci. Technol. Nihon Univ. 45 (1999) 1-6.

18) D A Knuth. The Art of Computer Programming, 3/e, Vol. 1, Fundamental Algorithms. P. 52, Exercise 21, gives Arbogast's formula for one variable. The solution, pp. 481-483, begins with a brief proof using a recursion relation. Then it continues with a combinatorial proof using partitions.

19) M. McKiernen, On the n-th derivative of composite functions, Amer. Math. Monthly 63 (1956) 331-333. This was brought to my attention by B. Schweizer, as was [10]. It contains a short derivation of the single variable Faà.

20) E. Lucas, Applications of Faà di Bruno's formula in mathematical statistics, Amer. Math. Monthly 62 (1955) 340-348.

21) R. L. Mishkov, Generalization of the formula of Faà di Bruno for a composite function with a vector argument, Internat. J. Math. & Math. Sci. 24 (2000) n. 7, 481-491.

22) D. Pandres, Jr., On higher orderer differentiation, Amer. Math. Monthly 64 (1957) 566. I haven't looked at this.

23) J. Riordan, Derivatives of composite functions, Bull. Amer. Math. Soc, 52 (1946), 664-667.

24) S. Roman, Faà de Bruno's formula, Amer Math Monthly 87 (1980), 805-809.

25) F. Ronga, A new look at Faa de Bruno's formula, Proc. Sympos. Pure Math 40:2 (1981) 423-431.

26) H. S. Wall, Bull. Amer. Math. Soc. 44, (1938), 395-398. This is Knuth's reference for the partition proof. I have not looked at it.

27) X. Zhao and T. Wang, Some strange identities related to Faa di Bruno formula, J.Math. Res. Exposition 21 (2001) no. 2, 215-218.

C) Automatic Differentiation (AD)

28) A. Griewank and G. Corliss ed, Automatic Diffderentiation of Algorithms: Theory, Implementation, and Application, SIAM 1991.

29) C. H. Bischof, A. Griewank, and P. M. Khademi ed, Workshop Report on First Theory Institute on Computational Differentiation, Argonne Nat'l. Lab., 1993.

30) M. Berz, C. Bischof, G. Corlis, and A. Griewank ed, Computational Differentiation: Techniques, Applications, and Tools, SIAM 1996

31) A. Griewank, Evaluatimg Derivatives: Principles and Techniques of Algorithmic Differentiation, SIAM, 2000.

32) G. Corliss, et al ed, Algorithmic Differentiation Algorithms: From Simulation to Optimization, Springer 2002.