From e0c6872cf40896c7be36b11dcc744620f10adf1d Mon Sep 17 00:00:00 2001 From: Norbert Preining Date: Mon, 2 Sep 2019 13:46:59 +0900 Subject: Initial commit --- macros/latex/contrib/maple/MTNarticle.tex | 746 ++++++++++++++++++++++++++++++ macros/latex/contrib/maple/README | 131 ++++++ macros/latex/contrib/maple/mtn.cls | 173 +++++++ 3 files changed, 1050 insertions(+) create mode 100644 macros/latex/contrib/maple/MTNarticle.tex create mode 100644 macros/latex/contrib/maple/README create mode 100644 macros/latex/contrib/maple/mtn.cls (limited to 'macros/latex/contrib/maple') diff --git a/macros/latex/contrib/maple/MTNarticle.tex b/macros/latex/contrib/maple/MTNarticle.tex new file mode 100644 index 0000000000..0f28aee0f8 --- /dev/null +++ b/macros/latex/contrib/maple/MTNarticle.tex @@ -0,0 +1,746 @@ +\documentclass[11pt,dvips]{mtn} +\usepackage{palatino} +\begin{document} +% +\title{The D Operator and Algorithmic \\ Differentiation} +\author{Michael Monagan +\thanks{Informatik E.T.H., Z\"{u}rich, Switzerland. monagan@inf.ethz.ch} +\and J. S. Devitt\thanks{Faculty of Mathematics, University of Waterloo, +Canada, jsdevitt@daisy.uwaterloo.ca} +} +\shorttitle{D Operator} +\maketitle + +\section{Introduction} +In this article we would like to inform our readers and users about +the development of the \mexpr{D} operator in Maple. +As with many major tasks in system development, getting something like +this nicely integrated into a system, and working correctly, +notationally correct, and making it easy to use, requires the design +of new facilities and changes to many parts of the system. + +Although ``differentiation'' is often regarded as a +relatively simple task for a computer algebra system, it turns +out that this is not actually the case. +A paper by Stanly Steinberg and Michael Wester {\cite {MUC84}} presented +at the 1984 Macsyma Users Conference pointed out problems with +the differentiation facility in the computer algebra systems available +at that time. In particular, Maple and other systems could not distinguish +correctly between total and partial derivatives. + +Operators were first introduced into Maple in version 4.2 +by Gaston Gonnet {\cite {OPERATORS}}. The addition of the \mexpr{D} operator +addressed the distinction of total and partial derivatives, and also +a representation of the derivative of a function evaluated at a +point (for example, $y'(0)$ by \mexpr{D(y)(0)}). +Partial derivatives and the ability to +apply the chain rule to an unknown function were added in Maple V. +Presently the \mexpr{D} operator is being extended to address the +problem of algorithmic differentiation, that is, to differentiate +Maple procedures. + +In this article we follow the development of the \mexpr{D} operator +by way of examples discussing some of details and system design +issues as we go. + +\section{Functions -- Expressions or Mappings?} + +Users will find two facilities for differentiation in Maple, +the \mexpr{diff} procedure, and the \mexpr{D} procedure. + +The \mexpr{diff} procedure takes as input what Maple calls +an {\em expression} or a {\em formula} which is a function of +zero of more variables ($x_1, x_2, \ldots x_n$) which appear explicitly +in the expression. +It computes the partial derivative of the formula with respect to +a given variable. + +The \mexpr{D} procedure in Maple (often called the +\mexpr{D} operator) takes as input a function which is +a mapping from $R^N \rightarrow R$. In Maple this is called an +{\em operator} or a {\em mapping}. +For example, $sin(x)$ is an expression in $x$ but $sin$ by itself is a +mapping from $R \rightarrow R$. +Another mapping in Maple is $sin+cos^2$. +A {\em mapping} can always be applied to an argument. +For example, given the mapping + +\begin{mapleinput} +F := sin+cos^2; +\end{mapleinput} +\begin{maplelatex} +\[ +{F} := {\rm sin} + {\rm cos}^{2} +\] +\end{maplelatex} +if we apply it to a number we get a number and if we apply +it to a formula we get a formula, e.g. + +\begin{mapleinput} +F(1.0); +\end{mapleinput} +\begin{maplelatex} +\[ +1.133397567 +\] +\end{maplelatex} +\begin{mapleinput} +F(Pi/3); +\end{mapleinput} +\begin{maplelatex} +\[ +{\displaystyle \frac {1}{2}}\,\sqrt {3} + {\displaystyle \frac {1 +}{4}} +\] +\end{maplelatex} +\begin{mapleinput} +F(x); +\end{mapleinput} +\begin{maplelatex} +\[ +{\rm sin}(\,{x}\,) + {\rm cos}(\,{x}\,)^{2} +\] +\end{maplelatex} + +Strictly speaking, +Maple would call both the formula $sin(x) + cos(x)^2$ and +the mapping $sin + cos^2$ expressions. +Any distinction between the two comes from how we use them. +Mappings are mappings because our intention is +to {\em apply} them to arguments, while formulae are the +result of applying mappings to their arguments. +Throughout this article we will call the former +mappings and the latter formulae. +Thus the \mexpr{diff} procedure differentiates a formula and returns +a formula. The \mexpr{D} operator differentiates a mapping +and returns a mapping. Compare + +\begin{mapleinput} +diff( sin(x)^2, x ); +\end{mapleinput} +\begin{maplelatex} +\[ +2\,{\rm sin}(\,{x}\,)\,{\rm cos}(\,{x}\,) +\] +\end{maplelatex} +\begin{mapleinput} +D(sin^2); +\end{mapleinput} +\begin{maplelatex} +\[ +2\,{\rm cos}\,{\rm sin} +\] +\end{maplelatex} + +Note, for mappings, functional composition is represented +explicitly by use of the \mexpr{@} operator, and repeated composition +is represented by the \mexpr{@@} operator. Compare + +\begin{mapleinput} +diff( sin(cos(x)), x ); +\end{mapleinput} +\begin{maplelatex} +\[ + - {\rm cos}(\,{\rm cos}(\,{x}\,)\,)\,{\rm sin}(\,{x}\,) +\] +\end{maplelatex} +\begin{mapleinput} +D( sin@cos ); +\end{mapleinput} +\begin{maplelatex} +\[ + - {\rm cos}^{(\,2\,)}\,{\rm sin} +\] +\end{maplelatex} + +\section{Derivatives of Unknown Functions} + +As well as being able to compute with known functions, like +$\sin, \cos, \exp, \ln$, etc., Maple has always supported the ability to +compute with unknown functions. In the following examples +of partial and repeated partial differentiation of an unknown function $f$, the +notation \mexpr{D[i](f)} means the partial derivative of $f$ with +respect to the $i^{th}$ argument. + +\begin{mapleinput} +diff(f(x,y),y); +\end{mapleinput} +\begin{maplelatex} +\[ +{\frac {{ \partial}}{{ \partial}{y}}}\,{\rm f}(\,{x}, {y}\,) +\] +\end{maplelatex} +\begin{mapleinput} +D[2](f); +\end{mapleinput} +\begin{maplettyout} +\end{maplettyout} +\begin{maplelatex} +\[ +{{D}_{2}}(\,{f}\,) +\] +\end{maplelatex} +\begin{mapleinput} +diff(f(x,y),x,y,x) = diff(diff(diff(f(x,y),x),y),x); +\end{mapleinput} +\begin{maplelatex} +\[ +{\frac {{ \partial}^{3}}{{ \partial}{y}\,{ \partial}{x}^{2}}}\, +{\rm f}(\,{x}, {y}\,)={\frac {{ \partial}^{3}}{{ \partial}{y}\,{ +\partial}{x}^{2}}}\,{\rm f}(\,{x}, {y}\,) +\] +\end{maplelatex} +\begin{mapleinput} +D[1,2,1](f) = D[1](D[2](D[1](f))); +\end{mapleinput} +\begin{maplettyout} +\end{maplettyout} +\begin{maplelatex} +\[ +{{D}_{1, 1, 2}}(\,{f}\,)={{D}_{1, 1, 2}}(\,{f}\,) +\] +\end{maplelatex} + +In Maple, the \mexpr{D} operator is an ordinary Maple procedure. +When we input \mexpr{D[1,2,1](f)}, what happens? +If \mexpr{D} was an array or table then the entry \mexpr{D[1,2,1]} +would be applied to $f$. In the case of a procedure, what happens +is that it is called with the given arguments and inside +the procedure the $procname$ variable's value will be the subscript. +In our example, \mexpr{D} is called with $f$ as an argument +and the value of $procname$ will be \mexpr{D[1,2,1]}. +The \mexpr{D} code sorts the indices (assumes partial derivatives commute) +and returns \mexpr{D[1,1,2](f)} unevaluated. +This subscripted function calling facility is new in Maple V. +It is also used for the log function for different bases. +For example, \mexpr{log[b](x)} means $\log _b x$ i.e. logarithm base $b$ of $x$. + +One of the main reasons why Maple has a \mexpr{D} operator as well +as a \mexpr{diff} procedure is because it is not possible to specify $y'(0)$ using +\mexpr{diff}. Maple users reading this article might think of +using the Maple \mexpr{subs} procedure e.g. \mexpr{subs(x=0,diff(sin(x),x))}. +This works if Maple can actually differentiate the function +but it will not work for an unknown function $y$. +Being able to represent $y'(0)$ simply as $D(y)(0)$ motivated the +introduction of operators, in particular the \mexpr{D} operator in Maple. +This notation is used to specify the initial conditions for the +\mexpr{dsolve} procedure, which solves systems of ODE's, +replacing an earlier defunct notation $yp(0), ypp(0), \ldots$ +It is also used in series; for example, here is the +Taylor series for an unknown function $f$ to order $O(x^6)$ + +\begin{mapleinput} +taylor(f(x),x); +\end{mapleinput} +\begin{maplettyout} +\end{maplettyout} +\begin{maplelatex} +\begin{eqnarray*} +\lefteqn{{\rm f}(\,0\,) + {\rm D}(\,{f}\,)(\,0\,)\,{x} + +{\displaystyle \frac {1}{2}}\,{D}^{(\,2\,)}(\,{f}\,)(\,0\,)\,{x} +^{2} + {\displaystyle \frac {1}{6}}\,{D}^{(\,3\,)}(\,{f}\,)(\,0\, +)\,{x}^{3} + {\displaystyle \frac {1}{24}}\,{D}^{(\,4\,)}(\,{f}\, +)(\,0\,)\,{x}^{4} + } \\ + & & {\displaystyle \frac {1}{120}}\,{D}^{(\,5\,)}(\,{f}\,)(\,0\, +)\,{x}^{5} + {\rm O}(\,{x}^{6}\,)\mbox{\hspace{200pt}} +\end{eqnarray*} +\end{maplelatex} +And here is a multivariate Taylor series to third order. + +\begin{mapleinput} +readlib(mtaylor); # load the multivariate series package +\end{mapleinput} +\begin{maplelatex} +\end{maplelatex} +\begin{maplettyout} +proc() ... end + +\end{maplettyout} +\begin{mapleinput} +mtaylor(f(x,y),[x,y],3); +\end{mapleinput} +\begin{maplettyout} +\end{maplettyout} +\begin{maplelatex} +\begin{eqnarray*} +\lefteqn{{\rm f}(\,0, 0\,) + {{D}_{1}}(\,{f}\,)(\,0, 0\,)\,{x} + +{{D}_{2}}(\,{f}\,)(\,0, 0\,)\,{y} + {\displaystyle \frac {1}{2}} +\,{{D}_{1, 1}}(\,{f}\,)(\,0, 0\,)\,{x}^{2} + {x}\,{{D}_{1, 2}}(\, +{f}\,)(\,0, 0\,)\,{y}} \\ + & & \mbox{} + {\displaystyle \frac {1}{2}}\,{{D}_{2, 2}}(\,{f}\, +)(\,0, 0\,)\,{y}^{2}\mbox{\hspace{250pt}} +\end{eqnarray*} +\end{maplelatex} + +\newpage +Without use of the \mexpr{D} operator it would be difficult to apply +the chain rule to unknown functions. For example, we have + +\begin{mapleinput} +diff(f(x^2),x); +\end{mapleinput} +\begin{maplettyout} +\end{maplettyout} +\begin{maplelatex} +\[ +2\,{\rm D}(\,{f}\,)(\,{x}^{2}\,)\,{x} +\] +\end{maplelatex} +\begin{mapleinput} +diff(f(x^2,x*y),x); +\end{mapleinput} +\begin{maplettyout} +\end{maplettyout} +\begin{maplelatex} +\[ +2\,{{D}_{1}}(\,{f}\,)(\,{x}^{2}, {y}\,{x}\,)\,{x} + {{D}_{2}}(\,{ +f}\,)(\,{x}^{2}, {y}\,{x}\,)\,{y} +\] +\end{maplelatex} +\begin{mapleinput} +D(f@g); +\end{mapleinput} +\begin{maplettyout} +\end{maplettyout} +\begin{maplelatex} +\[ +{\rm D}(\,{f}\,){\rm @}{g}\,{\rm D}(\,{g}\,) +\] +\end{maplelatex} +There are distinct advantages to manipulating mappings as if +they were expressions. The following example illustrates implicit +differentiation of $y$ as a function of $x$. +Given the equation + +\begin{mapleinput} +eq := y^2*x + y^3*x^2 + y + 3*x = 0; +\end{mapleinput} +\begin{maplelatex} +\[ +{\it eq} := {y}^{2}\,{x} + {y}^{3}\,{x}^{2} + {y} + 3\,{x}=0 +\] +\end{maplelatex} +we can regard $x$ and $y$ as arbitrary mappings. Then applying +\mexpr{D} to both sides of the equation we have + +\begin{mapleinput} +map(D,eq); +\end{mapleinput} +\begin{maplettyout} +\end{maplettyout} +\begin{maplelatex} +\[ +2\,{\rm D}(\,{y}\,)\,{y}\,{x} + {y}^{2}\,{\rm D}(\,{x}\,) + 3\, +{\rm D}(\,{y}\,)\,{y}^{2}\,{x}^{2} + 2\,{y}^{3}\,{\rm D}(\,{x}\,) +\,{x} + {\rm D}(\,{y}\,) + 3\,{\rm D}(\,{x}\,)=0 +\] +\end{maplelatex} +This equation can be interpreted in many different ways. For example, +it can be solved to obtain a formula for $D(y)$ +\begin{mapleinput} +D(y) = solve(",D(y)); +\end{mapleinput} +\begin{maplettyout} +\end{maplettyout} +\begin{maplelatex} +\[ +{\rm D}(\,{y}\,)= - \,{\displaystyle \frac {{y}^{2}\,{\rm D}(\,{x +}\,) + 2\,{y}^{3}\,{\rm D}(\,{x}\,)\,{x} + 3\,{\rm D}(\,{x}\,)}{2 +\,{y}\,{x} + 3\,{y}^{2}\,{x}^{2} + 1}} +\] +\end{maplelatex} +while the interpretation that $x$ is an independent variable can +be indicated by the substitution +\begin{mapleinput} +subs(D(x)=1,"); +\end{mapleinput} +\begin{maplettyout} +\end{maplettyout} +\begin{maplelatex} +\[ +{\rm D}(\,{y}\,)= - \,{\displaystyle \frac {{y}^{2} + 2\,{y}^{3} +\,{x} + 3}{2\,{y}\,{x} + 3\,{y}^{2}\,{x}^{2} + 1}} +\] +\end{maplelatex} + +Earlier we mentioned that application of a mapping to a symbolic +variable yields a formula. And hence the identity +\mexpr{D(f)(x) = diff(f(x),x)}. For example + +\begin{mapleinput} +F := sin+cos^2; +\end{mapleinput} +\begin{maplelatex} +\[ +{F} := {\rm sin} + {\rm cos}^{2} +\] +\end{maplelatex} +\begin{mapleinput} +F(x); +\end{mapleinput} +\begin{maplelatex} +\[ +{\rm sin}(\,{x}\,) + {\rm cos}(\,{x}\,)^{2} +\] +\end{maplelatex} +\begin{mapleinput} +diff(F(x),x) - D(F)(x); +\end{mapleinput} +\begin{maplelatex} +\[ +0 +\] +\end{maplelatex} + +Given the formula, how can we get back the mapping $F$? +This is called {\em lambda abstraction} in the language of lambda calculus. +In Maple it is called \mexpr{unapply} because it +is the inverse of application, that is, it takes a formula and returns +a mapping. For example + +\begin{mapleinput} +G := unapply(F(x),x); +\end{mapleinput} +\begin{maplelatex} +\[ +{G} := {x} \rightarrow {\rm sin}(\,{x}\,) + {\rm cos}(\,{x}\,)^{2 +} +\] +\end{maplelatex} +is a mapping in the form of a Maple procedure equivalent to +\mexpr{proc(x) sin(x)+cos(x)^2 end:} except it has been +displayed using a more succinct format, +known as arrow operators. The arrow notation above is used often in algebra. +This new notation is essentially equivalent to Maple's +older angle bracket notation + +\begin{mapleinput} +; +\end{mapleinput} +\begin{maplelatex} +\[ + \langle {\rm sin}(\,{x}\,) + {\rm cos}(\,{x}\,)^{2}\,{ \mid}\,{x +} \rangle +\] +\end{maplelatex} +differing only in how the procedure is entered and displayed. + +Another notation for functions that is used often in applied mathematics +is the $F(x)=sin(x)+cos(x)^2$ notation. In Maple one might use +\mexpr{F(x):=sin(x)+cos(x)^2}, but this already has a meaning in Maple (which +unfortunately is different) and this does lead to confusion. +The meaning of \mexpr{F(x):=y} is to enter the entry $(x,y)$ in $F$'s remember +table so that when $F$ is called with the literal symbol +$x$, $y$ is returned. It is rather like making $F$ work like a table +of values. + +\section{Equivalence of Mappings} + +Notice though, that \mexpr{unapply} did not return the mapping +in the same {\em form} $F$ that we started with. +This raises another question, namely, given two mappings, how could one +test if they are the same? Users are familiar with the problem of testing +whether two formulae are the same. For example, suppose we are +given the two formulae + +\begin{mapleinput} +f1 := sin(x)+cos(x)^2: +f2 := sin(x)+cos(2*x)/2+1/2: +\end{mapleinput} + +How would we test whether $f_1 = f_2$? This is the problem of +simplification, or zero recognition. +In Maple, one would use the expand (or simplify) function as follows + +\begin{mapleinput} +expand(f1-f2); +\end{mapleinput} +\begin{maplelatex} +\[ +0 +\] +\end{maplelatex} + +In this case, expand applies the transformation $cos(2 x) = 2 cos(x)^2 - 1$ +hence recognizing that $f_1 = f_2$. +But what about mappings? + +\begin{mapleinput} +expand(eval(G)); +\end{mapleinput} +\begin{maplelatex} +\[ +{\rm sin} + {\rm cos}^{2} +\] +\end{maplelatex} + +Expand tries to write an arrow (or angle bracket) +operator as an algebraic combination of other mappings, in this case +allowing us to recognize that $F$ and $G$ are effectively +the same mapping. + +\begin{mapleinput} +expand(F-eval(G)); +\end{mapleinput} +\begin{maplelatex} +\[ +0 +\] +\end{maplelatex} + +Maple can differentiate those arrow operators too, even +in their unexpanded form. + +\begin{mapleinput} +D(G); +\end{mapleinput} +\begin{maplettyout} +\end{maplettyout} +\begin{maplelatex} +\[ +{x} \rightarrow {\rm cos}(\,{x}\,) - 2\,{\rm cos}(\,{x}\,)\,{\rm +sin}(\,{x}\,) +\] +\end{maplelatex} + +\section{Notational Equivalence and Conversions} + +Two important identities relating \mexpr{D} and +\mexpr{diff} are \mexpr{D(f)(x)} = \mexpr{diff(f(x),x)} (and its +multiviate counterpart), and \mexpr{D(f)} = \mexpr{unapply(diff(f(x),x))}. +When two notations are involved for essentially the same +expression, it is essential to be able to convert from +one notation to the other. For example + +\begin{mapleinput} +diff(f(x),x); +\end{mapleinput} +\begin{maplelatex} +\[ +{\frac {{ \partial}}{{ \partial}{x}}}\,{\rm f}(\,{x}\,) +\] +\end{maplelatex} +\begin{mapleinput} +convert(",D); +\end{mapleinput} +\begin{maplettyout} +\end{maplettyout} +\begin{maplelatex} +\[ +{\rm D}(\,{f}\,)(\,{x}\,) +\] +\end{maplelatex} +\begin{mapleinput} +unapply(",x); +\end{mapleinput} +\begin{maplettyout} +\end{maplettyout} +\begin{maplelatex} +\[ +{\rm D}(\,{f}\,) +\] +\end{maplelatex} + +\section{Algorithmic Differentiation} + +The use of arrow operators, or more generally, arbitrary procedures +leads us to the interesting problem of program differentiation. +Consider the function $f$ defined by the following Maple procedure + +\begin{mapleinput} +f := proc(x) local s,t; s := sin(x); t := x^2; s*t+2*t end: +\end{mapleinput} + +\vspace{1mm} +What is its derivative? +We could compute its value as a formula and differentiate +the formula. + +\begin{mapleinput} +f(x); +\end{mapleinput} +\begin{maplelatex} +\[ +{\rm sin}(\,{x}\,)\,{x}^{2} + 2\,{x}^{2} +\] +\end{maplelatex} +\begin{mapleinput} +diff(",x); +\end{mapleinput} +\begin{maplelatex} +\[ +{\rm cos}(\,{x}\,)\,{x}^{2} + 2\,{\rm sin}(\,{x}\,)\,{x} + 4\,{x} +\] +\end{maplelatex} + +The Maple V Release 2 Share Library% +\footnote{Information about the Share Library +is included in the {\em News and Announcements} section.} +introduced a facility for differentiating programs. This has +since been incoporated into Release 3 and is accessible directly +as +\begin{mapleinput} +PD := readlib('`PD/PD`'): +\end{mapleinput} +The \mexpr{PD} procedure takes as input a Maple procedure $f$ which +is a function of $n$ parameters, and a positive integer $i$, and it returns +a Maple procedure which computes the partial derivative of $f$ with +respect to the $i^{th}$ parameter. +For example + +\begin{mapleinput} +g := PD(f,1); +\end{mapleinput} +\begin{maplelatex} +\end{maplelatex} +\begin{maplettyout} +g := proc(x) + local s,t,sx,tx; + sx := cos(x); s := sin(x); tx := 2*x; t := x^2; sx*t+s*tx+2*tx + end + +\end{maplettyout} +Does the procedure $g$ really compute $f'$? +In this case we can \emph{prove} that it does by executing the procedure +on symbolic parameters, in effect converting the function represented +by the procedure into a formula. + +\begin{mapleinput} +diff(f(x),x) - g(x); +\end{mapleinput} +\begin{maplelatex} +\[ +0 +\] +\end{maplelatex} + +Clearly one couldn't do this if a procedure had a conditional +statement involving the formal parameter $x$ and one called the procedure +with a symbolic parameter, but +under what conditions could one differentiate a +procedure involving more than just an expression? +For example, can this be done +if the procedure had loops or subroutine calls? +It turns out that the answer to this question is, surprisingly, yes. +And moreover, there exists a very simple algorithm for computing the +derivative of a procedure or a program. + +To construct the derivative procedure, +for each assignment statement $v := f(v_1, \ldots , v_n)$ that appears +in the procedure, where the $v_i$ are local variables or formal parameters, +precede it by $v_x := g(v_1, \ldots , v_n)$ where +$g(v_1, \ldots , v_n)$ is obtained by differentiating $f(v_1, \ldots , v_n)$ +formally. That is, $v_i$ may depend on $x$, hence its derivative +will be $v_{i_x}$. +Replace the last statement (or any RETURN value) by its derivative. +This very simple algorithm is called ``forward differentiation''. +There is actually quite a lot of literature on this subject. Many different +algorithms, and quite a number of implementations have been +written to differentiate Fortran code. +For a good reference see {\cite {PROCEEDINGS}}, which also contains a +fairly complete bibliography on algorithmic differentiation. + +Here is an example which illustrates the power of algorithmic +differentiation. +In this example, the use of a loop allows us to represent +a very large formula in a very compact way. +There is a theoretical gain here. In general, a function that can +be represented by a formula can be represented by a program +in an exponentially more compact way by using local variables and loops. + +\begin{mapleinput} +f := proc(x,n) local i,t; + t := x; + for i to n do t := ln(t) od; + t +end: +g := PD(f,1,2); # compute D(D(f)) +\end{mapleinput} +\begin{maplelatex} +\end{maplelatex} +\begin{maplettyout} +g := proc(x,n) + local tx,i,t,txx; + txx := 0; + tx := 1; + t := x; + for i to n do txx := txx/t-tx^2/t^2; tx := tx/t; t := ln(t) od; + txx + end + +\end{maplettyout} + +Another nice theoretical result is that the size of the resulting +program which computes the derivative is linear in the size of the +original program. In fact, in most cases, it is not much bigger. +What can algorithmic differentiation be used for? +In numerical computation, one often is given a function $f:R^N \rightarrow R$, +where $f$ is given by a program, rather than an analytic formula. +The standard fast methods for computing the zeros +of $f$ or the extrema require the derivatives of $f$. +An example is given in the article \emph{The Billiard Problem} +in this issue, by Walter Gander and Dominik Gruntz, where a Newton +iteration is used to find the zeroes of a function. + +Here is another example where we are given a function which +evaluates a polynomial input as an array of coefficients using Horner's +rule and we compute its derivative. + +\begin{mapleinput} +f := proc(x,b,n) local i,s; + # the array b represents the polynomial b = sum( b[i]*x^i, i=0..n ) + s := 0; + for i from n by -1 to 0 do s := s*x+b[i]; od; + s +end: +g := PD(f,1); +\end{mapleinput} +\begin{maplelatex} +\end{maplelatex} +\begin{maplettyout} +g := proc(x,b,n) + local i,s,sx; + sx := 0; + s := 0; + for i from n by -1 to 0 do sx := sx*x+s; s := s*x+b[i] od; + sx + end + +\end{maplettyout} + +It may not be apparent from these examples, but the difficult +part of algorithmic differentiation is program optimization. +This is because differentiation produces redundant computation. +For example, repeatedly differentiating formulae results in +lots of repeated common subexpressions. And, when computing partial +derivatives, a lot of zeroes may result. +Thus two of the main focuses of algorithmic differentiation is +to avoid as much of this redundancy as possible and +do program optimization. +We are presently working on extending Maple's capabilities for +differentiating procedures to compute gradients and jacobians, +and improving the optimization of the resulting procedures. + +\begin{thebibliography}{10} + +\bibitem{MUC84} +Michael Wester and Stanly Steinberg, +A Survey of Symbolic Differentiation Implementations, +\emph{Proceedings of the 1984 MACSYMA Users' Conference}, +Schenectady NY, (1984). + +\bibitem{OPERATORS} +Gaston Gonnet, +An Implementation of Operators for Symbolic Algebra Systems, +\emph{Proceedings of the 1986 Symposium on Symbolic and Algebraic Computations}, +Symsac `86, ACM, (1986). + +\bibitem{PROCEEDINGS} +Automatic Differentiation of Algorithms: Theory, Implementation +and Application, SIAM, Philadelphia 1991. +\textit{Proceedings of the SIAM Workshop on Automatic Differentiation}, +Breckenridge, CO, (1991). + +\end{thebibliography} + +\end{document} diff --git a/macros/latex/contrib/maple/README b/macros/latex/contrib/maple/README new file mode 100644 index 0000000000..617786845a --- /dev/null +++ b/macros/latex/contrib/maple/README @@ -0,0 +1,131 @@ +The Maple Technical Newsletter Styles (LaTeX2e) +================================================ + +This directory contains latex2e style files and sample documents of +interest to contributors to the Maple Technical NewsLetter. In +particular, see the sample article MTNarticle.tex. This article is +also available as an HTML document. See the file: + + ftp://ftp.maplesoft.com/pub/maple/MTN/MTNarticle/MTNarticle.html + +Author's Guide Lines +-------------------- + +When preparing an article for MTN, the following general guidelines should +be followed. + + - Prepare the article exactly as you would a standard LaTeX + "article", indicating the \title and \author. Abstracts will not be + used in the final publication. + + - When giving examples in Maple, both input and output must + be shown. Include Maple commands and and Maple results using the + same macros as used by "Export to LaTeX". (See below) + + - The reader should be able to reproduce the output by simply + entering every Maple input, i.e. you should not hide some steps. + +To prepare your article, structure it exactly as you would a standard +latex "article". For example, + + - Specify the title using the \title{...} macro. + + - Specify the author / authors using \author{...} and their + institutions by using \thanks{...} + + - Include the title by using the \maketitle macro. + + - Use ordinary \section{...}, and \subsection{...} commands to + break up your article. + +The final document will be processed using the the document class +mtn.cls. Thus, a typical article will have the structure + + \documentclass[11pt]{mtn} + \usepackage{palatino} + \begin{document} + \title{The D Operator and Algorithmic \\ Differentiation} + \author{Michael Monagan + \thanks{Informatik E.T.H., Z\"{u}rich, Switzerland. monagan@inf.ethz.ch} + \and J. S. Devitt\thanks{Faculty of Mathematics, University of Waterloo, + Canada, jsdevitt@daisy.uwaterloo.ca} + } + \shorttitle{D Operator} + \maketitle + \begin{document} + \section{Introduction} + ... + \end{document} + +You can use the standard LaTeX "article" style for preparation just by +omitting the "\shorttitle". Use the macro package found in +"mapleenv.sty". In that case the document would begin + + \documentclass[11pt]{article} + \usepackage{mapleenv} + \begin{document} + \title{...} + \author{...} + \maketitle + ... + +In either case, Maple input and output should be inserted in a format +analogous to that produced by "Export to LaTeX" from a Maple V Release 3 +worksheet. Examples of Maple input and output are + + Input: + + \begin{mapleinput} + x + y^2; + \end{mapleinput} + + Output: + + \begin{maplelatex} + \[ + x + y^2 + \] + \end{maplelatex} + + TTYOutput: + + \begin{maplettyout} + 2 + x + y + \end{maplettyout} + + Plots: + + \mapleplot{filename.ps} + + +Required LaTeX2e Macro Packages and Styles +------------------------------------------- + +Before processing your document with LaTeX2e you will require +the style files + + mtn.cls (fileversion 1.8 or newer) + mapleenv.sty (fileversion 4.0 or newer) + +and the "graphics" package that is part of LaTeX2e distribution must be +installed as part of your LaTeX environment. A copy is located in the +"graphics" subdirectory. The graphics macros must be expanded for +installation by running the command + + % latex2e graphics.ins + +The result of expanding this macro package is found in the subdirectory +"graphics_expanded". The master graphics source files are available from + + ftp://ftp.shsu.edu/tex-archive/macros/latex2e/packages/graphics + +The Maple styles are available from + + ftp://ftp.maplesoft.com/pub/maple/MTN + ftp://ftp.shsu.edu/tex-archive/macros/latex2e/contrib/supported/maple + +The document maplems.tex provides additional documentation on how to use +the styles. For additional information, contact doc@maplesoft.on.ca . + +Feb, 1995. diff --git a/macros/latex/contrib/maple/mtn.cls b/macros/latex/contrib/maple/mtn.cls new file mode 100644 index 0000000000..5bf1af5c47 --- /dev/null +++ b/macros/latex/contrib/maple/mtn.cls @@ -0,0 +1,173 @@ +% LaTeX style file for the Maple Technical Newsletter +% Copyright 1994, by Waterloo Maple Software. +\NeedsTeXFormat{LaTeX2e} +\typeout{} +\typeout{mtn.cls: A Document Class for the Maple Technical Newsletter} +\typeout{} +\typeout{This style is based on the macros used by Maple's Export to LaTeX.} +\typeout{Maple input and output are specified by:} +\typeout{} +\typeout{Input:} +\typeout{} +\typeout{ \protect\begin{mapleinput}} +\typeout{ x + y;} +\typeout{ \protect\end{mapleinput}} +\typeout{} +\typeout{Output:} +\typeout{} +\typeout{ \protect\begin{maplelatex}} +\typeout{ \protect\[} +\typeout{ x + y} +\typeout{ \protect\]} +\typeout{ \protect\end{maplelatex}} +\typeout{} +\typeout{Plots:} +\typeout{} +\typeout{To include postscript graphics from a file use the macro} +\typeout{} +\typeout{ \protect\mapleplot{filename.ps}} +\typeout{} +\typeout{} +% +\def\fileversion{1.8} +\def\filedate{1994/10/25} +\ProvidesClass{mtn}[\filedate\space\fileversion] +% +\edef\PtSize{11pt} %% default +\DeclareOption{10pt}{ + \edef\PtSize{10pt} + } +\DeclareOption{11pt}{ + \edef\PtSize{11pt} + } +\DeclareOption{12pt}{ + \edef\PtSize{12pt} + } +\DeclareOption*{\PassOptionsToPackage{\CurrentOption}{mapleenv}} +\ExecuteOptions{dvips} +\ProcessOptions +% +\LoadClass[\PtSize,twoside]{article} +\RequirePackage{mapleenv,fancyheadings} +%% +%% DEFINE PAGE LAYOUT +%% including fancy headers and footers +%% +\setlength{\marginparwidth}{30pt} +\setlength{\marginparsep}{5pt} +\setlength{\oddsidemargin}{0.5 in} +\setlength{\evensidemargin}{-0.5 in} +\setlength{\textheight}{21.5 cm} +\setlength{\textwidth}{6.25 in} +\setlength{\headheight}{\baselineskip} +\setlength{\footskip}{1.36 cm} +\setlength{\topmargin}{-0.125 in} +%% +%% USE FANCY PAGESTYLE TO ALLOW PROPER HEADERS AND FOOTERS +%% (see man fancyheadings for details) +%% +\pagestyle{fancyplain} +\setlength{\footrulewidth}{0.6pt} +\setlength{\headrulewidth}{0.6pt} +\setlength{\plainheadrulewidth}{0.6pt} +\setlength{\plainfootrulewidth}{0.6pt} +\lfoot[\rm\thepage]{} +\cfoot{} +\rfoot[]{\rm\thepage} +%% +%%% Define the section behavior, etc. +\setcounter{secnumdepth}{0} +\renewcommand\section{\@startsection{section}{1}{-0.09em}% + {-2ex \@plus -1ex \@minus -.2ex}% + {1ex \@plus.2ex}% + {\reset@font\Large\bfseries\rmfamily}} +\renewcommand\subsection{\@startsection{subsection}{2}{\z@}% + {-1ex\@plus -1ex \@minus -.2ex}% + {1ex \@plus .2ex}% + {\reset@font\large\bfseries\scshape}} +\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}% + {-3.25ex\@plus -1ex \@minus -.2ex}% + {1.5ex \@plus .2ex}% + {\reset@font\normalsize\bfseries}} +\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}% + {3.25ex \@plus1ex \@minus.2ex}% + {-1em}% + {\reset@font\normalsize\bfseries}} +%%% +\def\title#1{\gdef\@title{#1}} +\def\shorttitle#1{\gdef\@shorttitle{#1}} +\def\author#1{\gdef\@author{#1}} +\def\thanks#1{\footnotemark\begingroup +\def\protect{\noexpand\protect\noexpand}\xdef\@thanks{\@thanks + \protect\footnotetext[\the\c@footnote]{#1}}\endgroup} + +\def\@thanks{} +\def\@shorttitle{} +\def\and{%% % \begin{tabular} +\end{tabular}\hskip 1em plus .17fil\begin{tabular}[t]{c}%% \end{tabular} +} +% +\renewcommand\maketitle{\par + \begingroup + \renewcommand\thefootnote{\fnsymbol{footnote}}% + \def\@makefnmark{\hbox to\z@{$\m@th^{\@thefnmark}$\hss}}% + \long\def\@makefntext##1{\parindent 1em\noindent + \hbox to1.8em{\hss$\m@th^{\@thefnmark}$}##1}% + \if@twocolumn + \ifnum \col@number=\@ne + \@maketitle + \else + \twocolumn[\@maketitle]% + \fi + \else + \newpage + \global\@topnum\z@ % Prevents figures from going at top of page. + \@maketitle + \fi + \thispagestyle{plain}\@thanks + \endgroup + \setcounter{footnote}{0}% + \let\thanks\relax + \let\maketitle\relax\let\@maketitle\relax + \gdef\@thanks{}\gdef\@author{}\gdef\@title{}} +% +% \noindent \hspace{-0.09 em}{\Huge\rmfamily\bfseries{#1}}\par +% \noindent {\Large\rmfamily\bfseries\em{#2}}\par +\def\@shorttitle{\@title} +\def\@maketitle{% + \headsep=0pt + \newpage + \thispagestyle{plain} + \null + \noindent + \vbox{\vskip-2.5ex\noindent\Huge\rmfamily\mdseries \@title \par}% + \vskip 0.5ex% + \lineskip .5ex% + \noindent% + {\Large\rmfamily\bfseries\itshape% + \begin{tabular}[t]{c}% + \hspace*{-1ex}\@author + \end{tabular}\par}% + \vskip 1.5ex + \hrule + \par + \thispagestyle{plain} + \rhead[]{\fancyplain{}{\@shorttitle}} + \lhead[\fancyplain{}{\@shorttitle}]{} + \vskip 3ex} + +% +% aliases for old style usage +% +\let\heading\section +\let\subheading\subsection +\newcommand{\HEADING}[3]{% + \let\footnote\thanks% + \title{#1} + \author{#2} + \shorttitle{#3} + \maketitle +}% + +\raggedbottom +\endinput % mtn.cls -- cgit v1.2.3