Expose SubsetPreconditioner in the API

https://github.com/ceres-solver/ceres-solver/issues/270

Detailed list of changes:

1. Add SUBSET to the PreconditionerType enum.
2. Add Solver::Options::residual_blocks_for_subset_preconditioner
3. Integrate SubsetPreconditioner into the CGNR solver.
4. Add the reordering logic needed for this to TrustRegionPreprocessor.
5. Expect CreateJacobianBlockTranspose to take the starting row block
   so that we can work with subparts of the Jacobian matrix.
6. Extend the denoising example to use this preconditioner.

As an illustration of its performance, we consider the performance of
denoising -input ../data/ceres_noisy.pgm  --foe_file ../data/5x5.foe

tl;dr

For the same cost,

SPARSE_NORMAL_CHOLESKY -  81s
CGNR + JACOBI          - 718s
CGNR + SUBSET          -  57s

SPARSE_NORMAL_CHOLESKY
======================

Cost:
Initial                          2.317806e+05
Final                            2.232323e+04
Change                           2.094574e+05

Minimizer iterations                       10
Successful steps                           10
Unsuccessful steps                          0

Time (in seconds):
Preprocessor                         2.999746

  Residual only evaluation           2.306811 (10)
  Jacobian & residual evaluation     7.421727 (10)
  Linear solver                     65.517273 (10)
Minimizer                           78.731011

Postprocessor                        0.026079
Total                               81.756836

Termination:                      CONVERGENCE (Function tolerance reached. |cost_change|/cost: 8.573046e-04 <= 1.000000e-03)

CGNR + JACOBI
=============
Cost:
Initial                          2.317806e+05
Final                            2.232344e+04
Change                           2.094572e+05

Minimizer iterations                       10
Successful steps                           10
Unsuccessful steps                          0

Time (in seconds):
Preprocessor                         0.648814

  Residual only evaluation           2.297607 (10)
  Jacobian & residual evaluation     7.327886 (10)
  Linear solver                    699.601248 (10)
Minimizer                          712.419493

Postprocessor                        0.024014
Total                              713.092321

Termination:                      CONVERGENCE (Function tolerance reached. |cost_change|/cost: 8.528538e-04 <= 1.000000e-03)

CGNR + SUBSET (random 20% residuals used for the preconditioner)
===============================================================
Cost:
Initial                          2.317806e+05
Final                            2.232327e+04
Change                           2.094574e+05

Minimizer iterations                       10
Successful steps                           10
Unsuccessful steps                          0

Time (in seconds):
Preprocessor                         1.472743

  Residual only evaluation           2.428315 (10)
  Jacobian & residual evaluation     7.367796 (10)
  Linear solver                     42.585999 (10)
Minimizer                           55.664459

Postprocessor                        0.024098
Total                               57.161301

Termination:                      CONVERGENCE (Function tolerance reached. |cost_change|/cost: 8.538277e-04 <= 1.000000e-03)

Change-Id: Ifb011408bd53edbb9439b0b7345649a38f999e18
17 files changed
tree: 1d740314b431c4149ae8e7121dd90a858c7dc552
  1. .clang-format
  2. .gitignore
  3. .travis.yml
  4. BUILD
  5. CMakeLists.txt
  6. CONTRIBUTING.md
  7. LICENSE
  8. README.md
  9. WORKSPACE
  10. bazel/
  11. cmake/
  12. config/
  13. data/
  14. docs/
  15. examples/
  16. include/
  17. internal/
  18. package.xml
  19. scripts/
  20. travis/
README.md

Build Status

Ceres Solver

Ceres Solver is an open source C++ library for modeling and solving large, complicated optimization problems. It is a feature rich, mature and performant library which has been used in production at Google since 2010. Ceres Solver can solve two kinds of problems.

  1. Non-linear Least Squares problems with bounds constraints.
  2. General unconstrained optimization problems.

Please see ceres-solver.org for more information.