Schur Eliminator: Bug in DetectStructure()?

[Werner Trobin]

Hello,

      I'm using the sparse Schur complement solver and after a couple of extensions to my model I'm hitting asserts in the solver code. After some debugging it seems that the DetectStructure() call in internal/ceres/detect_structure.cc is a bit too optimistic about early stopping.

The current implementation returns as soon as it hits the first row that does not contain a reference to an E block (line 54). In my case this results in a <-1, 3, 6> configuration for the Schur complement solver. However, my model contains F blocks with a size != 6 but these are not linked to any E block. The (incorrectly) fixed F block size leads to problems; the first one is around line 197 in internal/ceres/schur_eliminator_impl.h

The attached patch contains one possible fix for that problem (attention: the patch was created using "diff -b" to make it less confusing to read). I guess the more elegant way would be splitting out a second loop that just scans the remaining F blocks before it returns. Either way, applying the attached patch results in a <-1, 3, -1> configuration and the Schur eliminator works properly. Well, almost. The attached patch also fixes a small typo in internal/ceres/small_blas.h

Ciao,

Werner

[Sameer Agarwal]

Werner,

Yes you are right, that is a bug. Could you submit the fix and a test via gerrit.

https://ceres-solver.googlesource.com/

Instructions are at 

http://ceres-solver.org/contributing.html

Also please split the small_blas fix from the detectstructure fix into two separate patches.

Sameer

--
You received this message because you are subscribed to the Google Groups "Ceres Solver" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/da05de5f-4f31-4c88-81c2-199d1ad678a3%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Sameer Agarwal]

Werner,

My apologies for the delay, but I finally got a chance to look at the problem you described. Your bug report is true, but the cause and the solution of the problem is not quite correct. Here is why:

DetectStructure is supposed to detect the static structure in the Jacobian matrix only for rows that contain an e-block, because the template specialization in the schur eliminator is only supposed to be used for rows with e-blocks. For rows without e-blocks, we are careful not to use template specialized code. Except for the one case you pointed out, where I was updating the diagonal blocks of the Schur complement using the statically detected f-block size.

So the solution is not to modify detect_structure.cc but to fix the schur eliminator. Please take a look at 

https://ceres-solver-review.googlesource.com/#/c/6930/1

and I believe it should solve the problems you are seeing. I have also added better documentation to detect_structure.h.

The fix to detect_structure that you proposed is actually not wrong. It would fix the problem, but it would do so by reducing the number of cases in which we can use a fixed f-block size. Since the bulk of the rows in which we use the Schur eliminator contain e-blocks, it is better from a performance point of view to try and use as much statically sized matrix operations as possible.

Sameer

[Werner Trobin]

Thanks a lot Sameer, your patch indeed fixes my problem (and it looks a lot cleaner than my patch ;-)

Ciao,

Werner