Home | History | Annotate | Download | only in ceres
      1 // Ceres Solver - A fast non-linear least squares minimizer
      2 // Copyright 2010, 2011, 2012 Google Inc. All rights reserved.
      3 // http://code.google.com/p/ceres-solver/
      4 //
      5 // Redistribution and use in source and binary forms, with or without
      6 // modification, are permitted provided that the following conditions are met:
      7 //
      8 // * Redistributions of source code must retain the above copyright notice,
      9 //   this list of conditions and the following disclaimer.
     10 // * Redistributions in binary form must reproduce the above copyright notice,
     11 //   this list of conditions and the following disclaimer in the documentation
     12 //   and/or other materials provided with the distribution.
     13 // * Neither the name of Google Inc. nor the names of its contributors may be
     14 //   used to endorse or promote products derived from this software without
     15 //   specific prior written permission.
     16 //
     17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
     18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     20 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
     21 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     22 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     23 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     24 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     25 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     26 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     27 // POSSIBILITY OF SUCH DAMAGE.
     28 //
     29 // Author: sameeragarwal (at) google.com (Sameer Agarwal)
     30 
     31 #ifndef CERES_INTERNAL_PARAMETER_BLOCK_ORDERING_H_
     32 #define CERES_INTERNAL_PARAMETER_BLOCK_ORDERING_H_
     33 
     34 #include <vector>
     35 #include "ceres/ordered_groups.h"
     36 #include "ceres/graph.h"
     37 #include "ceres/types.h"
     38 
     39 namespace ceres {
     40 namespace internal {
     41 
     42 class Program;
     43 class ParameterBlock;
     44 
     45 // Uses an approximate independent set ordering to order the parameter
     46 // blocks of a problem so that it is suitable for use with Schur
     47 // complement based solvers. The output variable ordering contains an
     48 // ordering of the parameter blocks and the return value is size of
     49 // the independent set or the number of e_blocks (see
     50 // schur_complement_solver.h for an explanation). Constant parameters
     51 // are added to the end.
     52 //
     53 // The ordering vector has the structure
     54 //
     55 // ordering = [independent set,
     56 //             complement of the independent set,
     57 //             fixed blocks]
     58 int ComputeSchurOrdering(const Program& program,
     59                          vector<ParameterBlock* >* ordering);
     60 
     61 // Same as above, except that ties while computing the independent set
     62 // ordering are resolved in favour of the order in which the parameter
     63 // blocks occur in the program.
     64 int ComputeStableSchurOrdering(const Program& program,
     65                                vector<ParameterBlock* >* ordering);
     66 
     67 // Use an approximate independent set ordering to decompose the
     68 // parameter blocks of a problem in a sequence of independent
     69 // sets. The ordering covers all the non-constant parameter blocks in
     70 // the program.
     71 void ComputeRecursiveIndependentSetOrdering(const Program& program,
     72                                             ParameterBlockOrdering* ordering);
     73 
     74 // Builds a graph on the parameter blocks of a Problem, whose
     75 // structure reflects the sparsity structure of the Hessian. Each
     76 // vertex corresponds to a parameter block in the Problem except for
     77 // parameter blocks that are marked constant. An edge connects two
     78 // parameter blocks, if they co-occur in a residual block.
     79 Graph<ParameterBlock*>* CreateHessianGraph(const Program& program);
     80 
     81 }  // namespace internal
     82 }  // namespace ceres
     83 
     84 #endif  // CERES_INTERNAL_PARAMETER_BLOCK_ORDERING_H_
     85