commit 15bf0d5018dfe432ef67e726b248efcf3b58bc4f Author: Sergey Sharybin Date: Mon Jan 13 20:38:28 2014 +0600 Code cleanup: fix no previous declaration warnings Move internally used functions to an anonymous namespace, Change-Id: I84c98facf901e64771d131b088e20e2c033cab70 commit 80a53eebfd28bfc032cedbf7852d5c56eb1d5af5 Author: Sameer Agarwal Date: Thu Jan 9 12:40:54 2014 -0800 Faster LBFGS. 1. Use column major storage for the various matrices used by LowRankInverseHessian. Since all the operations are on columns. 2. Use a circular buffer to keep track of history of the LBFGS updates so that an update does not require copying the entire history. This makes the updates O(1) rather than O(rank). The implementation has been checked against the denoising code where it gives numerically identical results. The overhead of the LBFGS code is now near negligible as compared to the gradient evaluation. On a sample problem before 1050ms after: 630ms Change-Id: I537ba506ac35fc4960b304c10d923a8dea2ae031 commit f55780063620e7a3dcfe7e018d6488bf6a5b29da Author: Sameer Agarwal Date: Wed Jan 8 10:43:31 2014 -0800 Reduce logging verbosity. When user specifies Solver::Options::logging_type = SILENT, ensure that the minimizer does not log anything. Change-Id: I94e34dae504881ab36d4a66e6adb7a19a227363e commit 85561eee951c91e578984c6d3eecf0073acabb64 Author: Sameer Agarwal Date: Tue Jan 7 22:22:14 2014 -0800 Use int32 for parameter block sizes. CostFunction now uses int32 instead of int16 to store the size of its parameter blocks. This is an API breaking change. Change-Id: I032ea583bc7ea4b3009be25d23a3be143749c73e commit a7fda3317b1a97702750bea96ac3ef3d1a2afb49 Author: Alex Stewart Date: Mon Jan 6 10:25:42 2014 +0000 Fix typos in error messages in line search config checks. Change-Id: I3ae2ae58328e996598e3e32c12869d2b10109ef7 commit f695322eb8c5ff118f0d27f68d46d557338e5db1 Author: Sameer Agarwal Date: Sat Jan 4 14:28:23 2014 -0800 Remove a compilation warning on windows. Only define NOMINMAX if it is not already defined. Thanks to Pierre Moulon for this fix. Change-Id: Ia5dc0f5ff2afe10e4c7e97a57f54297d82052b21 commit b811041d78d80518db153ef3030bcbdbaf80df8d Author: Sergey Sharybin Date: Thu Jan 2 15:19:17 2014 +0600 Code cleanup: fix no previous declaration warnings Moved some internally used functions into an anonymous namespace. Change-Id: Ie82df61b0608abac79ccc9f7b14e7f7e04ab733d commit f14f6bf9b7d3fbd2cab939cf4ad615b317e93c83 Author: Sameer Agarwal Date: Thu Dec 26 09:50:45 2013 -0800 Speed up SPARSE_NORMAL_CHOLESKY when using CX_SPARSE. When using sparse cholesky factorization to solve the linear least squares problem: Ax = b There are two sources of computational complexity. 1. Computing H = A'A 2. Computing the sparse Cholesky factorization of H. Doing 1. using CX_SPARSE is particularly expensive, as it uses a generic cs_multiply function which computes the structure of the matrix H everytime, reallocates memory and does not take advantage of the fact that the matrix being computed is a symmetric outer product. This change adds a custom symmetric outer product algorithm for CompressedRowSparseMatrix. It has a symbolic phase, where it computes the sparsity structure of the output matrix and a "program" which allows the actual multiplication routine to determine exactly which entry in the values array each term in the product contributes to. With these two bits of information, the outer product H = A'A can be computed extremely fast without any reasoning about the structure of H. Further gains in efficiency are made by exploiting the block structure of A. With this change, SPARSE_NORMAL_CHOLESKY with CX_SPARSE as the backend results in > 300% speedup for some problems. The symbolic analysis phase of the solver is a bit more expensive now but the increased cost is made up in 3-4 iterations. Change-Id: I5e4a72b4d03ba41b378a2634330bc22b299c0f12 commit d79f886eb87cb064e19eb12c1ad3d45bbed92198 Author: Sameer Agarwal Date: Mon Dec 30 07:39:10 2013 -0800 Refactor line search error checking code. Move the error checking code into its own function so that it can be used in upcoming changes. Change-Id: Icf348e5a8bbe8f8b663f04fb8cfc9a2149b12f22 commit 2b16b0080b6e673eaaf9ed478c9e971d9fcd65de Author: Sameer Agarwal Date: Fri Dec 20 15:22:26 2013 -0800 CompressedRowSparseMatrix::AppendRows and DeleteRows bugfix. CompressedRowSparseMatrix can store the row and column block structure but the AppendRows and DeleteRows methods did not pay attention to them. This meant that it was possible to get to a CompressedRowSparseMatrix whose block structure did not match the contents of the matrix. This change fixes this problem. Change-Id: I1b3c807fc03d8c049ee20511e2bc62806d211b81 commit 27bb4a8589c47a65b5ea2c01872a903043d0ef74 Author: Sameer Agarwal Date: Wed Dec 18 13:06:58 2013 -0800 Handle empty problems consistently. Until now Ceres was inconsistent in the way it handled a solve call on an "empty" Problem. If the problem did not contain any residual or parameter blocks, it failed. However, if after constructing the reduced program, the problem was found to not contain any modifiable parameter blocks, it was considered a valid problem which had a constant objective function value. When creating problems automatically, it is often the case that an empty problem is a corner case. This change makes handling this corner case consistent with the rest of Ceres logic. Change-Id: Ia9da09fbf5d5cd7eae6b39a92c1976b8645db9fe commit dcee120bac04911bf01d8365bddca87c74ce2af9 Author: Sameer Agarwal Date: Sat Dec 7 21:48:56 2013 -0800 Consolidate SolverTerminationType enum. 1. Rename SolverTerminationType to TerminationType. 2. Consolidate the enum as a. CONVERGENCE - subsumes FUNCTION_TOLERANCE, PARAMETER_TOLERANCE and GRADIENT_TOLERANCE b. NO_CONVERGENCE c. FAILURE - captures all kinds of failures including DID_NOT_RUN. d. USER_SUCCESS e. USER_FAILURE 3. Solver::Summary::error is renamed to be Solver::Summary::message, to both reduce confusion as well as capture its true meaning. Change-Id: I27a382e66e67f5a4750d0ee914d941f6b53c326d commit d1cf320bb4f032cb14b20114a29ce2d867307492 Author: Sergey Sharybin Date: Thu Nov 28 23:11:11 2013 +0600 Made collections port compatible with MSVC2008 The issue was caused by the fact that in this version of MSVC unordered_map class is defined in header file, but this file declares the class int std::tr1 namespace. This confused existing assumption that if there's an existing file then class is declared in std namespace. Added an extra check to CMake which detects whether it's std or std::tr1 which actually contains class of unordered_map. Change-Id: Ic5cf41913895a6ce8e791cc7602d7cf5492c34de commit 324eccb5f6ce2a1a0061ec9f3c40778a029a2d97 Author: Sameer Agarwal Date: Tue Dec 3 09:28:14 2013 -0800 Restore the state of the Problem after a call to Evaluate. Calling Problem::Evaluate mutates the state of the parameter blocks. In particular, depending on the set and order of parameter blocks passed to the evaluate call, it will change the internal indexing used by the Program object used by ProblemImpl. This needs to be undone before Evaluate returns, otherwise the Problem object is in an invalid state. To help with testing and debugging in the future, a new method Program::IsValid has been added which checks whether the problem has its parameter and residual blocks in the right state. Thanks to Stefan Leutenegger for reporting this. Change-Id: I209b486a31433f0cbb58b570047649eca6d42b56 commit 3b1ad31a1fe89fe0bd78e1fffdf22d47d43faaf5 Author: Sameer Agarwal Date: Mon Dec 2 15:43:20 2013 -0800 Fix build breakage on old versions of SuiteSparse. Change-Id: I2a061615fc374abef2ed323c298359002a6fc5f1 commit 5fd480692b0a0c87e2af2f5a8754042a14f5f089 Author: Sameer Agarwal Date: Mon Dec 2 12:16:53 2013 -0800 Add more documentation to the linear solver enums. Change-Id: Id57f76f73fa38043c0b6729972b1de8578ad7ede commit d73acd035359886dfa1c5762b01c6f6449edcab8 Author: Sameer Agarwal Date: Mon Dec 2 12:02:03 2013 -0800 Lint cleanup from William Rucklidge. Change-Id: I8abcfd369f41b895ce746a21a35f250fe05c39d1 commit 3faac6a28cec4c99c41421d3f585f3786be443b3 Author: Sameer Agarwal Date: Thu Nov 28 07:13:26 2013 -0800 More lint cleanups and breakage fixes. The previous CL was a premature submit due to lack of coffee. Change-Id: Id425d0ef332f569a954f0413e6b1ae6087f40f30 commit ed92366592a951041bd0367c24006101ef7b6286 Author: Sameer Agarwal Date: Thu Nov 28 06:50:43 2013 -0800 Lint cleanup from William Rucklidge. Change-Id: I745810f5496a1b93263b20ff140f8883da61995e commit 34b6359f39884683f2bbf06c93040afd42ae135d Author: Sergey Sharybin Date: Thu Nov 28 18:51:34 2013 +0600 Fix compilation error after recent enum rename in 33e01b9 Change-Id: I920aa4754df6b013e86f0e77c61338d7a80e7f45 commit 33e01b9c5e1416fe29c55ac0332cdca21c053c83 Author: Sameer Agarwal Date: Wed Nov 27 10:24:03 2013 -0800 Rename LinearSolverTerminationType enums. This increases clarity, drops redundant enums and makes things cleaner all around. Change-Id: I761f195ddf17ea6bd8e4e55bf5a72863660c4c3b commit 068437eb89d495d905465544ccd442efef457b04 Author: Sameer Agarwal Date: Wed Nov 27 07:05:57 2013 -0800 Pipe minimizer termination messages to Solver::Summary. All minimizer termination messages are now available as Solver::Summary::error. This is part of the ongoing refactoring or Change-Id: I4514c3c042645bbd1471bcde9bd3dbf81d9ee8b0 commit 89a592f410fb6f80c03dea84b6b9f1a10bea36c1 Author: Sameer Agarwal Date: Tue Nov 26 11:35:49 2013 -0800 LinearSolver::Summary::status -> LinearSolver::Summary::message. And a bunch of minor lint cleanups as they showed up. Change-Id: I430a6b05710923c72daf6a5df4dfcd16fbf44b3a commit b16e118b96c55451c0d8556f3c5b52ad36b69cac Author: Sameer Agarwal Date: Mon Nov 25 05:47:43 2013 -0800 Better error checking and reporting for linear solvers. A lot of error checking cruft has accumulated over the years in the various linear solvers. This change makes the error reporting more robust and consistent across the various solvers. Preconditioners are not covered by this change and will be the subject of a future change. Change-Id: Ibeb2572a1e67758953dde8d12e3abc6d1df9052d commit 5794d41be2d8d6a67dcdfe607e66050f0ac04c55 Author: Sameer Agarwal Date: Mon Nov 25 13:37:02 2013 -0800 Remove overzealous checks in Summary::FullReport. Thanks to sebi.koch@gmail.com for reporting this. Change-Id: I1ba9b375e5cf66639e292ba37b34a90446f13162 commit 40ef90304ac200bb948549e8e3748e487d27dc53 Author: Alex Stewart Date: Mon Nov 25 16:36:40 2013 +0000 Adding VLOG output to line search. - Previously line search was sparse in terms of debug orientated VLOG output which made debugging failure cases difficult. Change-Id: Idfabf74d2b3f7b8256f79dff8c6b7fcdc2fcf4d3 commit 1284a5141426597f3ca1e29ae8548c9b4c43c9c1 Author: Sameer Agarwal Date: Sun Nov 24 15:09:43 2013 -0800 Use explicit formula to solve quadratic polynomials. polynomial.cc implements a companion matrix base method for solving polynomials. This is both expensive and numerically sensitive. This change adds a quadratic equation solver. Instead of using the usual quadratic formula, it uses the formula suggested by BKP Horn for improved numerical stability. Change-Id: I476933ce010d81db992f1c580d2fb23a4457eb3e commit a9334d67d7973c0f56e65f12ae897dd53504ef0d Author: Sameer Agarwal Date: Wed Nov 20 10:12:23 2013 -0800 Fix constant parameter handling in inner iterations. There was a bug in the way RemoveFixedBlocksFromProgram was working. It only removed the constant parameter blocks from the linear_solver_ordering, it was not even aware of the inner_iteration_ordering. This change fixes this bug. The code for RemoveFixedBlocksFromProgram is also cleaned up and made more readable and the test have been updated. Thanks to Mikael Persson for reporting this. Change-Id: I454fa89f9b6f4f6320b02d5235e6f322cc15ff51 commit 331ff090dcae7096cea50144047b71cab2d3e819 Author: Alex Stewart Date: Mon Nov 25 13:44:53 2013 +0000 Downgrading log status of BFGS secant condition messages. - These messages were originally VLOG(2) and were mistakenly upgraded to WARNINGs when the tolerances were reduced. Change-Id: I89dee666a09bc82cfa89b793dc0907268662f95e commit 9697a08a2bf29531671526b49df73bfbc0d7d237 Author: Alex Stewart Date: Sat Nov 23 10:03:37 2013 +0000 Defining CERES_FOUND in addition to Ceres_FOUND in CeresConfig. - Previously we relied on FindPackage() to define Ceres_FOUND when find_package(Ceres) was called. - This is fine, but users might legitimately expect the variable to be CERES_FOUND given the form of CERES_INCLUDE_DIRS/LIBRARIES. - As there is an inconsistency in the CMake recommended names when FindPackage() is called in Module vs Config form, we now explicltly define both. Change-Id: I54bce9aa112b684d26b60a9ae4d11eb7925a6ee5 commit 66e15b41d80b155f333f099a0278d50312cdaa15 Author: Sameer Agarwal Date: Fri Nov 22 07:59:23 2013 -0800 Lint cleanup from Jim Roseborough. Change-Id: I6ddbf5c3d66595d27f7967a309768e5f5dd7e1fd commit 79bde35f29291cf464b59f3dc2dd9f1fa88776a9 Author: Sameer Agarwal Date: Thu Nov 21 21:33:51 2013 -0800 SuiteSparse errors do not cause a fatal crash. 1. Move LinearSolverTerminationType to ceres::internal. 2. Add FATAL_ERROR as a new enum to LinearSolverTerminationType. 3. Pipe SuiteSparse errors via a LinearSolverTerminationType so to distinguish between fatal and non-fatal errors. 4. Update levenberg marquardt and dogleg strategies to deal with FATAL_ERROR. 5. Update trust_region_minimizer to terminate when FATAL_ERROR is encountered. 6. Remove SuiteSparse::SolveCholesky as it screws up the error handling. 7. Fix all clients calling SuiteSparse to handle the result of SuiteSparse::Cholesky correctly. 8. Remove fatal failures in SuiteSparse when symbolic factorization fails. 9. Fix all clients of SuiteSparse to deal with null symbolic factors. This is a temporary fix to deal with some production problems. A more extensive cleanup and testing regime will be put in place in a subsequent CL. Change-Id: I1f60d539799dd95db7ecc340911e261fa4824f92 commit a674e0f8534ea6948f70a72fe9718e07b3d039ff Author: Sameer Agarwal Date: Thu Nov 21 22:12:15 2013 -0800 Fix corrector_test.cc. Fix two death tests dealing with the sign of the gradient. Change-Id: Ic91d54a64cc509307c94fce6d1fca083078936e2 commit a8006af3110e98d64fb369e958fc00ec88d771a3 Author: Alex Stewart Date: Wed Nov 20 19:56:06 2013 +0000 Adding threads libraries to exported dependencies if using OpenMP. - Previously we were only adding the flags to the link flags for the Ceres project, which resulted in them not being exported. Thus projects importing Ceres (if using OpenMP) would have to manually specify them in addition to CERES_LIBRARIES. Change-Id: If0354cc07e84dbebfc870a8862e1a8ca64659791 commit 6c0d96424e2c27326757936a3738f9efc37c6c24 Author: Sameer Agarwal Date: Wed Nov 20 11:52:01 2013 -0800 Minor documentation fix. Thanks to Satya Mallick. Change-Id: I556f1c141bf16739d54450351b0f29fd4ea40014 commit 7747bb0e6b0e54366933ed75c1bcafe6a1109c3d Author: Sameer Agarwal Date: Wed Nov 20 11:29:22 2013 -0800 Minor corrections to the documentation. Thanks to Satya Mallick for reporting these. Change-Id: Ia52e08a7e21d5247dc475cfbf10bf57265aa118f commit 3fca2c4b2fae9abcaa9611f2bd3885ce6b11963b Author: Alex Stewart Date: Mon Nov 18 10:26:49 2013 +0000 Decreasing update threshold for BFGS as per L-BFGS. - Improves performance of BFGS on NIST, as per L-BFGS. - Adding explanation of origin and purpose of Secant condition tolerance check for Hessian update in (L)BFGS. Change-Id: If57b9957d31d8629c772c19a069e1e56e727b350 commit 54fcbf893852272ba2158d6a56572a2eb3ccc41f Author: Sameer Agarwal Date: Tue Nov 19 10:12:05 2013 -0800 Relax the requirements on loss functiond derivatives. We now require that the first derivative of the loss function be positive only if the second derivative is non-zero. This is because when the second derivative is non-positive, we do not use the second order correction suggested by BANS and instead use a simpler first order strategy which does not use a division by the gradient of the loss function. Change-Id: I3d65713f152611998e196ff389a7081acfdfd8c1 commit db98425b94c9eff9b125bf4a854545162e8c1aec Author: Sameer Agarwal Date: Fri Nov 15 14:14:09 2013 -0800 Small bugfix to logging.h from Scott Ettinger. Change-Id: Ie6d51e7883adf36c6fc7a78ff95afab6a78e488b commit 4d0e626b55f36ab8f44a4acc8157b85cfecd4673 Author: Alex Stewart Date: Fri Nov 15 13:53:44 2013 +0000 Fixing gflags HINTS variable names (adding missing “_DIR”). - The HINTS variables for gflags were incorrectly used as GFLAGS_[INCLUDE/LIBRARY]_HINTS when they should have been GFLAGS_[INCLUDE/LIBRARY]_DIR_HINTS as per the docs. - Also removing a completed TODO in the main CMakeLists. - Updating method of extracting current directory in CeresConfig.cmake to avoid use of CMAKE_CURRENT_LIST_DIR, which was not present in CMake =< v2.8.3. Change-Id: I42ae696e3b785febe48688d912f0f343e8947cb0 commit bf4c1b76e4926c738fc805e9ff4be0ed584d9eee Author: Alex Stewart Date: Thu Nov 14 21:27:20 2013 +0000 Decreasing threshold at which L-BFGS Hessian is updated. - Decreasing threshold at which L-BFGS Hessian is updated from 1e-10 to 1e-14 results in a very significant improvement in NIST scores (43 -> 53 for CUBIC). - Adding comment in FindPolynomialRoots() explaining why behaviour is correct. Change-Id: If668e087e7a86d29659aa74e8528b192b604c841 commit 7124c3474cd201134c3a3350b46aca468f1edafa Author: Alex Stewart Date: Thu Nov 7 16:10:02 2013 +0000 Fixes for some line search bugs & corner cases. - Increase precision of numeric values output in error messages to allow for easier debugging. - Ensure termination after Wolfe search bracketing phase if bracket width has been shrunk to below tolerance. - Cleaned up return value for BracketingPhase(), now false iff optimisation should stop, true otherwise. - Fix bug whereby we would mark a step size as satisfying the Wolfe conditions when it did not due to numerical issues in the cost function. - Adding explanation of a subtlety in which a zoom could still be acceptably invoked with bracket_low.f > bracket_high.f. - Replacing hard check of a pre-condition of ZoomPhase() with a conditional return if not satisfied to address issue whereby a bracket could be incorrectly identified due to inconsistent values & gradients returned from the cost function. - Adding missing check for step size validity in line search minimizer. - Adding ToDebugString() for FunctionSample. Change-Id: Iad98e635749877f80c079ebad126bf022d82232d commit 54fc9423673886ac9ed3fe329a80f07544aeea70 Author: Alex Stewart Date: Thu Nov 14 11:42:00 2013 +0000 Removing incorrect specialisation of install dirs on Windows. - Previously on Windows the leaf include & lib install directories passed to CeresConfig.cmake.in when configured where capitalised on Windows. - This capitalisation was incorrect, as the actual paths used are specified in the install() statements and are always in the standard lower-case form. - This likely did not cause any issues previously as although NTFS is case sensitive, the Win32 API is not, and most applications access files through the Win32 API, and are thus not case-sensitive. Change-Id: I335b6e2d10a1c64f320c2a1a68eeda1b22344e73 commit fcbbb11e37386097b1427dc3aa89f264d6951ded Author: Alex Stewart Date: Wed Nov 13 22:22:30 2013 +0000 Ensure build paths for dependencies are searched in FindPackage(Ceres) - Append to hint locations used by FindPackage scripts for public dependencies (glog & Eigen) the locations of the dependencies when Ceres was built. - This means that the user should not have to supply them again when using find_package(Ceres) even if they are installed in a non-standard location. Change-Id: I9550de91025ba47f01f1ea3c3fefe80fe38d14ff commit 7899e45d378f589a67ad8e042bf6a7cb7e15df00 Author: Alex Stewart Date: Wed Nov 13 21:08:27 2013 +0000 Fixing a documentation typo, DIRS -> DIR in HINTS variables. Change-Id: I42b75a5e0b8a451c3a43ab29d0c14856e4b86ab8 commit 1a041c35b780e60c3b497eb096b72ad20f47960e Author: Sameer Agarwal Date: Tue Nov 12 14:17:52 2013 -0800 Update to 1.8.0. Change-Id: Id42e594f03e3575d06e18c1ef66df64f43d86839 commit 36b26139296060511718b3ef0da03a52706db481 Author: Alex Stewart Date: Thu Nov 7 16:57:36 2013 +0000 Fix ordering of ParseCommandLineFlags() & InitGoogleTest() for Windows. - On Windows gtest passes additional non-gflags command line flags for death-tests, to avoid gflags invoking an error for these flags InitGoogleTest() must be called before ParseCommandLineFlags() to handle and remove them before gflags parses the remaining flags. Change-Id: I0c705ecd3aa029b70a2589b592e6a2c192745c0e commit 8c155d51fab099ee7bf64f4bdbfeda82881925a5 Author: Sameer Agarwal Date: Fri Nov 8 08:04:44 2013 -0800 Speed up the application of robust loss functions. Since we added special handling for the case for rho[2] < 0, the bulk of CorrectJacobian is pointless in the common case. So add a simple one dimensional loop which rescales the Jacobian. This speeds up this method immensely. The robustification of a Jacobian gets speeded up by > 50%. Change-Id: I97c4e897ccbb5521c053e1fb931c5d0d32f542c7 commit 58792dc8ee0e4b56331f33f753f1b1932c5c2960 Author: Sameer Agarwal Date: Wed Nov 6 09:42:46 2013 -0800 Update to 1.8.0rc2. Change-Id: Ifbf5312377bf1791a29aefd3edc3a765999c5824 commit af04d7f18740faf452e9171af530aa1bdead44bb Author: Sameer Agarwal Date: Tue Nov 5 13:47:30 2013 -0800 Remove DCHECK_GE checks from fixed_array.h This triggers -Wtype-limits warnings on comparisons which are always true, since the test being done is n >= 0, where n is of type size_t, which is always true. This causes problems when compiling Ceres on linux with miniglog. Change-Id: Ia1d1d1483e03469c71fde029b62ca6d84e9b27e0