commit d3ecd18625ba260e0d00912a305a448b566acc59 Author: Sameer Agarwal Date: Tue Sep 23 10:12:42 2014 -0700 Add an explicit include for local_parameterization.h Thanks to cooordz for reporting this. Change-Id: I7d345404e362a94ff1eb433ad6b9dcc4960ba76d commit 5dd76869cf45122c79579423f09e0de08cf04092 Author: Alex Stewart Date: Fri Sep 19 16:08:25 2014 +0100 Fix unused-function warning with Eigen < 3.2.2. - CreateBlockJacobian() is only ever used when Eigen >= 3.2.2 is detected, but was previously defined whenever CERES_USE_EIGEN_SPARSE was defined with no check on the Eigen version. - This resulted in an unused-function compile warning that became an error due to -Werror, preventing compilation when using Eigen < 3.2.2. Change-Id: I24628ff329f14b087ece66bf2626bdc0de4ba224 commit 820cb7b14831aa03eca1e8186000cebfdf0a42f3 Author: Sameer Agarwal Date: Wed Sep 17 09:46:08 2014 -0700 Add solver_utils.cc to Android.mk Change-Id: I358522971711280f4362a1fa39b1568160e21e63 commit 092b94970a073f8b47179d96160226fc19095898 Author: Sameer Agarwal Date: Fri Sep 5 11:56:29 2014 -0700 Add GradientProblem and GradientProblemSolver. The line search minimizer in Ceres does not require that the problems that is solving is a sum of squares. Over the past year there have been multiple requests to expose this algorithm on its own so that it can be used to solve unconstrained non-linear minimization problems on its own. With this change, a new optimization problem called GradientProblem is introduced which is basically a thin wrapper around a user defined functor that evaluates cost and gradients (FirstOrderFunction) and an optional LocalParameterization. Corresponding to it, a GradientProblemSolver and its associated options and summary structs are introduced too. An example that uses the new API to find the minimum of Rosenbrock's function is also added. Change-Id: I42bf687540da25de991e9bdb00e321239244e8b4 commit 6c45d6b891aac01489b478a021f99081c61792cb Author: Sameer Agarwal Date: Thu Sep 11 07:48:30 2014 -0700 Add more inspection methods to Problem. Problem::GetCostFunctionForResidualBlock Problem::GetLossFunctionForResidualBlock are added, so that users do not have to maintain this mapping outside the Problem. Change-Id: I38356dfa094b2c7eec90651dafeaf3a33c5f5f56 commit 6ad9b8e2ae66c9009441d0f9304486ec8dfa9a6a Author: Sameer Agarwal Date: Tue Sep 9 14:29:28 2014 -0700 Ignore row/column blocks structure when using dynamic sparsity The row/column blocks can be huge when using dynamic sparsity. This can result in very large memory usage when augmenting the jacobian with the LM diagonal. Thanks to Mingsong Dou for reporting this. Change-Id: I6aa140ceefa98389ae17958f89ca76e0c76f95b8 commit 7e43460d42e20be1ba13121655dbbfd0d1c751ae Author: Martin Baeuml Date: Mon Sep 8 16:49:06 2014 +0200 Fix a few typos in the documentation. Change-Id: I541db56b2b81ae758e233ce850d78c3cbb4b6fa3 commit 1aef66eeae7042902655a11b0d6a1a32900abb7b Author: Sameer Agarwal Date: Sun Sep 7 21:18:44 2014 -0700 Remove errant space. Change-Id: Iedc06960417a9b938d57f623b4beb87a98e3d081 commit 89080ab153a33008782759187fa8e9af7d2f83f1 Author: Sameer Agarwal Date: Sat Sep 6 21:13:48 2014 -0700 Add LocalParameterization::MultiplyByJacobian. This is needed to efficiently support LocalParameterization objects in GradientProblemSolver. Change-Id: Ic7b715b8be694b099dc95d6707a67474297533e6 commit d76da16f49d419ae3664ca1bdc2286c1ea78ebed Author: Sameer Agarwal Date: Sun Sep 7 18:42:49 2014 -0700 Move some routines to solver_utils.h/cc This moves a couple of routines from solver.cc into solver_utils.h/cc so that they can also be used by the upcoming GradientProblemSolver. Change-Id: I627b32ad3dc639422aacde78a8e391459d947e99 commit cbf03ac292a0c0e9e6b7fcc1b08b67e95965922f Author: Sameer Agarwal Date: Sat Sep 6 21:07:08 2014 -0700 Make LineSearchMinimizer consistent with TrustRegionMinimizer. Change the logic for how IterationSummary objects are added to Summary::iterations to match the one in TrustRegionMinimizer. Change-Id: I57851ad8294e58f83b9115cca9c24695d86ee92a commit f04c32319751e1efd610acd3699bca0a6dd6c6d1 Author: Sameer Agarwal Date: Sat Sep 6 21:05:41 2014 -0700 Fix some obsolete documentation in CostFunction::Evaluate Change-Id: I1d7ee5c596fbf6a4d886dce5b989c8eb18af2dce commit 9263547c02a1807532b159c217e7acd124d3db10 Author: Johannes Schönberger Date: Sat Sep 6 17:26:15 2014 -0400 Fix CG solver options for ITERATIVE_SCHUR, which did not copy min_num_iterations Change-Id: If31bc53b49ec20426fd438b79b8fa1f69d11e861 commit b41f048256d1a8184cbe874b5a96dffa7fa4630d Author: Martin Baeuml Date: Fri Sep 5 15:03:32 2014 +0200 Remove obsolete include of numeric_diff_functor.h. numeric_diff_functor.h was removed and does not exist anymore. Change-Id: I07bf04bf81142551e867b95b83a0653e11cad54c commit b7fb6056a717cc3c372cfb7115c527ee8bc05ddb Author: Sameer Agarwal Date: Wed Sep 3 11:19:02 2014 -0700 Remove NumericDiffFunctor. Its API was broken, and its implementation was an unnecessary layer of abstraction over CostFunctionToFunctor. Change-Id: I18fc261fc6a3620b51a9eeb4dde0af03d753af69 commit 175fa8ff09049110a8509409f60cee5fd52cdbe6 Author: Sameer Agarwal Date: Tue Sep 2 06:49:08 2014 -0700 CostFunctionToFunctor allows dynamic number of residuals. The code itself was perfectly capable of handling residuals, but there was an overly strict runtime check that had to be removed. Thanks to Domink Reitzle for reporting this. Change-Id: I6a6d000a7c5203dd5945a61b4caeda1b8aeb09c9 commit 70ace0d5a5601901288974fcf27919754260cf0e Author: Johannes Schönberger Date: Sat Aug 30 15:52:34 2014 -0400 Fix max. linear solver iterations in ConjugateGradientsSolver Change-Id: Ice0cef46441dbc1c121eeb42113667a46c96936f commit c5d8d0680250f5eb554577d30d28fc805b03fab9 Author: Sameer Agarwal Date: Fri Aug 29 20:31:19 2014 -0700 Fix a unused function error with Eigen version 3.2.1 or less. Thanks to Johannes Schoenberger for reporting this. Change-Id: Ie17d28f2a68734a978a8c95007724bc4055de43a commit 0e1cc2a55488e4cf381833baaa3531c02ce9d69e Author: Sameer Agarwal Date: Fri Aug 29 09:16:56 2014 -0700 Fix the build on Eigen version 3.2.1 and older. Change-Id: I18f5cb5d42113737d7b8f78a67acee28bd5b3e08 commit 5f96c62b56222f27e606f2246a8a16b6942af8d1 Author: Sameer Agarwal Date: Thu Aug 28 23:06:17 2014 -0700 Add Block AMD ordering for SPARSE_SCHUR + EIGEN_SPARSE. Ordering routines for the Schur complement when using EIGEN_SPARSE. Also integration into SchurComplementSolver. Part of this CL is also a refactoring of the block jacobian matrix construction. Change-Id: I11d665cc7d4867c64190e6fed1118f4d2e13d59b commit 7344626c04d19ca1dc4871c377c4422c744b1bca Author: Sameer Agarwal Date: Thu Aug 28 22:03:09 2014 -0700 Let EIGEN_SPARSE + SPARSE_NORMAL_CHOLESKY use block AMD. Modify SparseNormalCholeskySolver to use a pre-ordered Jacobian matrix. Change-Id: Ib4d725d7a2d7bb94ea76dbb3a9b172784dbc8ea0 commit 9f7032369ea4e432f0fb507cb6d2209741ee6946 Author: Sameer Agarwal Date: Thu Aug 28 21:46:43 2014 -0700 Block AMD for SparseNormalCholesky + EIGEN_SPARSE. This is just the reordering routine. The integration with SparseNormalCholesky shall happen in a subsequent CL. Change-Id: I39ddc32aa66b11c368faf75404850fa0ae0d2b3a commit b9331cd4077100d645be22a912d5743eeda72878 Author: Sameer Agarwal Date: Thu Aug 28 14:42:27 2014 -0700 Cleanup reorder_program.cc Program::SetParameterOffsetsAndIndex() was being called willy nilly. Now the invariant is that any function that actually reorders the program, updates the offsets and indices. Also the logic around handling EIGEN_SPARSE has been simplified in anticipation of the block AMD code that is forthcoming. Last but not the least, num_eliminate_blocks, which is a rather cryptic name to begin with has been replaced by the more meaningful size_of_first_elimination_group. Change-Id: I77e684f699a93b53e76aa406d64f40f8704df813 commit 79491a3f4a3939a3cce4644da7a998b7782b963a Author: Sameer Agarwal Date: Thu Aug 28 13:57:50 2014 -0700 Solver::FullReport now reports build config. The header of Summary::FullReport now looks like Solver Summary (v 1.10.0-suitesparse-cxsparse-lapack-no_openmp) Original Reduced Parameter blocks 22122 22122 Parameters 66462 66462 Residual blocks 83718 83718 Residual 167436 167436 Change-Id: Id1b81bbf90ba412d19e2dd3687eeb9d372b72c1b commit 48068c753e91d77f6c96ef2d529a27ef8ee3947c Author: Sameer Agarwal Date: Thu Aug 28 13:03:40 2014 -0700 Lint cleanup from William Rucklidge. Change-Id: Ie0e0aa58440be7a4f67dcd633dbb6f1bb0c051a8 commit 6a51b135e6298e8ba44a58cc2b54a170ab61a82f Author: Sameer Agarwal Date: Thu Aug 28 10:48:29 2014 -0700 Fix solver_test.cc When Eigen is not installed, Solver::IsValid was not detecting it correctly. Change-Id: Id285a84d829a9e20bc5de663adfca66ac31e08f3 commit 62a8d64453ee41dae56710a4eead3fadf2fe1a4e Author: Sameer Agarwal Date: Wed Aug 27 22:54:00 2014 -0700 Expand check for lack of a sparse linear algebra library. The LinearSolver factory was creating a NULL linear solver if only Eigen's sparse linear algebra backend was available. Thanks to Michael Samples and Domink Reitzle for reporting this. Change-Id: I35e3a6c0fd0da2a31934adb5dfe4cad29577cc73 commit 12eb389b4ec4113a2260c1a192a1d3f8d1b6a2d3 Author: Sameer Agarwal Date: Wed Aug 27 22:18:33 2014 -0700 Fix Eigen Row/ColMajor bug in NumericDiffCostFunction. If the parameter block size is 1, asking Eigen to create a row-major matrix triggers a compile time error. Previously we were handling the case where the number of rows in the jacobian block was known statically, but the problem is present when the nummber of rows is dynamic. This CL fixes this problem. Thanks to Dominik Reitzle for reporting this. Change-Id: I99c3eec3558e66ebf4efa51c4dee8ce292ffe0c1 commit 6c25185bb1643d8d0f3d8e1a7b82a058156aa869 Author: Alex Stewart Date: Thu Aug 28 16:07:51 2014 +0100 Fix crash in Covariance if # threads > 1 requested without OpenMP. - Previously if options.num_threads > 1 was given to Covariance compiled without OpenMP, a CHECK() would be triggered in program_evalutor. Change-Id: Iaade4f5ed5326b0c59a7014c750c41ee026e1124 commit 6f89d850fb4ace0104abccf467c4fe37ad378b79 Author: Sameer Agarwal Date: Wed Aug 27 11:51:50 2014 -0700 Further build breakage fixes. 1. Allow the minimum number of linear solver iterations to be zero. 2. Fix conjugate gradients solver's iteration loop to be sane again. Change-Id: I8594815fec940c2b30e28eb58ec5d8baacf13dae commit dd596d0f0d6d08951efc2c11a639b546db2080c6 Author: Sameer Agarwal Date: Wed Aug 27 11:26:50 2014 -0700 Fix the broken build. Change-Id: I083cf1cca1bf4cca956193022d450364e73f833a commit d906afae22b05b9b9a9a2657924f4c0bf1a9b5ea Author: Sameer Agarwal Date: Mon Aug 25 22:32:38 2014 -0700 A number of bug fixes. 1. Fix a build breakage in graph_test. 2. Respect Solver::Options::min_num_linear_solver_iterations in conjugate_gradients_solver.cc Thanks to Johannes Schönberger for reporting these. Change-Id: Ib32e3929bf5d92dd576ae5b53d4d88797095136e commit dab955928c6d0942d6acc5b5f1c4c11260d0767d Author: Sameer Agarwal Date: Sun Aug 17 13:14:50 2014 -0700 Add an unweighted graph. Rename Graph -> WeightedGraph. Add a new Graph class, which is cheaper to construct and work with if the weights are not needed. This cuts down the cost of building the Hessian graph significantly. Change-Id: Id0cfc81dd2c0bb5ff8f63a1b55aa133c53c0c869 commit a0c282adbd268c2ad82551fab31fe1cf8d0c4282 Author: Sameer Agarwal Date: Sun Aug 24 22:19:03 2014 -0700 Add EIGEN_STRONG_INLINE annotation to jet.h This improves performance when using MSVC on Windows. On GCC there will be no effect. Change-Id: I555a81ff6823c2855d64773073f75af50c48d716 commit 20de0a7793c574e964350a623446136889f74632 Author: Björn Piltz Date: Mon Aug 25 17:05:54 2014 +0200 Fixed Malformed regex I got the following error with MSVC: Syntax error at index 9 in simple regular expression "NumGroups()": '(' is unsupported. Change-Id: Id1952831d81d3eb5d73bbed8c311914c4c8ab51f commit ccf8aea988269841d84d746e52164d5056c67a10 Author: Björn Piltz Date: Mon Aug 25 16:16:01 2014 +0200 Fixed MSVC error C2124: divide or mod by zero Alternatively, if quiet_NaN is not available on all platforms a workaround would be: volatile double zero = 0.0; double x = 1.0/zero; The 'volatile' is needed to shut up "warning C4723: potential divide by 0". Change-Id: If2bbdab8540595aa2e0079e1eb6b6fed6d4a6ef7 commit 8de27be218d42b282d7f15867733ad07058b0887 Author: Sameer Agarwal Date: Tue Aug 19 08:22:40 2014 -0700 Fix a bug in TrustRegionPreprocessor TrustRegionPreprocessor was not setting Minimizer::Options::is_constrained. This meant that the line search for bounds constraints was not being invoked for bounds constrained problems. And some minor lint cleanup. Change-Id: I18852cfaf1b33fd90b7d8c196f2063c128126658 commit 1745dd615b3897a3ef9896acfdba67eee1739bf4 Author: Sameer Agarwal Date: Thu Jun 5 21:30:13 2014 -0700 Refactor SolverImpl. Replace SolverImpl with a. A minimizer specific preprocessor class. b. A generic Solve function inside solver.cc c. Presummarize and Postsummarize functions to handle updates to the summary object. The existing SolverImpl class was a mixture of the above three things and was increasingly complicated code to follow. This change, breaks it into its three separate constituents, with the aims of better separation of concerns and thus better testability and reliability. The call to Solver::Solve() now consists of 1. Presummarize - summarize the given state of the problem and solver options. 2. Preprocess - Setup everything that is needed to call the minimizer. This includes, removing redundant parameter and residual blocks, setting up the reordering for the linear solver, creating the linear solver, evaluator, inner iteration minimizer etc. 3. Minimize. 4. Post summarize - summarize the result of the preprocessing and the solve. Change-Id: I80f35cfc9f2cbf78f1df4aceace27075779d8a3a commit bd90384226a7f8629467f72fc410a9e8086a2dff Author: Sameer Agarwal Date: Mon Aug 18 11:27:06 2014 -0700 Lint comments from William Rucklidge. Also some minor refactoring of the trust_region_preprocessor_test.cc Change-Id: Ica28002254c95722faf93a7ef35bf3deab557f0b commit 3150321db4a0cb1bb4894961a030d95dacae3591 Author: Sameer Agarwal Date: Tue Aug 12 22:46:51 2014 -0700 Preprocessor for the LineSearchMinimizer. Change-Id: Ieb5dfe1c0b96ef323c1130edd0c3a8a8b2c644cc commit f7da411ef0d0067e269629887d64cdb769368800 Author: Sameer Agarwal Date: Thu Aug 7 14:30:33 2014 -0700 Preprocessor for the TrustRegionMinimizer. 1. Base class for preprocessors. 2. A preprocessor for problems that will be solved using the trust region minimizer. 3. Added sanity tests to the program reordering options for Schur type linear solvers. 4. Tests for the TrustRegionPreprocessor. Change-Id: I88cd926f0053bbbf2bd6b11e03ec55b8bf473cf1 commit 54893ba523106e38ab06eb72fb5d8748685c7797 Author: Alex Stewart Date: Mon Aug 11 19:04:18 2014 +0100 Add missing #include of for loss functions. Change-Id: Id632451429e03031a1533a9be795270debc70706 commit 4a2a888905fd1ce7203e45df15762d52740bb240 Author: Sameer Agarwal Date: Thu Aug 7 11:48:03 2014 -0700 Change ownership of pointers in Minimizer::Options. This is a intermediate change to clean things up in preparation for a broader refactoring of the SolverImpl. Essentially we are replacing raw pointers in Minimizer::Options with shared_ptr objects. For now this only makes things a bit more complicated looking inside solver_impl.cc, but going forward this will lead to considerable simplifications in tracking ownership of various pointers. Change-Id: I21db8fc6763c29b0d15e834d7c968a0f514042a0 commit 0d4e3bd664d442b700fee2895c7a8ac37717dc08 Author: Sameer Agarwal Date: Thu Aug 7 12:19:10 2014 -0700 GradientCheckingProblem's parameter blocks are initialized correctly. Ensure that when a new problem object is constructed for validing gradients, the parameter blocks have their data pointers point to the user's parameter blocks. We used to do this inside solver_impl.cc, but doing this at construction is the right thing to do. Change-Id: I3bfdc89bb0027c8d67cde937e8f2fa385d89c30c commit cfb36463f9c1f806121779d651c7105ad899bb20 Author: Sameer Agarwal Date: Tue Aug 5 14:42:33 2014 -0700 Small fixes from William Rucklidge. Change-Id: I0be52f0f1e53cedccffe4807dc664a2f3fb4a8e4 commit 9a41132a0523af407b53644c07900f86aa6fceac Author: Sameer Agarwal Date: Mon Aug 4 22:45:53 2014 -0700 Small changes from Jim Roseborough. Change-Id: Ic8b19ea5c5f4f8fd782eb4420b30514153087d18 commit a521fc3afc11425b46992388a83ef07017d02ac9 Author: Sameer Agarwal 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 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 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 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::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