Libmv: update ceres to latest upstream version

This brings faster BlockRandomAccessSparseMatrix::SymmetricRightMultiply.

6 files changed, 37 insertions, 31 deletions

diff --git a/extern/libmv/third_party/ceres/ChangeLog b/extern/libmv/third_party/ceres/ChangeLog
index ee67da5afb9..6f921542019 100644
--- a/extern/libmv/third_party/ceres/ChangeLog
+++ b/extern/libmv/third_party/ceres/ChangeLog
@@ -1,3 +1,25 @@
+commit 9e11cd16d09403b9270e621e839d5948b6a74b8d
+Author: Sameer Agarwal <sameeragarwal@google.com>
+Date:   Mon Sep 29 14:27:58 2014 -0700
+
+    Faster  BlockRandomAccessSparseMatrix::SymmetricRightMultiply.
+    
+    Trade a small amount of memory to improve the cache coherency of
+    the SymmetricRightMultiply operation.
+    
+    The resulting code leads to a 10-20% speedup in the linear solver
+    end to end.
+    
+    Change-Id: I8ab2fe152099e849b211b5b19e4ef9f03d8e7f1c
+
+commit 46b8461fd010c1e7ffce6bb2bdf8a84b659d5e09
+Author: Sameer Agarwal <sameeragarwal@google.com>
+Date:   Mon Sep 29 15:10:58 2014 -0700
+
+    Various minor fixes from William Rucklidge.
+    
+    Change-Id: Ibe731d5db374ad8ee148d62a9fdd8d726b607a3f
+
 commit b44cfdef25f6bf0917a23b3fd65cce38aa6a3362
 Author: Sameer Agarwal <sameeragarwal@google.com>
 Date:   Mon Sep 29 07:53:54 2014 -0700
@@ -647,19 +669,3 @@ Date:   Thu Aug 7 12:19:10 2014 -0700
     construction is the right thing to do.
     
     Change-Id: I3bfdc89bb0027c8d67cde937e8f2fa385d89c30c
-
-commit cfb36463f9c1f806121779d651c7105ad899bb20
-Author: Sameer Agarwal <sameeragarwal@google.com>
-Date:   Tue Aug 5 14:42:33 2014 -0700
-
-    Small fixes from William Rucklidge.
-    
-    Change-Id: I0be52f0f1e53cedccffe4807dc664a2f3fb4a8e4
-
-commit 9a41132a0523af407b53644c07900f86aa6fceac
-Author: Sameer Agarwal <sameeragarwal@google.com>
-Date:   Mon Aug 4 22:45:53 2014 -0700
-
-    Small changes from Jim Roseborough.
-    
-    Change-Id: Ic8b19ea5c5f4f8fd782eb4420b30514153087d18
diff --git a/extern/libmv/third_party/ceres/internal/ceres/block_jacobi_preconditioner.cc b/extern/libmv/third_party/ceres/internal/ceres/block_jacobi_preconditioner.cc
index ea49f077e37..7f79a4f993d 100644
--- a/extern/libmv/third_party/ceres/internal/ceres/block_jacobi_preconditioner.cc
+++ b/extern/libmv/third_party/ceres/internal/ceres/block_jacobi_preconditioner.cc
@@ -102,9 +102,5 @@ void BlockJacobiPreconditioner::RightMultiply(const double* x,
   m_->RightMultiply(x, y);
 }
 
-void BlockJacobiPreconditioner::LeftMultiply(const double* x, double* y) const {
-  m_->RightMultiply(x, y);
-}
-
 }  // namespace internal
 }  // namespace ceres
