include/ceres/ordering.h

// Ceres Solver - A fast non-linear least squares minimizer
// Copyright 2012 Google Inc. All rights reserved.
// http://code.google.com/p/ceres-solver/
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// * Redistributions of source code must retain the above copyright notice,
//   this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright notice,
//   this list of conditions and the following disclaimer in the documentation
//   and/or other materials provided with the distribution.
// * Neither the name of Google Inc. nor the names of its contributors may be
//   used to endorse or promote products derived from this software without
//   specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.
//
// Author: sameeragarwal@google.com (Sameer Agarwal)

#include <map>
#include <set>
#include "ceres/internal/port.h"
#include "glog/logging.h"

namespace ceres {

// The order in which variables are eliminated in a linear solver can
// have a significant of impact on the efficiency and accuracy of the
// method. e.g., when doing sparse Cholesky factorization, there are
// matrices for which a good ordering will give a Cholesky factor with
// O(n) storage, where as a bad ordering will result in an completely
// dense factor.
//
// Ceres allows the user to provide varying amounts of hints to the
// solver about the variable elimination ordering to use. This can
// range from no hints, where the solver is free to decide the best
// possible ordering based on the user's choices like the linear
// solver being used, to an exact order in which the variables should
// be eliminated, and a variety of possibilities in between. Instances
// of the Ordering class are used to communicate this infornation to
// Ceres.
//
// Formally an ordering is an ordered partitioning of the parameter
// blocks, i.e, each parameter block belongs to exactly one group, and
// each group has a unique integer associated with it, that determines
// its order in the set of groups.
//
// Given such an ordering, Ceres ensures that the parameter blocks in
// the lowest numbered group are eliminated first, and then the
// parmeter blocks in the next lowest numbered group and so on. Within
// each group, Ceres is free to order the parameter blocks as it
// chooses.
// e.g. Consider the linear system
//
//   x + y = 3
//   2x + 3y = 7
//
// There are two ways in which it can be solved. First eliminating x
// from the two equations, solving for y and then back substituting
// for x, or first eliminating y, solving for x and back substituting
// for y. The user can construct three orderings here.
//
//   {0: x}, {1: y} - eliminate x first.
//   {0: y}, {1: x} - eliminate y first.
//   {0: x, y}      - Solver gets to decide the elimination order.
//
// Thus, to have Ceres determine the ordering automatically using
// heuristics, put all the variables in group 0 and to control the
// ordering for every variable, create groups 0..N-1, one per
// variable, in the desired order.
//
// Bundle Adjustment
// -----------------
//
// A particular case of interest is bundle adjustment, where the user
// has two options. The default is to not specify an ordering at all,
// the solver will see that the user wants to use a Schur type solver
// and figure out the right elimination ordering.
//
// But if the user already knows what parameter blocks are points and
// what are cameras, they can save preprocessing time by partitioning
// the parameter blocks into two groups, one for the points and one
// for the cameras, where the group containing the points has an id
// smaller than the group containing cameras.
class Ordering {
 public:
  // Add a parameter block to a group with id group_id. If a group
  // with this id does not exist, one is created. This method can be
  // called any number of times for a parameter block.
  void AddParameterBlockToGroup(double* parameter_block, int group_id);

  // Remove the parameter block from the ordering, no matter what
  // group it is in. If the parameter block is not known to the
  // ordering, calling this method will result in a crash.
  void RemoveParameterBlock(double* parameter_block);

  // Return the group id for the parameter block. If the parameter
  // block is not known to the Ordering, calling this method results
  // in a crash.
  int GroupIdForParameterBlock(double* parameter_block) const;

  // This function always succeeds. For a group_id unknown to the
  // ordering is treated as empty groups and the function returns
  // zero.
  int GroupSize(int group_id) const;

  bool ContainsParameterBlock(double* parameter_block) const;
  int NumParameterBlocks() const;
  int NumGroups() const;
  const map<int, set<double*> >& group_id_to_parameter_blocks() const;

 private:
  map<int, set<double*> > group_id_to_parameter_blocks_;
  map<double*, int>  parameter_block_to_group_id_;
};

}  // namespace ceres