ConstrainedOptPack_MatrixHessianSuperBasic.cpp

Go to the documentation of this file.
00001 // @HEADER
00002 // ***********************************************************************
00003 // 
00004 // Moocho: Multi-functional Object-Oriented arCHitecture for Optimization
00005 //                  Copyright (2003) Sandia Corporation
00006 // 
00007 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
00008 // license for use of this work by or on behalf of the U.S. Government.
00009 // 
00010 // This library is free software; you can redistribute it and/or modify
00011 // it under the terms of the GNU Lesser General Public License as
00012 // published by the Free Software Foundation; either version 2.1 of the
00013 // License, or (at your option) any later version.
00014 //  
00015 // This library is distributed in the hope that it will be useful, but
00016 // WITHOUT ANY WARRANTY; without even the implied warranty of
00017 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00018 // Lesser General Public License for more details.
00019 //  
00020 // You should have received a copy of the GNU Lesser General Public
00021 // License along with this library; if not, write to the Free Software
00022 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
00023 // USA
00024 // Questions? Contact Roscoe A. Bartlett (rabartl@sandia.gov) 
00025 // 
00026 // ***********************************************************************
00027 // @HEADER
00028 
00029 #include "ConstrainedOptPack_MatrixHessianSuperBasic.hpp"
00030 #include "ConstrainedOptPack_initialize_Q_R_Q_X.hpp"
00031 #include "AbstractLinAlgPack_GenPermMatrixSliceOp.hpp"
00032 #include "AbstractLinAlgPack/src/AbstractLinAlgPack_SpVectorClass.hpp"
00033 #include "AbstractLinAlgPack_SpVectorOp.hpp"
00034 #include "AbstractLinAlgPack/src/AbstractLinAlgPack_MatrixOpOut.hpp"
00035 #include "DenseLinAlgPack_DVectorClass.hpp"
00036 #include "DenseLinAlgPack_LinAlgOpPack.hpp"
00037 #include "DenseLinAlgPack_AssertOp.hpp"
00038 
00039 namespace LinAlgOpPack {
00040   using AbstractLinAlgPack::Vp_StMtV;
00041 }
00042 
00043 namespace ConstrainedOptPack {
00044 
00045 MatrixHessianSuperBasic::MatrixHessianSuperBasic()
00046   : n_(0)
00047 {}
00048 
00049 void MatrixHessianSuperBasic::initialize(
00050   size_type            n
00051   ,size_type           n_R
00052   ,const size_type     i_x_free[]
00053   ,const size_type     i_x_fixed[]
00054   ,const EBounds       bnd_fixed[]
00055   ,const B_RR_ptr_t&   B_RR_ptr
00056   ,const B_RX_ptr_t&   B_RX_ptr
00057   ,BLAS_Cpp::Transp    B_RX_trans
00058   ,const B_XX_ptr_t&   B_XX_ptr
00059   )
00060 {
00061   using DenseLinAlgPack::Mp_M_assert_sizes;
00062   using BLAS_Cpp::no_trans;
00063 
00064   const size_type
00065     n_X = n - n_R;
00066 
00067     // Validate input arguments
00068 
00069   // i_x_free
00070   if( 0 < n_R && n_R < n && i_x_free == NULL ) {
00071     throw std::invalid_argument(
00072       "MatrixHessianSuperBasic::initialize(...) : Error, "
00073       "i_x_free can not be NULL when 0 < n_R < n" );
00074   }
00075   // i_x_fixed
00076   if( 0 < n_X && n_X < n && i_x_fixed == NULL ) {
00077     throw std::invalid_argument(
00078       "MatrixHessianSuperBasic::initialize(...) : Error, "
00079       "i_x_fixed can not be NULL when 0 < n-n_R < n" );
00080   }
00081   // bnd_fixed
00082   if( 0 < n_X && bnd_fixed == NULL ) {
00083     throw std::invalid_argument(
00084       "MatrixHessianSuperBasic::initialize(...) : Error, "
00085       "bnd_fixed can not be NULL when 0 < n-n_R" );
00086   }
00087   // B_RR
00088   if(n_R > 0 ) {
00089     if( !B_RR_ptr.get() )
00090       throw std::invalid_argument(
00091         "MatrixHessianSuperBasic::initialize(...) : Error, "
00092         "B_RR_ptr.get() can not be NULL when n_R > 0" );
00093     Mp_M_assert_sizes( n_R, n_R, no_trans, B_RR_ptr->rows(), B_RR_ptr->cols(), no_trans );
00094   }
00095   // op(B_RX)
00096   if( n_R < n ) {
00097     if( B_RX_ptr.get() ) {
00098       Mp_M_assert_sizes( n_R, n_X, no_trans, B_RX_ptr->rows(), B_RX_ptr->cols(), B_RX_trans );
00099     }
00100   }
00101   // B_XX
00102   if( n_R < n ) {
00103     if( !B_XX_ptr.get() )
00104       throw std::invalid_argument(
00105         "MatrixHessianSuperBasic::initialize(...) : Error, "
00106         "B_XX_ptr.get() can not be NULL if n_R < n" );
00107     Mp_M_assert_sizes( n_X, n_X, no_trans, B_XX_ptr->rows(), B_XX_ptr->cols(), no_trans );
00108   }
00109 
00110   // Setup Q_R and Q_X and validate i_x_free[] and i_x_fixed[]
00111   const bool Q_R_is_idenity = (n_R == n && i_x_fixed == NULL );
00112   if( Q_R_is_idenity ) {
00113     Q_R_row_i_.resize(0);
00114     Q_R_col_j_.resize(0);
00115   }
00116   else {
00117     Q_R_row_i_.resize(n_R);
00118     Q_R_col_j_.resize(n_R);
00119   }
00120   Q_X_row_i_.resize(n_X);
00121   Q_X_col_j_.resize(n_X);
00122   bool test_setup = true;  // ToDo: Make this an input parameter!
00123   initialize_Q_R_Q_X(
00124     n_R,n_X,i_x_free,i_x_fixed,test_setup
00125     ,!Q_R_is_idenity ? &Q_R_row_i_[0] : NULL
00126     ,!Q_R_is_idenity ? &Q_R_col_j_[0] : NULL
00127     ,&Q_R_
00128     ,n_X ? &Q_X_row_i_[0] : NULL
00129     ,n_X ? &Q_X_col_j_[0] : NULL
00130     ,&Q_X_
00131   );
00132 
00133   // Setup bnd_fixed
00134   bnd_fixed_.resize(n_X);
00135   {for(size_type i = 0; i < n_X; ++i) bnd_fixed_[i] = bnd_fixed[i]; }
00136 
00137   // Set the rest of the arguments
00138   n_           = n;
00139   n_R_         = n_R;
00140   B_RR_ptr_    = B_RR_ptr;
00141   B_RX_ptr_    = B_RX_ptr;
00142   B_RX_trans_  = B_RX_trans;
00143   B_XX_ptr_    = B_XX_ptr;
00144 
00145 }
00146 
00147 // Overridden from Matrix
00148 
00149 size_type MatrixHessianSuperBasic::rows() const
00150 {
00151   return n_;
00152 }
00153 
00154 // Overridden from MatrixOp
00155 
00156 void MatrixHessianSuperBasic::Vp_StMtV(
00157   DVectorSlice* y, value_type a, BLAS_Cpp::Transp B_trans
00158   , const DVectorSlice& x, value_type b
00159   ) const
00160 {
00161   using BLAS_Cpp::no_trans;
00162   using BLAS_Cpp::trans;
00163   using BLAS_Cpp::trans_not;
00164   using AbstractLinAlgPack::V_MtV;
00165   using LinAlgOpPack::V_MtV;
00166   assert_initialized();
00167   DenseLinAlgPack::Vp_MtV_assert_sizes( y->size(), n_, n_, B_trans, x.size() );
00168   if( n_ == n_R_ ) {
00169     //
00170     // B = Q_R*B_RR*Q_R'
00171     //
00172     // y = b*y + a*Q_R*B_RR*Q_R'*x
00173     //
00174     if( Q_R().is_identity() ) {
00175       AbstractLinAlgPack::Vp_StMtV(y,a,*this->B_RR_ptr(),no_trans,x,b);
00176     }
00177     else {
00178       DVector Q_R_x;
00179       V_MtV( &Q_R_x, Q_R(), trans, x );
00180       AbstractLinAlgPack::Vp_StPtMtV(y,a,Q_R(),no_trans,*this->B_RR_ptr(),no_trans,Q_R_x(),b);
00181     }
00182   }
00183   else if( n_R_ == 0 ) {
00184     //
00185     // B = Q_X *B_XX * Q_X'
00186     //
00187     TEST_FOR_EXCEPT(true); // ToDo: Implement this!
00188   }
00189   else {
00190     //
00191     // B = [ Q_R  Q_X  ] * [   B_RR      op(B_RX) ] * [ Q_R' ]
00192     //                     [ op(B_RX')      B_XX  ]   [ Q_X' ]
00193     //
00194     // y = b*y + a*op(B)*x
00195     //
00196     // y = b*y + a * [ Q_R  Q_X ] * [   B_RR      op(B_RX) ] * [ Q_R' ] * x
00197     //                              [ op(B_RX')      B_XX  ]   [ Q_X' ]
00198     //
00199     // y = b*y + a*Q_R*B_RR*x_R      + a*Q_R*op(B_RX)*x_X
00200     //         + a*Q_X*op(B_RX')*x_R + a*Q_X*B_XX*x_X
00201     // where:
00202     //     x_R = Q_R'*x
00203     //     x_X = Q_X'*x
00204     //
00205     SpVector
00206       x_R,
00207       x_X;
00208     // x_R = Q_R'*x
00209     V_MtV( &x_R, Q_R(), trans, x );
00210     // x_X = Q_X'*x
00211     V_MtV( &x_X, Q_X(), trans, x );
00212     // y = b*y + a*Q_R*B_RR*x_R
00213     AbstractLinAlgPack::Vp_StPtMtV(
00214       y, a, Q_R(), no_trans, *B_RR_ptr(), no_trans, x_R(), b );
00215     // y += a*Q_R*op(B_RX)*x_X + a*Q_X*op(B_RX')*x_R
00216     if( B_RX_ptr().get() ) {
00217       AbstractLinAlgPack::Vp_StPtMtV(
00218         y, a, Q_R(), no_trans, *B_RX_ptr(), B_RX_trans(), x_X() );
00219       AbstractLinAlgPack::Vp_StPtMtV(
00220         y, a, Q_X(), no_trans, *B_RX_ptr(), trans_not(B_RX_trans()), x_R() );
00221     }
00222     // y += a*Q_X*B_XX*x_X
00223     AbstractLinAlgPack::Vp_StPtMtV(
00224       y, a, Q_X(), no_trans, *B_XX_ptr(), no_trans, x_X() );
00225   }
00226 }
00227 
00228 void MatrixHessianSuperBasic::Vp_StMtV(
00229   DVectorSlice* y, value_type a, BLAS_Cpp::Transp B_trans
00230   , const SpVectorSlice& x, value_type b
00231   ) const
00232 {
00233   using BLAS_Cpp::no_trans;
00234   using BLAS_Cpp::trans;
00235   using BLAS_Cpp::trans_not;
00236   using AbstractLinAlgPack::V_MtV;
00237   using LinAlgOpPack::V_MtV;
00238   assert_initialized();
00239   DenseLinAlgPack::Vp_MtV_assert_sizes( y->size(), n_, n_, B_trans, x.size() );
00240   if( n_ == n_R_ ) {
00241     //
00242     // B = Q_R*B_RR*Q_R'
00243     //
00244     // y = b*y + a*Q_R*B_RR*Q_R'*x
00245     //
00246     if( Q_R().is_identity() ) {
00247       AbstractLinAlgPack::Vp_StMtV(y,a,*this->B_RR_ptr(),no_trans,x,b);
00248     }
00249     else {
00250       SpVector Q_R_x;
00251       AbstractLinAlgPack::V_MtV( &Q_R_x, Q_R(), trans, x );
00252       AbstractLinAlgPack::Vp_StPtMtV(y,a,Q_R(),no_trans,*this->B_RR_ptr(),no_trans,Q_R_x(),b);
00253     }
00254   }
00255   else if( n_R_ == 0 ) {
00256     //
00257     // B = Q_X *B_XX * Q_X'
00258     //
00259     TEST_FOR_EXCEPT(true); // ToDo: Implement this!
00260   }
00261   else {
00262     //
00263     // B = [ Q_R  Q_X  ] * [   B_RR      op(B_RX) ] * [ Q_R' ]
00264     //                     [ op(B_RX')      B_XX  ]   [ Q_X' ]
00265     //
00266     // y = b*y + a*op(B)*x
00267     //
00268     // y = b*y + a * [ Q_R  Q_X ] * [   B_RR      op(B_RX) ] * [ Q_R' ] * x
00269     //                              [ op(B_RX')      B_XX  ]   [ Q_X' ]
00270     //
00271     // y = b*y + a*Q_R*B_RR*x_R      + a*Q_R*op(B_RX)*x_X
00272     //         + a*Q_X*op(B_RX')*x_R + a*Q_X*B_XX*x_X
00273     // where:
00274     //     x_R = Q_R'*x
00275     //     x_X = Q_X'*x
00276     //
00277     SpVector
00278       x_R,
00279       x_X;
00280     // x_R = Q_R'*x
00281     V_MtV( &x_R, Q_R(), trans, x );
00282     // x_X = Q_X'*x
00283     V_MtV( &x_X, Q_X(), trans, x );
00284     // y = b*y + a*Q_R*B_RR*x_R
00285     AbstractLinAlgPack::Vp_StPtMtV(
00286       y, a, Q_R(), no_trans, *B_RR_ptr(), no_trans, x_R(), b );
00287     // y += a*Q_R*op(B_RX)*x_X + a*Q_X*op(B_RX')*x_R
00288     if( B_RX_ptr().get() ) {
00289       AbstractLinAlgPack::Vp_StPtMtV(
00290         y, a, Q_R(), no_trans, *B_RX_ptr(), B_RX_trans(), x_X() );
00291       AbstractLinAlgPack::Vp_StPtMtV(
00292         y, a, Q_X(), no_trans, *B_RX_ptr(), trans_not(B_RX_trans()), x_R() );
00293     }
00294     // y += a*Q_X*B_XX*x_X
00295     AbstractLinAlgPack::Vp_StPtMtV(
00296       y, a, Q_X(), no_trans, *B_XX_ptr(), no_trans, x_X() );
00297   }
00298 }
00299 
00300 void MatrixHessianSuperBasic::Vp_StPtMtV(
00301   DVectorSlice* y, value_type a
00302   , const GenPermMatrixSlice& P, BLAS_Cpp::Transp P_trans
00303   , BLAS_Cpp::Transp M_trans
00304   , const DVectorSlice& x, value_type b ) const
00305 {
00306   using BLAS_Cpp::no_trans;
00307   using BLAS_Cpp::trans;
00308   using BLAS_Cpp::trans_not;
00309   using AbstractLinAlgPack::V_MtV;
00310   using DenseLinAlgPack::Vt_S;
00311   using LinAlgOpPack::V_MtV;
00312   namespace slap = AbstractLinAlgPack;
00313 
00314   assert_initialized();
00315 
00316   //
00317   // y = b*y + a * op(P) * B * x
00318   //
00319   // =>
00320   //
00321   // y = b*y + a * op(P)*(Q_R*B_RR*Q_R' + Q_R*op(B_RX)*Q_X' + Q_X*op(B_RX')*Q_R + Q_X*B_XX*Q_X')*x
00322   //   
00323   //   = b*y + a*op(P)*Q_R*B_RR*Q_R'*x     + a*op(P)*Q_R*op(B_RX)*Q_X'*x
00324   //         + a*op(P)*Q_X*op(B_RX')*Q_R*x + a*op(P)*Q_X*B_XX*Q_X'*x
00325   //
00326   // In order to implement the above as efficiently as possible we need to minimize the
00327   // computations with the constituent matrices.  First off we will compute
00328   // Q_RT_x = Q_R'*x (O(n_R)) and Q_XT_x = Q_X'*x (O(n_R)) neglect any terms where
00329   // Q_RT_x.nz() == 0 or Q_XT_x.nz() == 0.  We will also determine if op(P)*Q_R == 0 (O(n_R))
00330   // or op(P)*Q_X == 0 (O(n_X)) and neglect these terms if the are zero.
00331   // Hopefully this work will allow us to skip as many computations as possible.
00332   //
00333   LinAlgOpPack::Vp_MtV_assert_sizes(y->size(),P.rows(),P.cols(),P_trans
00334     , BLAS_Cpp::rows( rows(), cols(), M_trans) );
00335   LinAlgOpPack::Vp_MtV_assert_sizes( BLAS_Cpp::cols( P.rows(), P.cols(), P_trans)
00336     ,rows(),cols(),M_trans,x.size());
00337   // Q_R'*x
00338   SpVector Q_RT_x;
00339   if(n_R_) {
00340     slap::V_MtV( &Q_RT_x, Q_R(), trans, x );
00341   }
00342   // Q_X'*x
00343   SpVector Q_XT_x;
00344   if(n_ > n_R_) {
00345     slap::V_MtV( &Q_XT_x, Q_X(), trans, x );
00346   }
00347   // op(P)*Q_R overlap
00348   size_type P_Q_R_nz = 0;
00349   AbstractLinAlgPack::intersection( P, P_trans, Q_R(), no_trans, &P_Q_R_nz );
00350   // op(P)*Q_X overlap
00351   size_type P_Q_X_nz = 0;
00352   AbstractLinAlgPack::intersection( P, P_trans, Q_X(), no_trans, &P_Q_X_nz );
00353   // y = b*y
00354   if(b==0.0)      *y = 0.0;
00355   else if(b!=1.0) Vt_S(y,b);
00356   // 
00357   DVector t; // ToDo: use workspace
00358   // y += a*op(P)*Q_R*B_RR*Q_R'*x
00359   if( P_Q_R_nz && Q_RT_x.nz() ) {
00360     t.resize(n_);
00361     slap::Vp_StPtMtV( &t(), 1.0, Q_R(), no_trans, *B_RR_ptr(), no_trans, Q_RT_x() );
00362     slap::Vp_StMtV( y, a, P, P_trans, t() );
00363   }
00364   // y += a*op(P)*Q_R*op(B_RX)*Q_X'*x
00365   if( P_Q_R_nz && B_RX_ptr().get() && Q_XT_x.nz() ) {
00366     t.resize(n_);
00367     slap::Vp_StPtMtV( &t(), 1.0, Q_R(), no_trans, *B_RX_ptr(), B_RX_trans(), Q_XT_x() );
00368     slap::Vp_StMtV( y, a, P, P_trans, t() );
00369   }
00370   // y += a*op(P)*Q_X*op(B_RX')*Q_R*x
00371   if( P_Q_X_nz && B_RX_ptr().get() && Q_RT_x.nz() ) {
00372     t.resize(n_);
00373     slap::Vp_StPtMtV( &t(), 1.0, Q_X(), no_trans, *B_RX_ptr(), trans_not(B_RX_trans()), Q_RT_x() );
00374     slap::Vp_StMtV( y, a, P, P_trans, t() );
00375   }
00376   // y += a*op(P)*Q_X*B_XX*Q_X'*x
00377   if( P_Q_X_nz && Q_XT_x.nz() ) {
00378     t.resize(n_);
00379     slap::Vp_StPtMtV( &t(), 1.0, Q_X(), no_trans, *B_XX_ptr(), no_trans, Q_XT_x() );
00380     slap::Vp_StMtV( y, a, P, P_trans, t() );
00381   }
00382 }
00383 
00384 value_type MatrixHessianSuperBasic::transVtMtV(
00385   const SpVectorSlice& x1, BLAS_Cpp::Transp B_trans
00386   , const SpVectorSlice& x2 ) const
00387 {
00388   using BLAS_Cpp::no_trans;
00389   using BLAS_Cpp::trans;
00390   assert_initialized();
00391   DenseLinAlgPack::Vp_MtV_assert_sizes( x1.size(), rows(), cols(), B_trans, x1.size() );
00392   if( n_ == n_R_ ) {
00393     //
00394     // B = Q_R*B_RR*Q_R'
00395     //
00396     // a = x1'*Q_R*B_RR*Q_R'*x2
00397     //
00398     if( Q_R().is_identity() ) {
00399       return AbstractLinAlgPack::transVtMtV( x1, *B_RR_ptr(), no_trans, x2 );
00400     }
00401     else {
00402       if( x1.overlap(x2) == DenseLinAlgPack::SAME_MEM ) {
00403         SpVector Q_RT_x2;
00404         AbstractLinAlgPack::V_MtV( &Q_RT_x2, Q_R(), trans, x2 );
00405         SpVectorSlice Q_RT_x2_slc = Q_RT_x2();
00406         return AbstractLinAlgPack::transVtMtV(
00407           Q_RT_x2_slc, *B_RR_ptr(), no_trans, Q_RT_x2_slc );
00408        }
00409       else {
00410         SpVector Q_RT_x2;
00411         AbstractLinAlgPack::V_MtV( &Q_RT_x2, Q_R(), trans, x2 );
00412         SpVector Q_RT_x1;
00413         AbstractLinAlgPack::V_MtV( &Q_RT_x1, Q_R(), trans, x1 );
00414         return AbstractLinAlgPack::transVtMtV(
00415           Q_RT_x1(), *B_RR_ptr(), no_trans, Q_RT_x2() );
00416       }
00417     }
00418   }
00419   else if( n_R_ == 0 ) {
00420     //
00421     // B = Q_X *B_XX * Q_X'
00422     //
00423     TEST_FOR_EXCEPT(true); // ToDo: Implement this!
00424   }
00425   else {
00426     //
00427     // B = [ Q_R  Q_X  ] * [   B_RR      op(B_RX) ] * [ Q_R' ]
00428     //                     [ op(B_RX')      B_XX  ]   [ Q_X' ]
00429     //
00430     //
00431     // a = x1'*B*x2
00432     // =>
00433     // a = x1' * [ Q_R  Q_X  ] * [   B_RR      op(B_RX) ] * [ Q_R' ] * x2
00434     //                           [ op(B_RX')      B_XX  ]   [ Q_X' ]
00435     //
00436     // a = x1'*Q_R*B_RR*Q_R'*x2 + 2*x1'*Q_R*op(B_RX)*Q_X'*x2 + x1'*Q_X*B_XX*Q_X'*x2
00437     //
00438     if( x1.overlap(x2) == DenseLinAlgPack::SAME_MEM ) {
00439       // a = x1'*Q_R*B_RR*Q_R'*x1 + 2*x1'*Q_R*op(B_RX)*Q_X'*x1 + x1'*Q_X*B_XX*Q_X'*x1
00440       SpVector Q_RT_x1;
00441       if( Q_R().nz() )
00442         AbstractLinAlgPack::V_MtV( &Q_RT_x1, Q_R(), trans, x1 );
00443       SpVector Q_XT_x1;
00444       if( Q_X().nz() )
00445         AbstractLinAlgPack::V_MtV( &Q_XT_x1, Q_X(), trans, x1 );
00446       SpVectorSlice Q_RT_x1_slc = Q_RT_x1();
00447       SpVectorSlice Q_XT_x1_slc = Q_XT_x1();
00448       return
00449         ( Q_R().nz()
00450           ? AbstractLinAlgPack::transVtMtV(
00451             Q_RT_x1_slc, *B_RR_ptr(), no_trans, Q_RT_x1_slc )
00452           : 0.0
00453           )
00454         + 2*(  B_RX_ptr().get() && Q_R().nz() && Q_X().nz()
00455              ? AbstractLinAlgPack::transVtMtV(
00456                Q_RT_x1_slc, *B_RX_ptr(), B_RX_trans(), Q_XT_x1_slc )
00457              : 0.0
00458           )
00459         + ( Q_X().nz()
00460           ? AbstractLinAlgPack::transVtMtV(
00461             Q_XT_x1_slc, *B_XX_ptr(), no_trans, Q_XT_x1_slc )
00462           : 0.0
00463           );
00464     }
00465     else {
00466       TEST_FOR_EXCEPT(true); // ToDo: Implement this!
00467     }
00468   }
00469   return 0.0; // Will never be executed!
00470 }
00471 
00472 // Private
00473 
00474 void MatrixHessianSuperBasic::assert_initialized() const
00475 {
00476   if( !n_ )
00477     throw std::logic_error(
00478       "MatrixHessianSuperBasic::assert_initialized() : Error, "
00479       "The matrix is not initialized yet" );
00480 }
00481 
00482 } // end namespace ConstrainedOptPack

Generated on Thu Sep 18 12:35:14 2008 for MOOCHO (Single Doxygen Collection) by doxygen 1.3.9.1