tree e633f8d7dec916c96c2890afa1b94503d3b2c419
parent 89b3e1f88fe548fba30759d88f5389b784165470
author Sameer Agarwal <sameeragarwal@google.com> 1667253686 -0700
committer Sameer Agarwal <sameeragarwal@google.com> 1667253817 -0700

Fix a regression in SuiteSparse::AnalyzeCholesky

When AnalyzeCholesky is called on a Jacobian which has been
pre-ordered in the preprocessor, we assume a NATURAL ordering.
In this case, asking CHOLMOD to do a postordering is detrimental
to the performance. This regression was introduced in

https://github.com/ceres-solver/ceres-solver/commit/d09f7e9d5e3bfab2d7ec7e81fd6a55786edca17a

based on an email exchange with Prof. Tim Davis the author of CHOLMOD
who suggested that this should be innocous. Unfortunately this is not
the case. The following table shows the performance of bundle_adjuster
on a variety of problems. This matches the performance of the
bundle adjuster before the CL that introduced the regression.

                               Before      After
problem-49-7776-pre.txt
SPARSE_NORMAL_CHOLESKY + AMD      0.8        0.6
SPARSE_NORMAL_CHOLESKY + NESDIS   0.8        0.6
SPARSE_SCHUR + AMD                0.1        0.1
SPARSE_SCHUR + NESDIS             0.1        0.1

problem-1778-993923-pre.txt
SPARSE_NORMAL_CHOLESKY + AMD    247.1      197.0
SPARSE_NORMAL_CHOLESKY + NESDIS 234.0      193.2
SPARSE_SCHUR + AMD               78.7       71.8
SPARSE_SCHUR + NESDIS            78.7       71.4

problem-1031-110968-pre.txt
SPARSE_NORMAL_CHOLESKY + AMD     26.1       22.4
SPARSE_NORMAL_CHOLESKY + NESDIS  26.0       23.0
SPARSE_SCHUR + AMD               14.9       13.1
SPARSE_SCHUR + NESDIS            14.9       13.1

problem-356-226730-pre.txt
SPARSE_NORMAL_CHOLESKY + AMD     43.9       34.7
SPARSE_NORMAL_CHOLESKY + NESDIS  42.5       34.8
SPARSE_SCHUR + AMD                6.8        6.1
SPARSE_SCHUR + NESDIS             6.8        6.1

problem-951-708276-pre.txt
SPARSE_NORMAL_CHOLESKY + AMD    170.3      139.0
SPARSE_NORMAL_CHOLESKY + NESDIS 168.9      139.8
SPARSE_SCHUR + AMD               52.3       47.9
SPARSE_SCHUR + NESDIS            52.0       47.7

Change-Id: I6421060dd835ab2fc81d270238f6f67e29f3ecd5