🚀 go-pugleaf

A few days ago I asked for information on software to do
"automatic differentiation".  For the uninitiated, this is a way to
get exact derivatives of any order without needing to analytically
evaluate the formulas for the derivatives.  I think of this as a great
advance for anyone who does nonlinear maximisation, for example.  With
such code at hand, we could fluently get gradiants and hessians of
complex objective functions without needing to approximate the hessian
(as most algorithms do).  We could do even better by going beyond the
second derivative: there is a paper by Kalaba et al on doing just that
(pointers are at EOF).

It looks like the best way to do automatic differentiation is to use
C++.  What follows gives you some pointers to software available.
It looks like the people who write matrix libraries in C++ have not
talked a lot with the people who do automatic differentiation in C++
:-)  Please do so!

I'm grateful to all who helped me on this.

        -ans.

---------------------------------------------------------------------------

From epperly@antares.mcs.anl.gov Mon Jul 20 11:44:01 1992

I have forwarded a copy of your post to Dr. Andreas
Griewank(griewank@antares.mcs.anl.gov) of Argonne National Laboratory.
He has a package called Adol-C which is a C++ library for doing
automatic differentiation.  I don't how he plans to distribute it;
otherwise, I would just mail you a copy.  I think that he wants to
make it available to researchers, but right now he is on vacation
until Aug. 29.

Here is a reference for another possible source.  I am going to be
verbose here in case you need this information.

Title: Automatic Differentiation of Algorithms: Theory, Implementation,
	and Application
Edited by	Andreas Griewank, Argonne National Laboratory
		George F. Corliss, Marquette University
Publisher: SIAM
ISBN 0-89871-284-X

Proceedings of the first SIAM Workshop on Automatic Differentian, held
in Breckenridge, Colorado, January 6-8, 1991.

Article 22: MXYZPTLK: A C++ Hacker's Implementation of Automatic
	Differentiation
Author: Leo Michelotti
	Fermilab, P.O. Box 500, Batavia, IL 60510

The article says that the source and user's guide are available on
request.  This is another possible source.

				Tom
