Prev Next

exp_2: First Order Reverse Mode

Purpose
First order reverse mode uses the operation sequence , and zero order forward sweep values, to compute the first order derivative of one dependent variable with respect to all the independent variables. The computations are done in reverse of the order of the computations in the original algorithm.

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


f_5
For our example, we chose to compute the derivative of the value returned by exp_2.hpp which is equal to the symbol  v_5 in the exp_2 operation sequence . We begin with the function  f_5  where  v_5 is both an argument and the value of the function; i.e.,  \[
\begin{array}{rcl}
f_5 ( v_1 , v_2 , v_3 , v_4 , v_5 ) & = & v_5 
\\
\D{f_5}{v_5} & = & 1
\end{array}
\] 
All the other partial derivatives of  f_5  are zero.

Index 5: f_4
Reverse mode starts with the last operation in the sequence. For the case in question, this is the operation with index 5,  \[
     v_5 = v_2 + v_4
\] 
We define the function  f_4 ( v_1 , v_2 , v_3 , v_4 )  as equal to  f_5  except that  v_5  is eliminated using this operation; i.e.  \[
f_4  = 
f_5 [  v_1 , v_2 , v_3 , v_4 , v_5 ( v_2 , v_4 ) ]
\] 
It follows that  \[
\begin{array}{rcll}
\D{f_4}{v_2} 
& = & \D{f_5}{v_2} + 
     \D{f_5}{v_5} * \D{v_5}{v_2} 
& = 1
\\
\D{f_4}{v_4} 
& = & \D{f_5}{v_4} + 
     \D{f_5}{v_5} * \D{v_5}{v_4} 
& = 1
\end{array}
\] 
All the other partial derivatives of  f_4 are zero.

Index 4: f_3
The next operation has index 4,  \[
     v_4 = v_3 / 2
\] 
We define the function  f_3 (  v_1 , v_2 , v_3 )  as equal to  f_4  except that  v_4  is eliminated using this operation; i.e.,  \[
f_3 = 
f_4 [ v_1 , v_2 , v_3 , v_4 ( v_3 ) ]
\] 
It follows that  \[
\begin{array}{rcll}
\D{f_3}{v_1}
& = & \D{f_4}{v_1}
& = 0
\\
\D{f_3}{v_2} 
& = & \D{f_4}{v_2}
& = 1
\\
\D{f_3}{v_3} 
& = & \D{f_4}{v_3} + 
     \D{f_4}{v_4} * \D{v_4}{v_3} 
& = 0.5
\end{array}
\] 


Index 3: f_2
The next operation has index 3,  \[
     v_3 = v_1 * v_1
\] 
We define the function  f_2 ( v_1 , v_2 )  as equal to  f_3  except that  v_3  is eliminated using this operation; i.e.,  \[
f_2 = 
f_3 [ v_1 , v_2 , v_3 ( v_1 ) ]
\] 
Note that the value of  v_1 is equal to  x which is .5 for this evaluation. It follows that  \[
\begin{array}{rcll}
\D{f_2}{v_1}
& = & \D{f_3}{v_1} +
     \D{f_3}{v_3} * \D{v_3}{v_1} 
& = 0.5
\\
\D{f_2}{v_2} 
& = & \D{f_3}{v_2}
& = 1
\end{array}
\] 


Index 2: f_1
The next operation has index 2,  \[
     v_2 = 1 + v_1
\] 
We define the function  f_1 ( v_1 )  as equal to  f_2  except that  v_2  is eliminated using this operation; i.e.,  \[
f_1 = 
f_2 [ v_1 , v_2 ( v_1 ) ]
\] 
It follows that  \[
\begin{array}{rcll}
\D{f_1}{v_1}
& = & \D{f_2}{v_1} +
     \D{f_2}{v_2} * \D{v_2}{v_1} 
& = 1.5
\end{array}
\] 
Note that  v_1 is equal to  x , so the derivative of this is the derivative of the function defined by exp_2.hpp at  x = .5 .

Verification
The file exp_2_rev1.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_rev1.cpp uses the values that are calculated by the routine defined by exp_2_for0.cpp ?
  2. Consider the case where  x = .1 and we first preform a zero order forward sweep for the operation sequence used above. What are the results of a first 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_rev1.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_rev1.cpp .

Input File: introduction/exp_apx/exp_2.omh