)]}'
{
  "commit": "36c73c26bb3fd9b319435aa9702a110678239d9c",
  "tree": "9c7aee840179c036498d61d9cb8dca233232daf8",
  "parents": [
    "44c79b89c9289874fbc0faa20c0a21e440556e10"
  ],
  "author": {
    "name": "Sameer Agarwal",
    "email": "sameeragarwal@google.com",
    "time": "Fri May 17 22:52:21 2013 -0700"
  },
  "committer": {
    "name": "Sameer Agarwal",
    "email": "sameeragarwal@google.com",
    "time": "Fri May 17 22:52:21 2013 -0700"
  },
  "message": "Stablize the schur ordering algorithm.\n\nThe schur ordering is used to construct an elimination\nordering for Schur type solvers when the user has not\nsupplied an elimination ordering.\n\nThe ordering algorithm does an ordered traversal of the\nsparsity graph of the Hessian. The order in which this is\ndone used to be determined by the degree of the parameter\nblocks with ties broken arbitrarily using the memory address\nof the parameter blocks.\n\nThis introduced non-determinism in the solver, causing subtle\nnumerical differences in the value of the solution everytime\nthe solve was run.\n\nThis change introduces ComputeStableSchurOrdering which utilizes\na new function StableIndependentSetOrdering. The latter takes\nas input an ordering of the vertices of the graph which is used\nto break ties when ordering the vertice by degree. The former\nconstructs such an ordering by using the order in which the\nparameter blocks were added to the Problem.\n\nIn this way, as long as the construction of the problem is\ndeterministic, the schur ordering will always be deterministic\ntoo.\n\nI have chosen not to delete the existing unstable implementations\nof these functions as they are used by the inner iteration\nminimizer.\n\nSometime in the near future I will clean up some of the duplicate\ncode and see if we can move all the code to using a stable ordering.\n\nChange-Id: I8fbfa240d7307a2c3fe9b135f6968aa410d78780\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "2e6eec0e6d8494a85ed45f913930b79a14e1cf20",
      "old_mode": 33188,
      "old_path": "internal/ceres/graph_algorithms.h",
      "new_id": "f38a13fdf13cf79a49e36034ef960c83e6617876",
      "new_mode": 33188,
      "new_path": "internal/ceres/graph_algorithms.h"
    },
    {
      "type": "modify",
      "old_id": "78a0452cc8a4f3c38b230533bb164114426d2011",
      "old_mode": 33188,
      "old_path": "internal/ceres/graph_algorithms_test.cc",
      "new_id": "7c244766b56a161be8a7446d5cfeb9f91b99f711",
      "new_mode": 33188,
      "new_path": "internal/ceres/graph_algorithms_test.cc"
    },
    {
      "type": "modify",
      "old_id": "e8f626f8e8027855aca06f8eaff1ee8dd30860ec",
      "old_mode": 33188,
      "old_path": "internal/ceres/parameter_block_ordering.cc",
      "new_id": "190715bee4388bf2fa97e12945f20a23f4f69f5e",
      "new_mode": 33188,
      "new_path": "internal/ceres/parameter_block_ordering.cc"
    },
    {
      "type": "modify",
      "old_id": "a5277a44c70631e65b91de61d0be9ac9fa065127",
      "old_mode": 33188,
      "old_path": "internal/ceres/parameter_block_ordering.h",
      "new_id": "4675cb8dc7c61534ceee1aaf7de416a835e26c60",
      "new_mode": 33188,
      "new_path": "internal/ceres/parameter_block_ordering.h"
    },
    {
      "type": "modify",
      "old_id": "ddcbb373609539311fa0e07990e36ec5f3b626b7",
      "old_mode": 33188,
      "old_path": "internal/ceres/solver_impl.cc",
      "new_id": "56993c874240b2da6ee4fbf1e664aa02a98f395e",
      "new_mode": 33188,
      "new_path": "internal/ceres/solver_impl.cc"
    }
  ]
}