--
Tom Epperly	University of Wisconsin-Madison		Chemical Engineering
Visiting	Argonne National Laboratory(summer `92)	(708) 252-7218
		epperly@osnome.che.wisc.edu
---------------------------------------------------------------------------

From vaniwaar@antares.mcs.anl.gov Mon Jul 20 12:04:02 1992

	There has been quite of bit of work out here at Argonne
National Laboratories in this area.  One package Adol-C has been
developed by my supervisor Andreas Griewank but I am unsure of his  
distribuion methods and will forward your message to him. Another  
package that is out there is called MXYZPTLK which was developed by
Leo Michelotti at Fermi labs just North of here. However, this
package only impliments the forward method of Automatic
differentiation whereas Adol-c does both forward and reverse.
	I am presently working on a new version of Adol-C which
should be much faster, more flexible and also more user friendly.  It
is called Radol-C and should be `finished' in the next few weeks.
	It is nice to hear of your interest.  If you have any
questions, feel free to send them on and I will try my best to answer
them.  Also, there is a book out called "The Automatic
Differentiation of Functions and Algorithms" which is published by
SIAM, edited by Andreas Griewank and George F Corliss and is the
proceedings from the conference that was held in
Breckenridge, CO.

>Thanks for your info.  I hope your Radol-C package will be
>widely available.  Does it do vector/matrix expressions?
>E.g. if I write a expression like
>
>L = Phi(-beta'x/sigma)
>
>where beta is a vector, x is a vector, sigma is a scalar, Phi
>is the cumulative normal density.  Would he be able to differentiate
>L correctly?
>
>        -ans.

My package will work by simply doing a global substitution from
double to vareal.  Then, you will need to identify what are the
independant and dependant variables.  Then, add a statement to
compute the derivatives.  Now, I am not sure what the cumulative
normal density is but, assuming that it is a functional, the code
would (hopefully) look similar to the following pseudo code:


#include "vareal.h"
main()
{
vareal x[n];
vareal x[gradient];
vareal L;
vareal y;
int i;
vareal beta[n];
vareal sigma;
for (i=0;i<n;++i) x[i].infect()		//this identifies x[i] as  
					//an independant
L = Phi(-beta*x/sigma);			//assumes * overloaded as dot 

					//product
L =>> y					//identfies y as the 	 
					//dependant
reverse(gradient);
for (i=0;i<n;++i) cout<<gradient[i];
}


This assumes that Phi(x) has been defined elsewhere and that it's
source code has been modified with the global double-vareal
substitution.  Also, the code for the * operator must also be
modified with the double-vareal substitution.

Again, this is in the preliminary stages.  I hope to have the reverse
method running by the end of the week but that is not definate.
I also am not sure what the lab's policies are regarding distributing
software and I will look into this.  As far as I am concerned, this
will be purely academic software.

--Ron

---------------------------------------------------------------------------

From dsf@palm.cray.com Mon Jul 20 10:13:10 1992
From: dsf@palm.cray.com (Dan Frankowski)

I don't have any references for a public domain C++ library.  However,
the book "Data Abstraction and Object-Oriented Programming in C++" by
Gorlen, Orlow, and Plexico (published by John Wiley & Sons) has a
partway implemented version for functions and matrices of functions
on pages 90-97.

They also reference

L. B. Rall, "The Arithmetic of Differentiation", Mathematics Magazine,
        59(5), 275-282 (1986).

L. B. Rall, "Differentiation in Pascal-SC: Type Gradient", ACM
        Transactions on Software Engineering, SE-1(4), 364-370 (1975).

According to the book, the first paper describes the math, the second
describes an implementation in "a computer language that supports data
abstraction and operator overloading."

If any of this helps you, please post it back on the net.

Dan Frankowski            dsf@teak.cray.com     (612) 683-5099

---------------------------------------------------------------------------

That is the end of email and replies to my posting.
Here is a bibliography on automatic differentiation, from my (
i.e., ANS) .bib:

@techreport{Garcia91,
	author = 	{Oscar Garcia},
	title = 	{Experience with automatic differentiation in estimating forest growth model parameters},
	institution = 	{Forest Research Institute},
	month = 	{March},
	year = 		1991,
	address = 	{Rotorua, New Zealand},
}
@article{Jerrell90,
	author = 	{Max E. Jerrell},
	title = 	{Automatic differentiation in {C++}},
	journal = 	JOOP,
	pages = 	{17-24},
	month = 	{May/June},
	year = 		1990,
	annote = 	{implementation of automatic derivatives in C++; based on Kalaba's "Table method"}
}
@techreport{KalabaTesfatsion89b,
	author = 	{Robert Kalaba and Leigh Tesfatsion},
	title = 	{Nonlocal Automated Sensitivity Analysis},
	institution = 	{USC},
	month = 	{July},
	year = 		1989,
	number = 	{M8911},
	annote = 	{algorithm, ODE oriented, automatic evaluation of derivatives}
}
@article{KalabaTesfatsionWang,
	author = 	{Robert Kalaba and Leigh Tesfatsion and Jone-Lin Wang},
	title = 	{Local and Nonlocal Comparative Static Analysis of Economic Systems},
	journal = 	{Applied Mathematics and Computation},
	volume = 	9,
	pages = 	{227-234},
	year = 		1981,
	annote = 	{automatic numerical evaluation of multipliers}
}
@article{KalabaTishler84a,
	author = 	{Robert Kalaba and A. Tishler},
	title = 	{Generalized newton algorithm to minimize a function with many variables using computer-evaluated exact higher-order derivatives},
	journal = 	JOTA,
	volume = 	42,
	number = 	3,
	pages = 	{383-395},
	month = 	{March},
	year = 		1984,
	annote = 	{optimisation algorithms, generalised newton algorithm, table algorithm, higher-order derivatives, numerical derivatives, automatic differentiation}
}
@article{KalabaTishler84b,
	author = 	{Robert Kalaba and Asher Tishler},
	title = 	{Automatic derivative evaluation in the optimisation of nonlinear models},
	journal = 	RES,
	volume = 	{??},
	number = 	{??},
	pages = 	{653-660},
	month = 	{??},
	year = 		{1984(?)},
	annote = 	{the table method; numerical (NOT) differentiation}
}
@article{Rall84,
	author = 	{L. B. Rall},
	title = 	{Differentiation in {Pascal-SC: Type GRADIENT}},
	journal = 	TOMS,
	volume = 	10,
	number = 	2,
	pages = 	{161-184},
	month = 	{June},
	year = 		1984,
	annote = 	{automatic derivatives, gradients, jacobians, sensitivity analysis}
}
@article{Rall86,
	author = 	{L. B. Rall},
	title = 	{The Arithmetic of Differentiation},
	journal = 	{Mathematics Magazine},
	volume = 	59,
	number = 	5,
	pages = 	{275-282},
	month = 	{December},
	year = 		1986,
	annote = 	{very mathematical look at automatic derivatives}
}
@article{Wengert64,
	author = 	{R. E. Wengert},
	title = 	{A simple automatic derivative evaluation program},
	journal = 	CACM,
	volume = 	7,
	number = 	8,
	pages = 	{463-464},
	month = 	{August},
	year = 		1964,
	annote = 	{automatic differentiation}
}

-- 
Ajay Shah, (213)749-8133, ajayshah@usc.edu