)]}'
{
  "commit": "39ec5e8f99c595226ab3cd760d4945e61c31fc57",
  "tree": "26193762df54e1dfeba76a5712af2b664409f8db",
  "parents": [
    "aa62dd86a8cd978cd75245a711ef3bbdd0defb15"
  ],
  "author": {
    "name": "Sameer Agarwal",
    "email": "sameeragarwal@google.com",
    "time": "Sat May 14 08:05:49 2022 -0700"
  },
  "committer": {
    "name": "Sameer Agarwal",
    "email": "sameeragarwal@google.com",
    "time": "Thu May 19 12:36:20 2022 -0700"
  },
  "message": "Add Nested Dissection based fill reducing ordering\n\nWith this change, the user can now choose between Approximate Minimum\nDegree and Nested Dissection as a fill reducing algorithm when using\na sparse direct factorization based linear solver like SPARSE_NORMAL_CHOLESKY\nor SPARSE_SCHUR.\n\nCurrenly only SUITE_SPARSE is supported. It requires that\nSuiteSparse be compiled with Metis support enabled.\n\nOn most problems AMD is still the better choice, but in some cases\nlike the grid3D dataset from https://lucacarlone.mit.edu/datasets/\nthe solution time with AMD is 57s and with NESDIS 38 on my M1 Mac.\n\nOn some other problems at Google we have observed speedups of 10x,\nthere is also a corresponding decrease in the total amount of memory\nused.\n\nThis patch is based on the original work done by NeroBurner in\nhttps://ceres-solver-review.googlesource.com/c/ceres-solver/+/20580\n\n1. Add a new enum to the public api LinearSolverOrderingType and\n   a setting Solver::Options::linear_solver_ordering_type.\n2. TrustRegionPreprocessor had some complicated logic which determined\n   when linear solvers should reorder their matrices on their own and not\n   this has been refactored into a more readable function that lives\n   inside reorder_program.h/cc.\n3. Plumbing in reorder_program.cc and trust_region_processor.cc to use\n   nested dissection.\n4. Update bundle_adjuster.cc to use nested dissection.\n\nChange-Id: I388b027934f86c58b4da2b65a4fa5204ea73bf40\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "d03c2ff59d89f17f49ed94a513c083888ce652a6",
      "old_mode": 33188,
      "old_path": "examples/bundle_adjuster.cc",
      "new_id": "87e18e110b0371f50aa25a1107249e5b6a533e8c",
      "new_mode": 33188,
      "new_path": "examples/bundle_adjuster.cc"
    },
    {
      "type": "modify",
      "old_id": "026fc1c08306888a01870fdcc3eaddfb00cf2277",
      "old_mode": 33188,
      "old_path": "include/ceres/solver.h",
      "new_id": "43146b110b770d8fc31b10fa65b2e0f60d6fe162",
      "new_mode": 33188,
      "new_path": "include/ceres/solver.h"
    },
    {
      "type": "modify",
      "old_id": "e5224238129dc48dd8798d7f02d14dbc6343e0f7",
      "old_mode": 33188,
      "old_path": "include/ceres/types.h",
      "new_id": "2fc5abccd20ec637e89134703cbcdea65ffec609",
      "new_mode": 33188,
      "new_path": "include/ceres/types.h"
    },
    {
      "type": "modify",
      "old_id": "c6765fef7ee513abf36f8b600a787eb48d64fc31",
      "old_mode": 33188,
      "old_path": "internal/ceres/reorder_program.cc",
      "new_id": "1f50a39efa6473372d623f0574cda3549729513b",
      "new_mode": 33188,
      "new_path": "internal/ceres/reorder_program.cc"
    },
    {
      "type": "modify",
      "old_id": "64f40950458de8cd252c5a4e398bfa334212e938",
      "old_mode": 33188,
      "old_path": "internal/ceres/reorder_program.h",
      "new_id": "8ae456ec40ba70dd775520c06b80466e87f0cb26",
      "new_mode": 33188,
      "new_path": "internal/ceres/reorder_program.h"
    },
    {
      "type": "modify",
      "old_id": "0fbab4e10b7c31563c13827edc5b85cecdfa56ba",
      "old_mode": 33188,
      "old_path": "internal/ceres/reorder_program_test.cc",
      "new_id": "872f3812ca5e1f84006257773e30b5178c54b718",
      "new_mode": 33188,
      "new_path": "internal/ceres/reorder_program_test.cc"
    },
    {
      "type": "modify",
      "old_id": "150c5550fc9238e12314ff9b9dd43fd2a6331dfc",
      "old_mode": 33188,
      "old_path": "internal/ceres/solver.cc",
      "new_id": "dbaba3e8903d0b6b262527293b58ffae3278e911",
      "new_mode": 33188,
      "new_path": "internal/ceres/solver.cc"
    },
    {
      "type": "modify",
      "old_id": "9467b5ac649ce20640a54e763d1daa4b61d57347",
      "old_mode": 33188,
      "old_path": "internal/ceres/trust_region_preprocessor.cc",
      "new_id": "ed62aa9d82718decdfbf2707b0e522eee3d55eaa",
      "new_mode": 33188,
      "new_path": "internal/ceres/trust_region_preprocessor.cc"
    },
    {
      "type": "modify",
      "old_id": "48242678b46197786d39cf4662de0891f46eebe0",
      "old_mode": 33188,
      "old_path": "internal/ceres/types.cc",
      "new_id": "eea03123723ab0639cff2660cb5e209f1e46ee31",
      "new_mode": 33188,
      "new_path": "internal/ceres/types.cc"
    },
    {
      "type": "modify",
      "old_id": "bde28140673e72df868689755308dc77d49b3b0f",
      "old_mode": 33188,
      "old_path": "internal/ceres/visibility_based_preconditioner.cc",
      "new_id": "0a7b19f97e12f410bd33f02c8984357af3766b83",
      "new_mode": 33188,
      "new_path": "internal/ceres/visibility_based_preconditioner.cc"
    }
  ]
}