diff --git a/extern/libmv/third_party/ceres/internal/ceres/block_jacobi_preconditioner.h b/extern/libmv/third_party/ceres/internal/ceres/block_jacobi_preconditioner.h
index 85792970925..e23e0e2d24c 100644
--- a/extern/libmv/third_party/ceres/internal/ceres/block_jacobi_preconditioner.h
+++ b/extern/libmv/third_party/ceres/internal/ceres/block_jacobi_preconditioner.h
@@ -60,7 +60,6 @@ class BlockJacobiPreconditioner : public BlockSparseMatrixPreconditioner {
 
   // Preconditioner interface
   virtual void RightMultiply(const double* x, double* y) const;
-  virtual void LeftMultiply(const double* x, double* y) const;
   virtual int num_rows() const { return m_->num_rows(); }
   virtual int num_cols() const { return m_->num_rows(); }
 
diff --git a/extern/libmv/third_party/ceres/internal/ceres/block_random_access_sparse_matrix.cc b/extern/libmv/third_party/ceres/internal/ceres/block_random_access_sparse_matrix.cc
index 9da16a469d5..c43a9b78feb 100644
--- a/extern/libmv/third_party/ceres/internal/ceres/block_random_access_sparse_matrix.cc
+++ b/extern/libmv/third_party/ceres/internal/ceres/block_random_access_sparse_matrix.cc
@@ -88,6 +88,8 @@ BlockRandomAccessSparseMatrix::BlockRandomAccessSparseMatrix(
        ++it) {
     const int row_block_size = blocks_[it->first];
     const int col_block_size = blocks_[it->second];
+    cell_values_.push_back(make_pair(make_pair(it->first, it->second),
+                                     values + pos));
     layout_[IntPairToLong(it->first, it->second)] =
         new CellInfo(values + pos);
     pos += row_block_size * col_block_size;
@@ -156,20 +158,19 @@ void BlockRandomAccessSparseMatrix::SetZero() {
 
 void BlockRandomAccessSparseMatrix::SymmetricRightMultiply(const double* x,
                                                            double* y) const {
-  for (LayoutType::const_iterator it = layout_.begin();
-       it != layout_.end();
-       ++it) {
-    int row;
-    int col;
-    LongToIntPair(it->first, &row, &col);
-
+  vector< pair<pair<int, int>, double*> >::const_iterator it =
+      cell_values_.begin();
+  for (; it != cell_values_.end(); ++it) {
+    const int row = it->first.first;
     const int row_block_size = blocks_[row];
     const int row_block_pos = block_positions_[row];
+
+    const int col = it->first.second;
     const int col_block_size = blocks_[col];
     const int col_block_pos = block_positions_[col];
 
     MatrixVectorMultiply<Eigen::Dynamic, Eigen::Dynamic, 1>(
-        it->second->values, row_block_size, col_block_size,
+        it->second, row_block_size, col_block_size,
         x + col_block_pos,
         y + row_block_pos);
 
@@ -179,7 +180,7 @@ void BlockRandomAccessSparseMatrix::SymmetricRightMultiply(const double* x,
     // triangular multiply also.
     if (row != col) {
       MatrixTransposeVectorMultiply<Eigen::Dynamic, Eigen::Dynamic, 1>(
-          it->second->values, row_block_size, col_block_size,
+          it->second, row_block_size, col_block_size,
           x + row_block_pos,
           y + col_block_pos);
     }
diff --git a/extern/libmv/third_party/ceres/internal/ceres/block_random_access_sparse_matrix.h b/extern/libmv/third_party/ceres/internal/ceres/block_random_access_sparse_matrix.h
index a4f89d8130f..51b5d20cfe0 100644
--- a/extern/libmv/third_party/ceres/internal/ceres/block_random_access_sparse_matrix.h
+++ b/extern/libmv/third_party/ceres/internal/ceres/block_random_access_sparse_matrix.h
@@ -111,6 +111,10 @@ class BlockRandomAccessSparseMatrix : public BlockRandomAccessMatrix {
   typedef HashMap<long int, CellInfo* > LayoutType;
   LayoutType layout_;
 
+  // In order traversal of contents of the matrix. This allows us to
+  // implement a matrix-vector which is 20% faster than using the
+  // iterator in the Layout object instead.
+  vector<pair<pair<int, int>, double*> > cell_values_;
   // The underlying matrix object which actually stores the cells.
   scoped_ptr<TripletSparseMatrix> tsm_;
 
diff --git a/extern/libmv/third_party/ceres/internal/ceres/solver.cc b/extern/libmv/third_party/ceres/internal/ceres/solver.cc
index e1c5ee30ba5..3512e156f9e 100644
--- a/extern/libmv/third_party/ceres/internal/ceres/solver.cc
+++ b/extern/libmv/third_party/ceres/internal/ceres/solver.cc
@@ -123,7 +123,7 @@ bool TrustRegionOptionsAreValid(const Solver::Options& options, string* error) {
   if (options.linear_solver_type == ITERATIVE_SCHUR &&
       options.use_explicit_schur_complement &&
       options.preconditioner_type != SCHUR_JACOBI) {
-    *error =  "use_explicit_schur_complement only supports"
+    *error =  "use_explicit_schur_complement only supports "
         "SCHUR_JACOBI as the preconditioner.";
     return false;
   }