)]}'
{
  "commit": "b44cfdef25f6bf0917a23b3fd65cce38aa6a3362",
  "tree": "4863e157912fb6567c69ad1817d8423b9855ca17",
  "parents": [
    "4ad91490827f2ebebcc70d17e63ef653bf06fd0d"
  ],
  "author": {
    "name": "Sameer Agarwal",
    "email": "sameeragarwal@google.com",
    "time": "Mon Sep 29 07:53:54 2014 -0700"
  },
  "committer": {
    "name": "Sameer Agarwal",
    "email": "sameeragarwal@google.com",
    "time": "Mon Sep 29 10:29:32 2014 -0700"
  },
  "message": "Let ITERATIVE_SCHUR use an explicit Schur Complement matrix.\n\nUp till now ITERATIVE_SCHUR evaluates matrix-vector products\nbetween the Schur complement and a vector implicitly by exploiting\nthe algebraic expression for the Schur complement.\n\nThis cost of this evaluation scales with the number of non-zeros\nin the Jacobian.\n\nFor small to medium sized problems there is a sweet spot where\ncomputing the Schur complement is cheap enough that it is much\nmore efficient to explicitly compute it and use it for evaluating\nthe matrix-vector products.\n\nThis changes implements support for an explicit Schur complement\nin ITERATIVE_SCHUR in combination with the SCHUR_JACOBI preconditioner.\n\nAPI wise a new bool Solver::Options::use_explicit_schur_complement\nhas been added.\n\nThe implementation extends the SparseSchurComplementSolver to use\nConjugate Gradients.\n\nExample speedup:\n\nuse_explicit_schur_complement \u003d false\n\nTime (in seconds):\nPreprocessor                            0.585\n\n  Residual evaluation                   0.319\n  Jacobian evaluation                   1.590\n  Linear solver                        25.685\nMinimizer                              27.990\n\nPostprocessor                           0.010\nTotal                                  28.585\n\nuse_explicit_schur_complement \u003d true\n\nTime (in seconds):\nPreprocessor                            0.638\n\n  Residual evaluation                   0.318\n  Jacobian evaluation                   1.507\n  Linear solver                         5.930\nMinimizer                               8.144\n\nPostprocessor                           0.010\nTotal                                   8.791\n\nWhich indicates an end-to-end speedup of more than 3x, with the linear\nsolver being sped up by \u003e 4x.\n\nThe idea to explore this optimization was inspired by the recent paper:\n\nMining structure fragments for smart bundle adjustment\nL. Carlone, P. Alcantarilla, H. Chiu, K. Zsolt, F. Dellaert\nBritish Machine Vision Conference, 2014\n\nwhich uses a more complicated algorithm to compute parts of the\nSchur complement to speed up the matrix-vector product.\n\nChange-Id: I95324af0ab351faa1600f5204039a1d2a64ae61d\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "296611f167e6c7a82d9ccf62faa05d9ca1c39d0d",
      "old_mode": 33188,
      "old_path": "examples/bundle_adjuster.cc",
      "new_id": "7787d93585446bcde9f7cdb356a32a60ad4b78e3",
      "new_mode": 33188,
      "new_path": "examples/bundle_adjuster.cc"
    },
    {
      "type": "modify",
      "old_id": "0af34cacef284b506aaf47d8ee12657ab4002b11",
      "old_mode": 33188,
      "old_path": "include/ceres/solver.h",
      "new_id": "a5efa2a39151924e96162d991c77d59c45883d66",
      "new_mode": 33188,
      "new_path": "include/ceres/solver.h"
    },
    {
      "type": "modify",
      "old_id": "d905ec2e1fdd362210aba9dd2de2a4beb6dcca03",
      "old_mode": 33188,
      "old_path": "internal/ceres/linear_solver.cc",
      "new_id": "e479b751363de7cf1c0a755d084f49983dcb219b",
      "new_mode": 33188,
      "new_path": "internal/ceres/linear_solver.cc"
    },
    {
      "type": "modify",
      "old_id": "58b9044b8f99f642066406f7086e5622a1f96eb2",
      "old_mode": 33188,
      "old_path": "internal/ceres/linear_solver.h",
      "new_id": "5f59765f074478675049f2428e388affaad631f6",
      "new_mode": 33188,
      "new_path": "internal/ceres/linear_solver.h"
    },
    {
      "type": "modify",
      "old_id": "d2aa168c807063ffe684122a72f84d63b8c4cf47",
      "old_mode": 33188,
      "old_path": "internal/ceres/schur_complement_solver.cc",
      "new_id": "33f812b8c964c4af4b40d70ffddea408230c9e56",
      "new_mode": 33188,
      "new_path": "internal/ceres/schur_complement_solver.cc"
    },
    {
      "type": "modify",
      "old_id": "1b431dc534036fdfa6343822208d09d78a1b75f0",
      "old_mode": 33188,
      "old_path": "internal/ceres/schur_complement_solver.h",
      "new_id": "93d23e3d0121446a2392f414ed3e8766cc62736b",
      "new_mode": 33188,
      "new_path": "internal/ceres/schur_complement_solver.h"
    },
    {
      "type": "modify",
      "old_id": "f90045baac9f522ef19fe08c11d3822b81eeda26",
      "old_mode": 33188,
      "old_path": "internal/ceres/solver.cc",
      "new_id": "e1c5ee30ba5d42e7711a330be4cc7947ed1b1c71",
      "new_mode": 33188,
      "new_path": "internal/ceres/solver.cc"
    },
    {
      "type": "modify",
      "old_id": "ba3baa12c1f3acf0807b69c44367dccb84f3b11e",
      "old_mode": 33188,
      "old_path": "internal/ceres/trust_region_preprocessor.cc",
      "new_id": "22ea1ec8c805dab662a29c2f6d2dbd2119c7e3fa",
      "new_mode": 33188,
      "new_path": "internal/ceres/trust_region_preprocessor.cc"
    }
  ]
}