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
diff --git a/internal/ceres/linear_solver.h b/internal/ceres/linear_solver.h
index f4bd0fb..ca10faa 100644
--- a/internal/ceres/linear_solver.h
+++ b/internal/ceres/linear_solver.h
@@ -74,7 +74,7 @@
: type(SPARSE_NORMAL_CHOLESKY),
preconditioner_type(JACOBI),
sparse_linear_algebra_library(SUITE_SPARSE),
- use_block_amd(true),
+ use_postordering(false),
min_num_iterations(1),
max_num_iterations(1),
num_threads(1),
@@ -90,8 +90,8 @@
SparseLinearAlgebraLibraryType sparse_linear_algebra_library;
- // See solver.h for explanation of this option.
- bool use_block_amd;
+ // See solver.h for information about this flag.
+ bool use_postordering;
// Number of internal iterations that the solver uses. This
// parameter only makes sense for iterative solvers like CG.
