)]}'
{
  "commit": "f14f6bf9b7d3fbd2cab939cf4ad615b317e93c83",
  "tree": "7e9e8b4d474133ac8aba606c545ac65270362e67",
  "parents": [
    "d79f886eb87cb064e19eb12c1ad3d45bbed92198"
  ],
  "author": {
    "name": "Sameer Agarwal",
    "email": "sameeragarwal@google.com",
    "time": "Thu Dec 26 09:50:45 2013 -0800"
  },
  "committer": {
    "name": "Sameer Agarwal",
    "email": "sameeragarwal@google.com",
    "time": "Mon Dec 30 10:00:06 2013 -0800"
  },
  "message": "Speed up SPARSE_NORMAL_CHOLESKY when using CX_SPARSE.\n\nWhen using sparse cholesky factorization to solve the linear\nleast squares problem:\n\n  Ax \u003d b\n\nThere are two sources of computational complexity.\n\n1. Computing H \u003d A\u0027A\n2. Computing the sparse Cholesky factorization of H.\n\nDoing 1. using CX_SPARSE is particularly expensive, as it uses\na generic cs_multiply function which computes the structure of\nthe matrix H everytime, reallocates memory and does not take\nadvantage of the fact that the matrix being computed is a symmetric\nouter product.\n\nThis change adds a custom symmetric outer product algorithm for\nCompressedRowSparseMatrix.\n\nIt has a symbolic phase, where it computes the sparsity structure\nof the output matrix and a \"program\" which allows the actual\nmultiplication routine to determine exactly which entry in the\nvalues array each term in the product contributes to.\n\nWith these two bits of information, the outer product H \u003d A\u0027A\ncan be computed extremely fast without any reasoning about\nthe structure of H.\n\nFurther gains in efficiency are made by exploiting the block\nstructure of A.\n\nWith this change, SPARSE_NORMAL_CHOLESKY with CX_SPARSE as the\nbackend results in \u003e 300% speedup for some problems.\n\nThe symbolic analysis phase of the solver is a bit more expensive\nnow but the increased cost is made up in 3-4 iterations.\n\nChange-Id: I5e4a72b4d03ba41b378a2634330bc22b299c0f12\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "439270ed3bc46a40c8c614892079d1f2e9b6a783",
      "old_mode": 33188,
      "old_path": "internal/ceres/compressed_row_sparse_matrix.cc",
      "new_id": "34f31ab6c7fcb6b015e779935ec3f53496c452d7",
      "new_mode": 33188,
      "new_path": "internal/ceres/compressed_row_sparse_matrix.cc"
    },
    {
      "type": "modify",
      "old_id": "c5721eb888abfd033908d2dfe29a9796d0ae9bd9",
      "old_mode": 33188,
      "old_path": "internal/ceres/compressed_row_sparse_matrix.h",
      "new_id": "06b86896f2344c8897abf49df3a774266208a1aa",
      "new_mode": 33188,
      "new_path": "internal/ceres/compressed_row_sparse_matrix.h"
    },
    {
      "type": "modify",
      "old_id": "4d20083a3259f95c887cb3bf0c6068034d492b2f",
      "old_mode": 33188,
      "old_path": "internal/ceres/compressed_row_sparse_matrix_test.cc",
      "new_id": "ea737b8d0e8b5062bb73179e55dbde803c376fa6",
      "new_mode": 33188,
      "new_path": "internal/ceres/compressed_row_sparse_matrix_test.cc"
    },
    {
      "type": "modify",
      "old_id": "b2dba440e106a3066a5be35c1b382271a1a71b91",
      "old_mode": 33188,
      "old_path": "internal/ceres/sparse_normal_cholesky_solver.cc",
      "new_id": "880adf7ebca60573c15740a9272affcf1beba11f",
      "new_mode": 33188,
      "new_path": "internal/ceres/sparse_normal_cholesky_solver.cc"
    },
    {
      "type": "modify",
      "old_id": "61111b41b496dea6f9a1a0357555e060016017f2",
      "old_mode": 33188,
      "old_path": "internal/ceres/sparse_normal_cholesky_solver.h",
      "new_id": "adca08a507f8b56b628441e3c16019ae99643057",
      "new_mode": 33188,
      "new_path": "internal/ceres/sparse_normal_cholesky_solver.h"
    },
    {
      "type": "modify",
      "old_id": "949fdd1f5df3bdce9248f7a4f581198918760a21",
      "old_mode": 33188,
      "old_path": "internal/ceres/unsymmetric_linear_solver_test.cc",
      "new_id": "624db68bbdeb949fd10447ae8aac8c67a331aa16",
      "new_mode": 33188,
      "new_path": "internal/ceres/unsymmetric_linear_solver_test.cc"
    }
  ]
}