Prev Next

@(@\newcommand{\W}[1]{ \; #1 \; } \newcommand{\R}[1]{ {\rm #1} } \newcommand{\B}[1]{ {\bf #1} } \newcommand{\D}[2]{ \frac{\partial #1}{\partial #2} } \newcommand{\DD}[3]{ \frac{\partial^2 #1}{\partial #2 \partial #3} } \newcommand{\Dpow}[2]{ \frac{\partial^{#1}}{\partial {#2}^{#1}} } \newcommand{\dpow}[2]{ \frac{ {\rm d}^{#1}}{{\rm d}\, {#2}^{#1}} }@)@
exp_2: Second Order Reverse Mode

Purpose
In general, a second order reverse sweep is given the first order expansion for all of the variables in an operation sequence. Given a choice of a particular variable, it computes the derivative, of that variables first order expansion coefficient, with respect to all of the independent variables.

Mathematical Form
Suppose that we use the algorithm exp_2.hpp to compute @[@ f(x) = 1 + x + x^2 / 2 @]@ The corresponding second derivative is @[@ \Dpow{2}{x} f (x) = 1 @]@

f_5
For our example, we chose to compute the derivative of @(@ v_5^{(1)} @)@ with respect to all the independent variable. For the case computed for the first order sweep , @(@ v_5^{(1)} @)@ is the derivative of the value returned by exp_2.hpp . This the value computed will be the second derivative of the value returned by exp_2.hpp . We begin with the function @(@ f_5 @)@ where @(@ v_5^{(1)} @)@ is both an argument and the value of the function; i.e., @[@ \begin{array}{rcl} f_5 \left( v_1^{(0)}, v_1^{(1)} , \ldots , v_5^{(0)} , v_5^{(1)} \right) & = & v_5^{(1)} \\ \D{f_5}{v_5^{(1)}} & = & 1 \end{array} @]@ All the other partial derivatives of @(@ f_5 @)@ are zero.

Index 5: f_4
Second order reverse mode starts with the last operation in the sequence. For the case in question, this is the operation with index 5. The zero and first order sweep representations of this operation are @[@ \begin{array}{rcl} v_5^{(0)} & = & v_2^{(0)} + v_4^{(0)} \\ v_5^{(1)} & = & v_2^{(1)} + v_4^{(1)} \end{array} @]@ We define the function @(@ f_4 \left( v_1^{(0)} , \ldots , v_4^{(1)} \right) @)@ as equal to @(@ f_5 @)@ except that @(@ v_5^{(0)} @)@ and @(@ v_5^{(1)} @)@ are eliminated using this operation; i.e. @[@ f_4 = f_5 \left[ v_1^{(0)} , \ldots , v_4^{(1)} , v_5^{(0)} \left( v_2^{(0)} , v_4^{(0)} \right) , v_5^{(1)} \left( v_2^{(1)} , v_4^{(1)} \right) \right] @]@ It follows that @[@ \begin{array}{rcll} \D{f_4}{v_2^{(1)}} & = & \D{f_5}{v_2^{(1)}} + \D{f_5}{v_5^{(1)}} * \D{v_5^{(1)}}{v_2^{(1)}} & = 1 \\ \D{f_4}{v_4^{(1)}} & = & \D{f_5}{v_4^{(1)}} + \D{f_5}{v_5^{(1)}} * \D{v_5}{v_4^{(1)}} & = 1 \end{array} @]@ All the other partial derivatives of @(@ f_4 @)@ are zero.

Index 4: f_3
The next operation has index 4, @[@ \begin{array}{rcl} v_4^{(0)} & = & v_3^{(0)} / 2 \\ v_4^{(1)} & = & v_3^{(1)} / 2 \end{array} @]@ We define the function @(@ f_3 \left( v_1^{(0)} , \ldots , v_3^{(1)} \right) @)@ as equal to @(@ f_4 @)@ except that @(@ v_4^{(0)} @)@ and @(@ v_4^{(1)} @)@ are eliminated using this operation; i.e., @[@ f_3 = f_4 \left[ v_1^{(0)} , \ldots , v_3^{(1)} , v_4^{(0)} \left( v_3^{(0)} \right) , v_4^{(1)} \left( v_3^{(1)} \right) \right] @]@ It follows that @[@ \begin{array}{rcll} \D{f_3}{v_2^{(1)}} & = & \D{f_4}{v_2^{(1)}} & = 1 \\ \D{f_3}{v_3^{(1)}} & = & \D{f_4}{v_3^{(1)}} + \D{f_4}{v_4^{(1)}} * \D{v_4^{(1)}}{v_3^{(1)}} & = 0.5 \end{array} @]@ All the other partial derivatives of @(@ f_3 @)@ are zero.

Index 3: f_2
The next operation has index 3, @[@ \begin{array}{rcl} v_3^{(0)} & = & v_1^{(0)} * v_1^{(0)} \\ v_3^{(1)} & = & 2 * v_1^{(0)} * v_1^{(1)} \end{array} @]@ We define the function @(@ f_2 \left( v_1^{(0)} , \ldots , v_2^{(1)} \right) @)@ as equal to @(@ f_3 @)@ except that @(@ v_3^{(0)} @)@ and @(@ v_3^{(1)} @)@ are eliminated using this operation; i.e., @[@ f_2 = f_3 \left[ v_1^{(0)} , \ldots , v_2^{(1)} , v_3^{(0)} ( v_1^{(0)} ) , v_3^{(1)} ( v_1^{(0)} , v_1^{(1)} ) \right] @]@ Note that, from the first order forward sweep , the value of @(@ v_1^{(0)} @)@ is equal to @(@ .5 @)@ and @(@ v_1^{(1)} @)@ is equal 1. It follows that @[@ \begin{array}{rcll} \D{f_2}{v_1^{(0)}} & = & \D{f_3}{v_1^{(0)}} + \D{f_3}{v_3^{(0)}} * \D{v_3^{(0)}}{v_1^{(0)}} + \D{f_3}{v_3^{(1)}} * \D{v_3^{(1)}}{v_1^{(0)}} & = 1 \\ \D{f_2}{v_1^{(1)}} & = & \D{f_3}{v_1^{(1)}} + \D{f_3}{v_3^{(1)}} * \D{v_3^{(1)}}{v_1^{(1)}} & = 0.5 \\ \D{f_2}{v_2^{(0)}} & = & \D{f_3}{v_2^{(0)}} & = 0 \\ \D{f_2}{v_2^{(1)}} & = & \D{f_3}{v_2^{(1)}} & = 1 \end{array} @]@

Index 2: f_1
The next operation has index 2, @[@ \begin{array}{rcl} v_2^{(0)} & = & 1 + v_1^{(0)} \\ v_2^{(1)} & = & v_1^{(1)} \end{array} @]@ We define the function @(@ f_1 ( v_1^{(0)} , v_1^{(1)} ) @)@ as equal to @(@ f_2 @)@ except that @(@ v_2^{(0)} @)@ and @(@ v_2^{(1)} @)@ are eliminated using this operation; i.e., @[@ f_1 = f_2 \left[ v_1^{(0)} , v_1^{(1)} , v_2^{(0)} ( v_1^{(0)} ) , v_2^{(1)} ( v_1^{(1)} ) \right] @]@ It follows that @[@ \begin{array}{rcll} \D{f_1}{v_1^{(0)}} & = & \D{f_2}{v_1^{(0)}} + \D{f_2}{v_2^{(0)}} * \D{v_2^{(0)}}{v_1^{(0)}} & = 1 \\ \D{f_1}{v_1^{(1)}} & = & \D{f_2}{v_1^{(1)}} + \D{f_2}{v_2^{(1)}} * \D{v_2^{(1)}}{v_1^{(1)}} & = 1.5 \end{array} @]@ Note that @(@ v_1 @)@ is equal to @(@ x @)@, so the second derivative of the function defined by exp_2.hpp at @(@ x = .5 @)@ is given by @[@ \Dpow{2}{x} v_5^{(0)} = \D{ v_5^{(1)} }{x} = \D{ v_5^{(1)} }{v_1^{(0)}} = \D{f_1}{v_1^{(0)}} = 1 @]@ There is a theorem about Algorithmic Differentiation that explains why the other partial of @(@ f_1 @)@ is equal to the first derivative of the function defined by exp_2.hpp at @(@ x = .5 @)@.

Verification
The file exp_2_rev2.cpp contains a routine which verifies the values computed above. It returns true for success and false for failure. It only tests the partial derivatives of @(@ f_j @)@ that might not be equal to the corresponding partials of @(@ f_{j+1} @)@; i.e., the other partials of @(@ f_j @)@ must be equal to the corresponding partials of @(@ f_{j+1} @)@.

Exercises
  1. Which statement in the routine defined by exp_2_rev2.cpp uses the values that are calculated by the routine defined by exp_2_for0.cpp ? Which statements use values that are calculate by the routine defined in exp_2_for1.cpp ?
  2. Consider the case where @(@ x = .1 @)@ and we first preform a zero order forward sweep, then a first order sweep, for the operation sequence used above. What are the results of a second order reverse sweep; i.e., what are the corresponding derivatives of @(@ f_5 , f_4 , \ldots , f_1 @)@.
  3. Create a modified version of exp_2_rev2.cpp that verifies the values you obtained for the previous exercise. Also create and run a main program that reports the result of calling the modified version of exp_2_rev2.cpp .

Input File: introduction/exp_2.omh