tree 590910785a7437c2a0164a37e56851075fe423b0
parent 5a161a2b9653489ee9040f054b24df971e6b9bbc
author Sameer Agarwal <sameeragarwal@google.com> 1382935093 -0700
committer Sameer Agarwal <sameeragarwal@google.com> 1383250977 -0700

Add support for multiple visibility clustering algorithms.

The original visibility based preconditioning paper and
implementation only used the canonical views algorithm.

This algorithm for large dense graphs can be particularly
expensive. As its worst case complexity is cubic in size
of the graph.

Further, for many uses the SCHUR_JACOBI preconditioner
was both effective enough while being cheap. It however
suffers from a fatal flaw. If the camera parameter blocks
are split between two or more parameter blocks, e.g,
extrinsics and intrinsics. The preconditioner because
it is block diagonal will not capture the interactions
between them.

Using CLUSTER_JACOBI or CLUSTER_TRIDIAGONAL will fix
this problem but as mentioned above this can be quite
expensive depending on the problem.

This change extends the visibility based preconditioner
to allow for multiple clustering algorithms. And adds
a simple thresholded single linkage clustering algorithm
which allows you to construct versions of CLUSTER_JACOBI
and CLUSTER_TRIDIAGONAL preconditioners that are cheap
to construct and are more effective than SCHUR_JACOBI.

Currently the constants controlling the threshold above
which edges are considered in the single linkage algorithm
are not exposed. This would be done in a future change.

Change-Id: I7ddc36790943f24b19c7f08b10694ae9a822f5c9