)]}'
{
  "commit": "9189f4ea4bb2d71ea7f6b9d9bd3290415aee323d",
  "tree": "01c7e7b2e26ca41368b0ae3ca7cf65cfe8307625",
  "parents": [
    "f7ed22efc3afee36aae71a4f7949b3d327b87f11"
  ],
  "author": {
    "name": "Sameer Agarwal",
    "email": "sameeragarwal@google.com",
    "time": "Fri Apr 19 17:09:49 2013 -0700"
  },
  "committer": {
    "name": "Sameer Agarwal",
    "email": "sameeragarwal@google.com",
    "time": "Fri Apr 19 19:27:23 2013 -0700"
  },
  "message": "Enable pre-ordering for SPARSE_NORMAL_CHOLESKY.\n\nSparse Cholesky factorization algorithms use a fill-reducing\nordering to permute the columns of the Jacobian matrix. There\nare two ways of doing this.\n\n1. Compute the Jacobian matrix in some order and then have the\n   factorization algorithm permute the columns of the Jacobian.\n\n2. Compute the Jacobian with its columns already permuted.\n\nThe first option incurs a significant memory penalty. The\nfactorization algorithm has to make a copy of the permuted\nJacobian matrix.\n\nStarting with this change Ceres pre-permutes the columns of the\nJacobian matrix and generally speaking, there is no performance\npenalty for doing so.\n\nIn some rare cases, it is worth using a more complicated\nreordering algorithm which has slightly better runtime\nperformance at the expense of an extra copy of the Jacobian\nmatrix. Setting Solver::Options::use_postordering to true\nenables this tradeoff.\n\nThis change also removes Solver::Options::use_block_amd\nas an option. All matrices are ordered using their block\nstructure. The ability to order them by their scalar\nsparsity structure has been removed.\n\nHere is what performance on looks like on some BAL problems.\n\nMemory\n\u003d\u003d\u003d\u003d\u003d\u003d\n                                     HEAD         pre-ordering\n16-22106                      137957376.0          113516544.0\n49-7776                        56688640.0           46628864.0\n245-198739                   1718005760.0         1383550976.0\n257-65132                     387715072.0          319512576.0\n356-226730                   2014826496.0         1626087424.0\n744-543562                   4903358464.0         3957878784.0\n1024-110968                   968626176.0          822071296.0\n\nTime\n\u003d\u003d\u003d\u003d\n                                     HEAD         pre-ordering\n16-22106                              3.8                  3.7\n49-7776                               1.9                  1.8\n245-198739                           82.6                 81.9\n257-65132                            14.0                 13.4\n356-226730                           98.8                 95.8\n744-543562                          325.2                301.6\n1024-110968                          42.1                 37.1\n\nChange-Id: I6b2e25f3fed7310f88905386a7898ac94d37467e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "8fff9f0bcdf6d73df60e74f54bb65e8461e297f7",
      "old_mode": 33188,
      "old_path": "examples/bundle_adjuster.cc",
      "new_id": "59420c91a4f181614e69e97d088effbc15c49a76",
      "new_mode": 33188,
      "new_path": "examples/bundle_adjuster.cc"
    },
    {
      "type": "modify",
      "old_id": "8c2ff32d80b0361587729f246b27a9a3625a1cbe",
      "old_mode": 33188,
      "old_path": "include/ceres/solver.h",
      "new_id": "97d082d80e0050a8732416155f1215ee1dbb6b3d",
      "new_mode": 33188,
      "new_path": "include/ceres/solver.h"
    },
    {
      "type": "modify",
      "old_id": "cf5562ac77183a0f8875bb75cac29a33625f012b",
      "old_mode": 33188,
      "old_path": "internal/ceres/iterative_schur_complement_solver.cc",
      "new_id": "15e0bdcd81a88fb8951200a35b8d825ba8fb12b0",
      "new_mode": 33188,
      "new_path": "internal/ceres/iterative_schur_complement_solver.cc"
    },
    {
      "type": "modify",
      "old_id": "f4bd0fb6f9f1917952a7ba49a6b6594fc8bd73af",
      "old_mode": 33188,
      "old_path": "internal/ceres/linear_solver.h",
      "new_id": "ca10faa24b46b2c2ae881b88a32d7b216192cdb6",
      "new_mode": 33188,
      "new_path": "internal/ceres/linear_solver.h"
    },
    {
      "type": "modify",
      "old_id": "bfc8464db173c35dfcfd8f6a9ef1b01f71b978e0",
      "old_mode": 33188,
      "old_path": "internal/ceres/preconditioner.h",
      "new_id": "d7c882936874bfcc372405fe27960dccb36e606c",
      "new_mode": 33188,
      "new_path": "internal/ceres/preconditioner.h"
    },
    {
      "type": "modify",
      "old_id": "875f4551044cb6d5e559a83e91b40836c00e3dae",
      "old_mode": 33188,
      "old_path": "internal/ceres/schur_complement_solver.cc",
      "new_id": "8afb121501596c1e5bbe560dd60ad6ff3e4c1937",
      "new_mode": 33188,
      "new_path": "internal/ceres/schur_complement_solver.cc"
    },
    {
      "type": "modify",
      "old_id": "0d7b83c4074b0d35de9397931f163993672b8bbf",
      "old_mode": 33188,
      "old_path": "internal/ceres/solver_impl.cc",
      "new_id": "8217484e609d597ee5ee99bcc69ba00b35415136",
      "new_mode": 33188,
      "new_path": "internal/ceres/solver_impl.cc"
    },
    {
      "type": "modify",
      "old_id": "0cd064b556f796dab276cdfff64fae24427098d6",
      "old_mode": 33188,
      "old_path": "internal/ceres/sparse_normal_cholesky_solver.cc",
      "new_id": "bc1f98334ae823d37a6ae19422a5bd0e77fc808b",
      "new_mode": 33188,
      "new_path": "internal/ceres/sparse_normal_cholesky_solver.cc"
    },
    {
      "type": "modify",
      "old_id": "0b0d593cf0cb64ae8ebeb158d386ae7858941aa2",
      "old_mode": 33188,
      "old_path": "internal/ceres/unsymmetric_linear_solver_test.cc",
      "new_id": "c8a15c02658556f850c0d5ad99df6ad8749a87ed",
      "new_mode": 33188,
      "new_path": "internal/ceres/unsymmetric_linear_solver_test.cc"
    },
    {
      "type": "modify",
      "old_id": "f5c46bfcc6852add1069241c2fd11f64c16594e2",
      "old_mode": 33188,
      "old_path": "internal/ceres/visibility_based_preconditioner.cc",
      "new_id": "4b1e26af6d2eebc837df873bc863f8b96408e78d",
      "new_mode": 33188,
      "new_path": "internal/ceres/visibility_based_preconditioner.cc"
    }
  ]
}