commit 487c1aa51fee4fa3edb149392c92faebc0d537b1
author Sameer Agarwal <sameeragarwal@google.com> Wed Jul 10 04:41:46 2019 +0200
committer Sameer Agarwal <sameeragarwal@google.com> Fri Jul 12 16:08:36 2019 +0200
tree 1d740314b431c4149ae8e7121dd90a858c7dc552
parent bf709ecac2e0acc57e37d02243f51031403ededc

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