Automatic
Differentiation: Origin and References
By Harley Flanders
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)]m
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
RM
→ RN
→ R. U = F•G
(domains open subsets actually)
Third, the special case where N = M + 1 and U(x) =
G(x, φ(x)), where
φ
RM
→ 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.