[Bf-blender-cvs] [b16e924] master: Libmv: Update Ceres to the latest upstream version
Sergey Sharybin
noreply at git.blender.org
Mon Sep 29 20:49:13 CEST 2014
Commit: b16e924251f10d878c5c056aed0c4133d3e00c82
Author: Sergey Sharybin
Date: Tue Sep 30 00:39:45 2014 +0600
Branches: master
https://developer.blender.org/rBb16e924251f10d878c5c056aed0c4133d3e00c82
Libmv: Update Ceres to the latest upstream version
Mainly to let ITERATIVE_SCHUR use an explicit Schur Complement matrix.
===================================================================
M extern/libmv/third_party/ceres/ChangeLog
M extern/libmv/third_party/ceres/include/ceres/solver.h
M extern/libmv/third_party/ceres/internal/ceres/block_jacobi_preconditioner.cc
M extern/libmv/third_party/ceres/internal/ceres/block_jacobi_preconditioner.h
M extern/libmv/third_party/ceres/internal/ceres/block_random_access_diagonal_matrix.cc
M extern/libmv/third_party/ceres/internal/ceres/block_random_access_diagonal_matrix.h
M extern/libmv/third_party/ceres/internal/ceres/block_random_access_sparse_matrix.cc
M extern/libmv/third_party/ceres/internal/ceres/block_random_access_sparse_matrix.h
M extern/libmv/third_party/ceres/internal/ceres/callbacks.cc
M extern/libmv/third_party/ceres/internal/ceres/linear_solver.cc
M extern/libmv/third_party/ceres/internal/ceres/linear_solver.h
M extern/libmv/third_party/ceres/internal/ceres/schur_complement_solver.cc
M extern/libmv/third_party/ceres/internal/ceres/schur_complement_solver.h
M extern/libmv/third_party/ceres/internal/ceres/schur_jacobi_preconditioner.cc
M extern/libmv/third_party/ceres/internal/ceres/schur_jacobi_preconditioner.h
M extern/libmv/third_party/ceres/internal/ceres/solver.cc
M extern/libmv/third_party/ceres/internal/ceres/trust_region_preprocessor.cc
===================================================================
diff --git a/extern/libmv/third_party/ceres/ChangeLog b/extern/libmv/third_party/ceres/ChangeLog
index cd168a4..ee67da5 100644
--- a/extern/libmv/third_party/ceres/ChangeLog
+++ b/extern/libmv/third_party/ceres/ChangeLog
@@ -1,3 +1,106 @@
+commit b44cfdef25f6bf0917a23b3fd65cce38aa6a3362
+Author: Sameer Agarwal <sameeragarwal at google.com>
+Date: Mon Sep 29 07:53:54 2014 -0700
+
+ Let ITERATIVE_SCHUR use an explicit Schur Complement matrix.
+
+ Up till now ITERATIVE_SCHUR evaluates matrix-vector products
+ between the Schur complement and a vector implicitly by exploiting
+ the algebraic expression for the Schur complement.
+
+ This cost of this evaluation scales with the number of non-zeros
+ in the Jacobian.
+
+ For small to medium sized problems there is a sweet spot where
+ computing the Schur complement is cheap enough that it is much
+ more efficient to explicitly compute it and use it for evaluating
+ the matrix-vector products.
+
+ This changes implements support for an explicit Schur complement
+ in ITERATIVE_SCHUR in combination with the SCHUR_JACOBI preconditioner.
+
+ API wise a new bool Solver::Options::use_explicit_schur_complement
+ has been added.
+
+ The implementation extends the SparseSchurComplementSolver to use
+ Conjugate Gradients.
+
+ Example speedup:
+
+ use_explicit_schur_complement = false
+
+ Time (in seconds):
+ Preprocessor 0.585
+
+ Residual evaluation 0.319
+ Jacobian evaluation 1.590
+ Linear solver 25.685
+ Minimizer 27.990
+
+ Postprocessor 0.010
+ Total 28.585
+
+ use_explicit_schur_complement = true
+
+ Time (in seconds):
+ Preprocessor 0.638
+
+ Residual evaluation 0.318
+ Jacobian evaluation 1.507
+ Linear solver 5.930
+ Minimizer 8.144
+
+ Postprocessor 0.010
+ Total 8.791
+
+ Which indicates an end-to-end speedup of more than 3x, with the linear
+ solver being sped up by > 4x.
+
+ The idea to explore this optimization was inspired by the recent paper:
+
+ Mining structure fragments for smart bundle adjustment
+ L. Carlone, P. Alcantarilla, H. Chiu, K. Zsolt, F. Dellaert
+ British Machine Vision Conference, 2014
+
+ which uses a more complicated algorithm to compute parts of the
+ Schur complement to speed up the matrix-vector product.
+
+ Change-Id: I95324af0ab351faa1600f5204039a1d2a64ae61d
+
+commit 4ad91490827f2ebebcc70d17e63ef653bf06fd0d
+Author: Sameer Agarwal <sameeragarwal at google.com>
+Date: Wed Sep 24 23:54:18 2014 -0700
+
+ Simplify the Block Jacobi and Schur Jacobi preconditioners.
+
+ 1. Extend the implementation of BlockRandomAccessDiagonalMatrix
+ by adding Invert and RightMultiply methods.
+
+ 2. Simplify the implementation of the Schur Jacobi preconditioner
+ using these new methods.
+
+ 3. Replace the custom storage used inside Block Jacobi preconditioner
+ with BlockRandomAccessDiagonalMatrix and simplify its implementation
+ too.
+
+ Change-Id: I9d4888b35f0f228c08244abbdda5298b3ce9c466
+
+commit 8f7be1036b853addc33224d97b92412b5a1281b6
+Author: Sameer Agarwal <sameeragarwal at google.com>
+Date: Mon Sep 29 08:13:35 2014 -0700
+
+ Fix a formatting error TrustRegionMinimizer logging.
+
+ Change-Id: Iad1873c51eece46c3fdee1356d154367cfd7925e
+
+commit c99872d48e322662ea19efb9010a62b7432687ae
+Author: Sameer Agarwal <sameeragarwal at google.com>
+Date: Wed Sep 24 21:30:02 2014 -0700
+
+ Add BlockRandomAccessSparseMatrix::SymmetricRightMultiply.
+
+ Change-Id: Ib06a22a209b4c985ba218162dfb6bf46bd93169e
+
commit d3ecd18625ba260e0d00912a305a448b566acc59
Author: Sameer Agarwal <sameeragarwal at google.com>
Date: Tue Sep 23 10:12:42 2014 -0700
@@ -560,93 +663,3 @@ Date: Mon Aug 4 22:45:53 2014 -0700
Small changes from Jim Roseborough.
Change-Id: Ic8b19ea5c5f4f8fd782eb4420b30514153087d18
-
-commit a521fc3afc11425b46992388a83ef07017d02ac9
-Author: Sameer Agarwal <sameeragarwal at google.com>
-Date: Fri Aug 1 08:27:35 2014 -0700
-
- Simplify, cleanup and instrument SchurComplementSolver.
-
- The instrumentation revealed that EIGEN_SPARSE can be upto
- an order of magnitude slower than CX_SPARSE on some bundle
- adjustment problems.
-
- The problem comes down to the quality of AMD ordering that
- CXSparse/Eigen implements. It does particularly badly
- on the Schur complement. In the CXSparse implementation
- we got around this by considering the block sparsity structure
- and computing the AMD ordering on it and lifting it to the
- full matrix.
-
- This is currently not possible with the release version of
- Eigen, as the support for using preordered/natural orderings
- is in the master branch but has not been released yet.
-
- Change-Id: I25588d3e723e50606f327db5759f174f58439e29
-
-commit b43e73a03485f0fd0fe514e356ad8925731d3a81
-Author: Sameer Agarwal <sameeragarwal at google.com>
-Date: Fri Aug 1 12:09:09 2014 -0700
-
- Simplify the Eigen code in SparseNormalCholeskySolver.
-
- Simplifying some of the template handling, and remove the use
- of SelfAdjointView as it is not needed. The solver itself takes
- an argument for where the data is actually stored.
-
- The performance of SparseNormalCholesky with EIGEN_SPARSE
- seems to be on par with CX_SPARSE.
-
- Change-Id: I69e22a144b447c052b6cbe59ef1aa33eae2dd9e3
-
-commit 031598295c6b2f061c171b9b2338919f41b7eb0b
-Author: Sameer Agarwal <sameeragarwal at google.com>
-Date: Thu Jul 17 14:35:18 2014 -0700
-
- Enable Eigen as sparse linear algebra library.
-
- SPARSE_NORMAL_CHOLESKY and SPARSE_SCHUR can now be used
- with EIGEN_SPARSE as the backend.
-
- The performance is not as good as CXSparse. This needs to be
- investigated. Is it because the quality of AMD ordering that
- we are computing is not as good as the one for CXSparse? This
- could be because we are working with the scalar matrix instead
- of the block matrix.
-
- Also, the upper/lower triangular story is not completely clear.
- Both of these issues will be benchmarked and tackled in the
- near future.
-
- Also included in this change is a bunch of cleanup to the
- SparseNormalCholeskySolver and SparseSchurComplementSolver
- classes around the use of the of defines used to conditionally
- compile out parts of the code.
-
- The system_test has been updated to test EIGEN_SPARSE also.
-
- Change-Id: I46a57e9c4c97782696879e0b15cfc7a93fe5496a
-
-commit 1b17145adf6aa0072db2989ad799e90313970ab3
-Author: Sameer Agarwal <sameeragarwal at google.com>
-Date: Wed Jul 30 10:14:15 2014 -0700
-
- Make canned loss functions more robust.
-
- The loss functions that ship with ceres can sometimes
- generate a zero first derivative if the residual is too
- large.
-
- In such cases Corrector fails with an ugly undebuggable
- crash. This CL is the first in a series of fixes to
- take care of this.
-
- We clamp the values of rho' from below by
- numeric_limits<double>::min().
-
- Also included here is some minor cleanup where the constants
- are treated as doubles rather than integers.
-
- Thanks to Pierre Moulon for reporting this problem.
-
- Change-Id: I3aaf375303ecc2659bbf6fb56a812e7dc3a41106
diff --git a/extern/libmv/third_party/ceres/include/ceres/solver.h b/extern/libmv/third_party/ceres/include/ceres/solver.h
index 0af34ca..a5efa2a 100644
--- a/extern/libmv/third_party/ceres/include/ceres/solver.h
+++ b/extern/libmv/third_party/ceres/include/ceres/solver.h
@@ -118,6 +118,7 @@ class CERES_EXPORT Solver {
#endif
num_linear_solver_threads = 1;
+ use_explicit_schur_complement = false;
use_postordering = false;
dynamic_sparsity = false;
min_linear_solver_iterations = 0;
@@ -496,6 +497,29 @@ class CERES_EXPORT Solver {
// smaller than the group containing cameras.
shared_ptr<ParameterBlockOrdering> linear_solver_ordering;
+ // Use an explicitly computed Schur complement matrix with
+ // ITERATIVE_SCHUR.
+ //
+ // By default this option is disabled and ITERATIVE_SCHUR
+ // evaluates evaluates matrix-vector products between the Schur
+ // complement and a vector implicitly by exploiting the algebraic
+ // expression for the Schur complement.
+ //
+ // The cost of this evaluation scales with the number of non-zeros
+ // in the Jacobian.
+ //
+ // For small to medium sized problems there is a sweet spot where
+ // computing the Schur complement is cheap enough that it is much
+ // more efficient to explicitly compute it and use it for evaluating
+ // the matrix-vector products.
+ //
+ // Enabling this option tells ITERATIVE_SCHUR to use an explicitly
+ // computed Schur complement.
+ //
+ // NOTE: This option can only be used with the SCHUR_JACOBI
+ // preconditioner.
+ bool use_explicit_schur_complement;
+
// Sparse Cholesky factorization algorithms use a fill-reducing
// ordering to permute the columns of the Jacobian matrix. There
// are two ways of doing this.
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 19b749b..ea49f07 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
@@ -30,9 +30,9 @@
#include "ceres/block_jacobi_preconditioner.h"
-#include "Eigen/Cholesky"
#include "ceres/block_sparse_matrix.h"
#include "ceres/block_structure.h"
+#include "ceres/block_random_acce
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list