123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114 |
- /*
- * autodiff.h
- *
- * Created on: 16 Apr 2013
- * Author: s0965328
- */
- #ifndef AUTODIFF_H_
- #define AUTODIFF_H_
- #include <boost/unordered_set.hpp>
- #include <boost/numeric/ublas/matrix_proxy.hpp>
- #include <boost/numeric/ublas/matrix.hpp>
- #include <boost/numeric/ublas/matrix_sparse.hpp>
- #include <boost/numeric/ublas/io.hpp>
- #include "auto_diff_types.h"
- #include "Node.h"
- #include "VNode.h"
- #include "OPNode.h"
- #include "PNode.h"
- #include "ActNode.h"
- #include "EdgeSet.h"
- /*
- * + Function and Gradient Evaluation
- * The tapeless implementation for function and derivative evaluation
- * Advantage for tapeless:
- * Low memory usage
- * Function evaluation use one stack
- * Gradient evaluation use two stack.
- * Disadvantage for tapeless:
- * Inefficient if the expression tree have repeated nodes.
- * for example:
- * root
- * / \
- * * *
- * / \ / \
- * x1 x1 x1 x1
- * Tapeless implementation will go through all the edges.
- * ie. adjoint of x will be updated 4 times for the correct
- * gradient of x1.While the tape implemenation can discovery this
- * dependence and update adjoint of x1 just twice. The computational
- * graph (DAG) for a taped implemenation will be look like bellow.
- * root
- * /\
- * *
- * /\
- * x1
- *
- * + Forward Hessian Evaluation:
- * This is an inefficient implementation of the forward Hessian method. It will evaluate the diagonal
- * and upper triangular of the Hessian. The gradient is also evaluation in the same routine. The result
- * will be returned in an array.
- * To use this method, one have to provide a len parameter. len = (nvar+3)*nvar/2 where nvar is the number
- * of independent variables. ie. x_1 x_2 ... x_nvar. And the varaible id need to be a consequent integer start
- * with 0.
- * ret_vec will contains len number of doubles. Where the first nvar elements is the gradient vector,
- * and the rest of (nvar+1)*nvar/2 elements are the upper/lower plus the diagonal part of the Hessian matrix
- * in row format.
- * This algorithm is inefficient, because at each nodes, it didn't check the dependency of the independent
- * variables up to the current node. (or it is hard to do so for this setup). Therefore, it computes a full
- * for loops over each independent variable (ie. assume they are all dependent), for those independent
- * variables that are not dependent at the current node, zero will be produced by computation.
- * By default the forward mode hessian routing is disabled. To enable the forward hessian interface, the
- * compiler marco FORWARD_ENABLED need to be set equal to 1 in auto_diff_types.h
- *
- * + Reverse Hessian*Vector Evaluation:
- * Simple, building a tape in the forward pass, and a reverse pass will evaluate the Hessian*vector. The implemenation
- * also discovery the repeated subexpression and use one piece of memory on the tape for the same subexpression. This
- * allow efficient evaluation, because the repeated subexpression only evaluate once in the forward and reverse pass.
- * This algorithm can be called n times to compute a full Hessian, where n equals the number of independent
- * variables.
- * */
- typedef boost::numeric::ublas::compressed_matrix<double,boost::numeric::ublas::column_major,0,std::vector<std::size_t>,std::vector<double> > col_compress_matrix;
- typedef boost::numeric::ublas::matrix_row<col_compress_matrix > col_compress_matrix_row;
- typedef boost::numeric::ublas::matrix_column<col_compress_matrix > col_compress_matrix_col;
- namespace AutoDiff{
- //node creation methods
- extern PNode* create_param_node(double value);
- extern VNode* create_var_node(double v=NaN_Double);
- extern OPNode* create_uary_op_node(OPCODE code, Node* left);
- extern OPNode* create_binary_op_node(OPCODE code, Node* left,Node* right);
- //single constraint version
- extern double eval_function(Node* root);
- extern unsigned int nzGrad(Node* root);
- extern double grad_reverse(Node* root,vector<Node*>& nodes, vector<double>& grad);
- extern unsigned int nzHess(EdgeSet&);
- extern double hess_reverse(Node* root, vector<Node*>& nodes, vector<double>& dhess);
- //multiple constraints version
- extern unsigned int nzGrad(Node* root, boost::unordered_set<Node*>& vnodes);
- extern double grad_reverse(Node* root, vector<Node*>& nodes, col_compress_matrix_row& rgrad);
- extern unsigned int nzHess(EdgeSet&,boost::unordered_set<Node*>& set1, boost::unordered_set<Node*>& set2);
- extern double hess_reverse(Node* root, vector<Node*>& nodes, col_compress_matrix_col& chess);
- #if FORWARD_ENDABLED
- //forward methods
- extern void hess_forward(Node* root, unsigned int nvar, double** hess_mat);
- #endif
- //utiliy methods
- extern void nonlinearEdges(Node* root, EdgeSet& edges);
- extern unsigned int numTotalNodes(Node*);
- extern string tree_expr(Node* root);
- extern void print_tree(Node* root);
- extern void autodiff_setup();
- extern void autodiff_cleanup();
- };
- #endif /* AUTODIFF_H_ */
|