tree 01c7e7b2e26ca41368b0ae3ca7cf65cfe8307625
parent f7ed22efc3afee36aae71a4f7949b3d327b87f11
author Sameer Agarwal <sameeragarwal@google.com> 1366416589 -0700
committer Sameer Agarwal <sameeragarwal@google.com> 1366424843 -0700

Enable pre-ordering for SPARSE_NORMAL_CHOLESKY.

Sparse Cholesky factorization algorithms use a fill-reducing
ordering to permute the columns of the Jacobian matrix. There
are two ways of doing this.

1. Compute the Jacobian matrix in some order and then have the
   factorization algorithm permute the columns of the Jacobian.

2. Compute the Jacobian with its columns already permuted.

The first option incurs a significant memory penalty. The
factorization algorithm has to make a copy of the permuted
Jacobian matrix.

Starting with this change Ceres pre-permutes the columns of the
Jacobian matrix and generally speaking, there is no performance
penalty for doing so.

In some rare cases, it is worth using a more complicated
reordering algorithm which has slightly better runtime
performance at the expense of an extra copy of the Jacobian
matrix. Setting Solver::Options::use_postordering to true
enables this tradeoff.

This change also removes Solver::Options::use_block_amd
as an option. All matrices are ordered using their block
structure. The ability to order them by their scalar
sparsity structure has been removed.

Here is what performance on looks like on some BAL problems.

Memory
======
                                     HEAD         pre-ordering
16-22106                      137957376.0          113516544.0
49-7776                        56688640.0           46628864.0
245-198739                   1718005760.0         1383550976.0
257-65132                     387715072.0          319512576.0
356-226730                   2014826496.0         1626087424.0
744-543562                   4903358464.0         3957878784.0
1024-110968                   968626176.0          822071296.0

Time
====
                                     HEAD         pre-ordering
16-22106                              3.8                  3.7
49-7776                               1.9                  1.8
245-198739                           82.6                 81.9
257-65132                            14.0                 13.4
356-226730                           98.8                 95.8
744-543562                          325.2                301.6
1024-110968                          42.1                 37.1

Change-Id: I6b2e25f3fed7310f88905386a7898ac94d37467e