Changeset 2994


Ignore:
Timestamp:
Oct 23, 2013 11:47:20 AM (6 years ago)
Author:
bradbell
Message:
  1. Fix bug in how reverse sparsity patterns are used during optimization.
  2. Add nz_compare to RevSparseJac? to support bug fix above.

cond_op.hpp: Indicate that conditional expressions depend on comparison result.
wish_list.omh: Add a new items connected to change in cond_op.hpp.
optimize.cpp: Add test for this bug and changes for change to cond_op.hpp.

Location:
trunk
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • trunk/cppad/local/ad_fun.hpp

    r2991 r2994  
    157157                bool               set_type  ,
    158158                bool               transpose ,
     159                bool               nz_compare,
    159160                size_t             p         ,
    160161                const VectorSet&   s         , 
     
    167168                const std::set<size_t>&  set_type  ,
    168169                bool                     transpose ,
     170                bool                     nz_compare,
    169171                size_t                   p         ,
    170172                const VectorSet&         s         , 
     
    363365        template <typename VectorSet>
    364366        VectorSet RevSparseJac(
    365                 size_t q, const VectorSet &s, bool transpose = false
     367                size_t q, const VectorSet &s, bool transpose = false,
     368                bool nz_compare = false
    366369        );
    367370        // reverse mode Hessian sparsity
  • trunk/cppad/local/checkpoint.hpp

    r2910 r2994  
    375375
    376376                // compute rt
     377                // 2DO: remove need for nz_compare all the time. It is only really
     378                // necessary when optimizer calls this member function.
    377379                bool transpose = true;
    378                 st = f_.RevSparseJac(q, rt, transpose);
     380                bool nz_compare = true;
     381                st = f_.RevSparseJac(q, rt, transpose, nz_compare);
    379382
    380383                return ok;
  • trunk/cppad/local/cond_op.hpp

    r2920 r2994  
    881881\c sparse_pack, \c sparse_set, or \c sparse_list.
    882882
     883\param nz_compare
     884Are the derivatives with respect to left and right of the expression below
     885considered to be non-zero:
     886\code
     887        CondExpRel(left, right, if_true, if_false)
     888\endcode
     889This is used by the optimizer to obtain the correct dependency relations.
     890
    883891\param i_z
    884892is the AD variable index corresponding to the variable z.
     
    961969template <class Vector_set>
    962970inline void reverse_sparse_jacobian_cond_op(
     971        bool                nz_compare    ,
    963972        size_t              i_z           ,
    964973        const addr_t*       arg           ,
     
    9911000        }
    9921001# endif
     1002        if( nz_compare )
     1003        {       if( arg[1] & 1 )
     1004                {       CPPAD_ASSERT_UNKNOWN( size_t(arg[2]) < i_z );
     1005                        sparsity.binary_union(arg[2], arg[2], i_z, sparsity);
     1006                }
     1007                if( arg[1] & 2 )
     1008                {       CPPAD_ASSERT_UNKNOWN( size_t(arg[3]) < i_z );
     1009                        sparsity.binary_union(arg[3], arg[3], i_z, sparsity);
     1010                }
     1011        }
     1012        // --------------------------------------------------------------------
    9931013        if( arg[1] & 4 )
    9941014        {       CPPAD_ASSERT_UNKNOWN( size_t(arg[4]) < i_z );
  • trunk/cppad/local/rev_jac_sweep.hpp

    r2991 r2994  
    6363\c sparse_pack, \c sparse_set, or \c sparse_list.
    6464
     65\param nz_compare
     66Are the derivatives with respect to left and right of the expression below
     67considered to be non-zero:
     68\code
     69        CondExpRel(left, right, if_true, if_false)
     70\endcode
     71This is used by the optimizer to obtain the correct dependency relations.
     72
    6573\param n
    6674is the number of independent variables on the tape.
     
    105113template <class Base, class Vector_set>
    106114void RevJacSweep(
     115        bool                  nz_compare,
    107116        size_t                n,
    108117        size_t                numvar,
     
    281290                        case CExpOp:
    282291                        reverse_sparse_jacobian_cond_op(
    283                                 i_var, arg, num_par, var_sparsity
     292                                nz_compare, i_var, arg, num_par, var_sparsity
    284293                        );
    285294                        break;
  • trunk/cppad/local/rev_sparse_jac.hpp

    r2910 r2994  
    1717$begin RevSparseJac$$
    1818$spell
     19        optimizer
     20        nz
     21        CondExpRel
    1922        std
    2023        VecAD
     
    8184The default value $code false$$ is used when $icode transpose$$ is not present.
    8285
     86$head nz_compare$$
     87The argument $icode nz_compare$$ has prototype
     88$codei%
     89        bool %nz_compare%
     90%$$
     91If $icode nz_compare$$ is true,
     92the derivatives with respect to left and right of the
     93$cref CondExp$$ below are considered to be non-zero:
     94$codei%
     95        %CondExp%Rel%(%left%, %right%, %if_true%, %if_false%)
     96%$$
     97This is used by the
     98$cref/optimizer/optimize/$$ with $cref checkpoint$$ functions
     99to obtain the correct dependency relations.
     100The default value $icode%nz_compare% = false%$$ is used when
     101$icode nz_compare$$ is not present.
     102
    83103$head r$$
    84104The argument $icode s$$ has prototype
     
    189209\param transpose
    190210are the sparsity patterns transposed.
     211
     212\param nz_compare
     213Are the derivatives with respect to left and right of the expression below
     214considered to be non-zero:
     215\code
     216        CondExpRel(left, right, if_true, if_false)
     217\endcode
     218This is used by the optimizer to obtain the correct dependency relations.
    191219
    192220\param q
     
    227255void RevSparseJacBool(
    228256        bool                   transpose        ,
     257        bool                   nz_compare       ,
    229258        size_t                 q                ,
    230259        const VectorSet&       r                ,
     
    274303        // evaluate the sparsity patterns
    275304        RevJacSweep(
     305                nz_compare,
    276306                n,
    277307                total_num_var,
     
    325355see \c RevSparseJacBool.
    326356
     357\param nz_compare
     358see \c RevSparseJacBool.
     359
    327360\param q
    328361see \c RevSparseJacBool.
     
    349382void RevSparseJacSet(
    350383        bool                   transpose        ,
     384        bool                   nz_compare       ,
    351385        size_t                 q                ,
    352386        const VectorSet&       r                ,
     
    420454        // evaluate the sparsity patterns
    421455        RevJacSweep(
     456                nz_compare,
    422457                n,
    423458                total_num_var,
     
    460495
    461496\param transpose
    462 See \c RevSparseJac(q, r, transpose)
     497See \c RevSparseJac(q, r, transpose, nz_compare)
     498
     499\param nz_compare
     500See \c RevSparseJac(q, r, transpose, nz_compare)
    463501
    464502\param q
    465 See \c RevSparseJac(q, r, transpose)
     503See \c RevSparseJac(q, r, transpose, nz_compare)
    466504
    467505\param r
    468 See \c RevSparseJac(q, r, transpose)
     506See \c RevSparseJac(q, r, transpose, nz_compare)
    469507
    470508\param s
     
    478516        bool                set_type          ,
    479517        bool                transpose         ,
     518        bool                nz_compare        ,
    480519        size_t              q                 ,
    481520        const VectorSet&    r                 ,
     
    489528        RevSparseJacBool(
    490529                transpose      ,
     530                nz_compare     ,
    491531                q              ,
    492532                r              ,
     
    511551
    512552\param transpose
    513 See \c RevSparseJac(q, r, transpose)
     553See \c RevSparseJac(q, r, transpose, nz_compare)
     554
     555\param nz_compare
     556See \c RevSparseJac(q, r, transpose, nz_compare)
    514557
    515558\param q
    516 See \c RevSparseJac(q, r, transpose)
     559See \c RevSparseJac(q, r, transpose, nz_compare)
    517560
    518561\param r
    519 See \c RevSparseJac(q, r, transpose)
     562See \c RevSparseJac(q, r, transpose, nz_compare)
    520563
    521564\param s
     
    528571        const std::set<size_t>&      set_type          ,
    529572        bool                         transpose         ,
     573        bool                         nz_compare        ,
    530574        size_t                       q                 ,
    531575        const VectorSet&             r                 ,
     
    539583        RevSparseJacSet(
    540584                transpose      ,
     585                nz_compare     ,
    541586                q              ,
    542587                r              ,
     
    554599The C++ source code corresponding to this operation is
    555600\verbatim
    556         s = f.RevSparseJac(q, r, transpose)
     601        s = f.RevSparseJac(q, r, transpose, nz_compare)
    557602\endverbatim
    558603
     
    572617\param transpose
    573618are the sparsity patterns for \f$ R \f$ and \f$ S(x) \f$ transposed.
     619
     620\param nz_compare
     621Are the derivatives with respect to left and right of the expression below
     622considered to be non-zero:
     623\code
     624        CondExpRel(left, right, if_true, if_false)
     625\endcode
     626This is used by the optimizer to obtain the correct dependency relations.
     627
    574628
    575629\return
     
    590644template <class VectorSet>
    591645VectorSet ADFun<Base>::RevSparseJac(
    592         size_t              q         ,
    593         const VectorSet&    r         ,
    594         bool                transpose )
     646        size_t              q          ,
     647        const VectorSet&    r          ,
     648        bool                transpose  ,
     649        bool                nz_compare )
    595650{
    596651        VectorSet s;
     
    600655                Set_type()    ,
    601656                transpose     ,
     657                nz_compare    ,
    602658                q             ,
    603659                r             ,
  • trunk/omh/whats_new/whats_new_13.omh

    r2992 r2994  
    1414$dollar @$$
    1515$spell
     16        nz
     17        Jacobian
    1618        CondExp
    1719        op_arg
     
    5860assist you in learning about changes between various versions of CppAD.
    5961
     62$head 10-23$$
     63Fix a bug in the optimization of calls to $cref atomic$$ functions.
     64This bug existed before recent change to optimizing conditional expressions.
     65This required adding the
     66$cref/nz_compare/RevSparseJac/nz_compare/$$ argument to the
     67reverse Jacobian sparsity pattern calculation.
     68For further details; see sparsity heading under conditional expressions in the
     69$cref/whish list/WishList/Conditional Expressions/Sparsity/$$.
     70
    6071$head 10-22$$
    6172$list number$$
  • trunk/omh/wish_list.omh

    r2992 r2994  
    1212$begin WishList$$
    1313$spell
     14        jacobian
     15        nz
     16        RevSparseJac
     17        optimizer
    1418        Rel
    1519        Gt
     
    6771
    6872$head Conditional Expressions$$
     73
     74$subhead Nested$$
    6975The $cref/optimization/CondExp/Optimize/$$ of conditional expressions
    7076$codei%
     
    8086not all the possible cases will be excluded by $cref optimize$$.
    8187
     88$subhead Sparsity$$
     89The $cref/optimizer/optimize/$$ uses
     90$cref/atomic reverse jacobian sparsity/atomic_rev_sparse_jac/$$
     91to determine which arguments affect the value of the results
     92for the atomic functions (which include $cref checkpoint$$ functions).
     93While the partials of
     94$codei%
     95        %z% = CondExp%Rel%( %left%, %right%, %if_true%, %if_false% )
     96%$$
     97with respect to $icode left$$ and $icode right$$ always evaluates to zero,
     98the value of $icode z$$ does depend on the value of $icode left$$ and
     99$icode right$$.
     100The $cref checkpoint$$ functions use the value true for
     101$cref/nz_compare/RevSparseJac/nz_compare/$$ when computing
     102reverse jacobian sparsity patterns.
     103This enables the optimizer to properly track the dependencies.
     104An $cref atomic_option$$ should be added so this is only
     105done when the optimizer is using the sparsity pattern for this purpose.
    82106
    83107$head Forward Mode Recomputation$$
  • trunk/test_more/optimize.cpp

    r2993 r2994  
    1717
    1818namespace {
     19        // ----------------------------------------------------------------
     20        // Test for bug where checkpoint function did not depend on
     21        // the operands in the logical comparison because of the CondExp
     22        // sparsity pattern.
     23        void j_algo(
     24                const CppAD::vector< CppAD::AD<double> >& ax ,
     25                      CppAD::vector< CppAD::AD<double> >& ay )
     26        {       ay[0] = CondExpGt(ax[0], ax[1], ax[2], ax[3]); }
     27       
     28        bool cond_exp_sparsity(void)
     29        {       bool ok = true;
     30                using CppAD::AD;
     31                using CppAD::vector;
     32       
     33                // Create a checkpoint version of the function g
     34                vector< AD<double> > au(4), av(1);
     35                for(size_t i = 0; i < 4; i++)
     36                        au[i] = AD<double>(i);
     37                CppAD::checkpoint<double> j_check("j_check", j_algo, au, av);
     38       
     39                // independent variable vector
     40                vector< AD<double> > ax(2), ay(1);
     41                ax[0] = 1.;
     42                ax[1] = 1.;
     43                Independent(ax);
     44       
     45                // call atomic function that does not get used
     46                for(size_t i = 0; i < 4; i++)
     47                        au[i] = ax[0] + AD<double>(i + 1) * ax[1];
     48                j_check(au, ay);
     49       
     50                // create function object f : ax -> ay
     51                CppAD::ADFun<double> f(ax, ay);
     52       
     53                // now optimize the operation sequence
     54                f.optimize();
     55       
     56                // check result where true case is used; i.e., au[0] > au[1]
     57                vector<double> x(2), y(1);
     58                x[0] = 1.;
     59                x[1] = -1;
     60                y    = f.Forward(0, x);
     61                ok  &= y[0] == x[0] + double(3) * x[1];
     62               
     63       
     64                // check result where false case is used; i.e., au[0] <= au[1]
     65                x[0] = 1.;
     66                x[1] = 1;
     67                y    = f.Forward(0, x);
     68                ok  &= y[0] == x[0] + double(4) * x[1];
     69               
     70                return ok;
     71        }
    1972        // -------------------------------------------------------------------
    2073        // Test conditional optimizing out call to an atomic function call
     
    10061059
    10071060                // Y[2]
    1008                 // 2DO: There is a subtitle issue that has to do with using reverse
    1009                 // jacobian sparsity patterns during the optimization process.
    1010                 // We need an option to include X[0] in the sparsity pattern
    1011                 // so the optimizer can know it affects the results.
    10121061                Y[index]             = CondExpLe(X[0], X[1], X[1]+X[1], X[2]-X[2]);
    10131062                Check[index * n + 0] = false;
     
    13191368bool optimize(void)
    13201369{       bool ok = true;
     1370        // check conditional expression sparsity pattern
     1371        // (used to optimize calls to atomic functions).
     1372        ok     &= cond_exp_sparsity();
    13211373        // check optimizing out entire atomic function
    13221374        ok     &= atomic_cond_exp();
Note: See TracChangeset for help on using the changeset viewer.