Add a specialized schur eliminator.

Add a new specialized Schur Eliminator for the case where there is
exactly one F block and all dimensions are known at compile time.

Benchmark on my macbook shoes ~3x speedup for Eliminate and 4x speedup for BackSubstitute.
Similar speedups are observed on other platforms.

------------------------------------------------------------------------------------------
Benchmark                                                   Time           CPU Iterations
------------------------------------------------------------------------------------------
BM_SchurEliminatorEliminate/10                           4176 ns       4132 ns     153522
BM_SchurEliminatorEliminate/64                          24392 ns      24234 ns      29993
BM_SchurEliminatorEliminate/512                        169632 ns     168709 ns       3872
BM_SchurEliminatorEliminate/4096                      1296407 ns    1292873 ns        519
BM_SchurEliminatorEliminate/10000                     3159652 ns    3149532 ns        216
BM_SchurEliminatorForOneFBlockEliminate/10               1187 ns       1184 ns     603953
BM_SchurEliminatorForOneFBlockEliminate/64               7917 ns       7898 ns      87558
BM_SchurEliminatorForOneFBlockEliminate/512             57629 ns      57485 ns      12035
BM_SchurEliminatorForOneFBlockEliminate/4096           484680 ns     480757 ns       1459
BM_SchurEliminatorForOneFBlockEliminate/10000         1157237 ns    1150735 ns        566
BM_SchurEliminatorBackSubstitute/10                       681 ns        679 ns    1070500
BM_SchurEliminatorBackSubstitute/64                      3899 ns       3887 ns     182883
BM_SchurEliminatorBackSubstitute/512                    33632 ns      33467 ns      22582
BM_SchurEliminatorBackSubstitute/4096                  241117 ns     240257 ns       2884
BM_SchurEliminatorBackSubstitute/10000                 631869 ns     626992 ns       1146
BM_SchurEliminatorForOneFBlockBackSubstitute/10           139 ns        138 ns    5021341
BM_SchurEliminatorForOneFBlockBackSubstitute/64           898 ns        892 ns     780396
BM_SchurEliminatorForOneFBlockBackSubstitute/512         7344 ns       7286 ns      87059
BM_SchurEliminatorForOneFBlockBackSubstitute/4096       57634 ns      57345 ns      11642
BM_SchurEliminatorForOneFBlockBackSubstitute/10000     153129 ns     152320 ns       4949

Change-Id: Iae64e96c91beb44b807df0e0572d202df7cdaed8
4 files changed
tree: d0dec22184e7b690ab70a51722cc0953dfd90bb7
  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.