Prev Next

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_apx/exp_2.omh