1.. _chapter-solving_faqs: 2 3.. default-domain:: cpp 4 5.. cpp:namespace:: ceres 6 7======= 8Solving 9======= 10 11#. How do I evaluate the Jacobian for a solved problem? 12 13 Using :func:`Problem::Evaluate`. 14 15#. How do I choose the right linear solver? 16 17 When using the ``TRUST_REGION`` minimizer, the choice of linear 18 solver is an important decision. It affects solution quality and 19 runtime. Here is a simple way to reason about it. 20 21 1. For small (a few hundred parameters) or dense problems use 22 ``DENSE_QR``. 23 24 2. For general sparse problems (i.e., the Jacobian matrix has a 25 substantial number of zeros) use 26 ``SPARSE_NORMAL_CHOLESKY``. This requires that you have 27 ``SuiteSparse`` or ``CXSparse`` installed. 28 29 3. For bundle adjustment problems with up to a hundred or so 30 cameras, use ``DENSE_SCHUR``. 31 32 4. For larger bundle adjustment problems with sparse Schur 33 Complement/Reduced camera matrices use ``SPARSE_SCHUR``. This 34 requires that you build Ceres with support for ``SuiteSparse``, 35 ``CXSparse`` or Eigen's sparse linear algebra libraries. 36 37 If you do not have access to these libraries for whatever 38 reason, ``ITERATIVE_SCHUR`` with ``SCHUR_JACOBI`` is an 39 excellent alternative. 40 41 5. For large bundle adjustment problems (a few thousand cameras or 42 more) use the ``ITERATIVE_SCHUR`` solver. There are a number of 43 preconditioner choices here. ``SCHUR_JACOBI`` offers an 44 excellent balance of speed and accuracy. This is also the 45 recommended option if you are solving medium sized problems for 46 which ``DENSE_SCHUR`` is too slow but ``SuiteSparse`` is not 47 available. 48 49 .. NOTE:: 50 51 If you are solving small to medium sized problems, consider 52 setting ``Solver::Options::use_explicit_schur_complement`` to 53 ``true``, it can result in a substantial performance boost. 54 55 If you are not satisfied with ``SCHUR_JACOBI``'s performance try 56 ``CLUSTER_JACOBI`` and ``CLUSTER_TRIDIAGONAL`` in that 57 order. They require that you have ``SuiteSparse`` 58 installed. Both of these preconditioners use a clustering 59 algorithm. Use ``SINGLE_LINKAGE`` before ``CANONICAL_VIEWS``. 60 61#. Use :func:`Solver::Summary::FullReport` to diagnose performance problems. 62 63 When diagnosing Ceres performance issues - runtime and convergence, 64 the first place to start is by looking at the output of 65 ``Solver::Summary::FullReport``. Here is an example 66 67 .. code-block:: bash 68 69 ./bin/bundle_adjuster --input ../data/problem-16-22106-pre.txt 70 71 iter cost cost_change |gradient| |step| tr_ratio tr_radius ls_iter iter_time total_time 72 0 4.185660e+06 0.00e+00 2.16e+07 0.00e+00 0.00e+00 1.00e+04 0 7.50e-02 3.58e-01 73 1 1.980525e+05 3.99e+06 5.34e+06 2.40e+03 9.60e-01 3.00e+04 1 1.84e-01 5.42e-01 74 2 5.086543e+04 1.47e+05 2.11e+06 1.01e+03 8.22e-01 4.09e+04 1 1.53e-01 6.95e-01 75 3 1.859667e+04 3.23e+04 2.87e+05 2.64e+02 9.85e-01 1.23e+05 1 1.71e-01 8.66e-01 76 4 1.803857e+04 5.58e+02 2.69e+04 8.66e+01 9.93e-01 3.69e+05 1 1.61e-01 1.03e+00 77 5 1.803391e+04 4.66e+00 3.11e+02 1.02e+01 1.00e+00 1.11e+06 1 1.49e-01 1.18e+00 78 79 Ceres Solver v1.12.0 Solve Report 80 ---------------------------------- 81 Original Reduced 82 Parameter blocks 22122 22122 83 Parameters 66462 66462 84 Residual blocks 83718 83718 85 Residual 167436 167436 86 87 Minimizer TRUST_REGION 88 89 Sparse linear algebra library SUITE_SPARSE 90 Trust region strategy LEVENBERG_MARQUARDT 91 92 Given Used 93 Linear solver SPARSE_SCHUR SPARSE_SCHUR 94 Threads 1 1 95 Linear solver threads 1 1 96 Linear solver ordering AUTOMATIC 22106, 16 97 98 Cost: 99 Initial 4.185660e+06 100 Final 1.803391e+04 101 Change 4.167626e+06 102 103 Minimizer iterations 5 104 Successful steps 5 105 Unsuccessful steps 0 106 107 Time (in seconds): 108 Preprocessor 0.283 109 110 Residual evaluation 0.061 111 Jacobian evaluation 0.361 112 Linear solver 0.382 113 Minimizer 0.895 114 115 Postprocessor 0.002 116 Total 1.220 117 118 Termination: NO_CONVERGENCE (Maximum number of iterations reached.) 119 120 Let us focus on run-time performance. The relevant lines to look at 121 are 122 123 124 .. code-block:: bash 125 126 Time (in seconds): 127 Preprocessor 0.283 128 129 Residual evaluation 0.061 130 Jacobian evaluation 0.361 131 Linear solver 0.382 132 Minimizer 0.895 133 134 Postprocessor 0.002 135 Total 1.220 136 137 138 Which tell us that of the total 1.2 seconds, about .3 seconds was 139 spent in the linear solver and the rest was mostly spent in 140 preprocessing and jacobian evaluation. 141 142 The preprocessing seems particularly expensive. Looking back at the 143 report, we observe 144 145 .. code-block:: bash 146 147 Linear solver ordering AUTOMATIC 22106, 16 148 149 Which indicates that we are using automatic ordering for the 150 ``SPARSE_SCHUR`` solver. This can be expensive at times. A straight 151 forward way to deal with this is to give the ordering manually. For 152 ``bundle_adjuster`` this can be done by passing the flag 153 ``-ordering=user``. Doing so and looking at the timing block of the 154 full report gives us 155 156 .. code-block:: bash 157 158 Time (in seconds): 159 Preprocessor 0.051 160 161 Residual evaluation 0.053 162 Jacobian evaluation 0.344 163 Linear solver 0.372 164 Minimizer 0.854 165 166 Postprocessor 0.002 167 Total 0.935 168 169 170 171 The preprocessor time has gone down by more than 5.5x!. 172