SPARSE_SCHUR + CX_SPARSE = Faster
There was a bug in the trust region preprocessor where no fill
reducing ordering was computed for the case of SPARSE_SCHUR + CX_SPARSE
but this was not signaled to SchurComplementSolver, so it was using
a naive/natural ordering. To fix this two changes are made:
1. TrustRegionProcessor's logic for signaling the ordering to the
linear solver has been re-worked. The surrounding code has also
been re-organized for better readability.
2. In SchurComplementSolver::SolveReducedSystem the row and column
block structure has been added to the CompressedRowSparseMatrix
containing the Schur complement so that block AMD can be used.
As a result of these changes the linear solve time for
problem-744-543562-pre.txt has been brought down from 58 seconds to
35 seconds.
Change-Id: I4d82efce05175260f97b1f925f8a1b4a9d650cae
diff --git a/internal/ceres/schur_complement_solver.cc b/internal/ceres/schur_complement_solver.cc
index 1a1becb..16470fd 100644
--- a/internal/ceres/schur_complement_solver.cc
+++ b/internal/ceres/schur_complement_solver.cc
@@ -337,6 +337,9 @@
lhs->set_storage_type(CompressedRowSparseMatrix::LOWER_TRIANGULAR);
}
+ *lhs->mutable_col_blocks() = blocks_;
+ *lhs->mutable_row_blocks() = blocks_;
+
summary.num_iterations = 1;
summary.termination_type = sparse_cholesky_->FactorAndSolve(
lhs.get(), rhs(), solution, &summary.message);
diff --git a/internal/ceres/trust_region_preprocessor.cc b/internal/ceres/trust_region_preprocessor.cc
index 4020e4c..d3f912c 100644
--- a/internal/ceres/trust_region_preprocessor.cc
+++ b/internal/ceres/trust_region_preprocessor.cc
@@ -121,6 +121,7 @@
&pp->error);
}
+
if (options.linear_solver_type == SPARSE_NORMAL_CHOLESKY &&
!options.dynamic_sparsity) {
return ReorderProgramForSparseNormalCholesky(
@@ -192,28 +193,40 @@
options.use_explicit_schur_complement;
pp->linear_solver_options.dynamic_sparsity = options.dynamic_sparsity;
pp->linear_solver_options.num_threads = options.num_linear_solver_threads;
-
- // Ignore user's postordering preferences and force it to be true if
- // cholmod_camd is not available. This ensures that the linear
- // solver does not assume that a fill-reducing pre-ordering has been
- // done.
pp->linear_solver_options.use_postordering = options.use_postordering;
- if (options.linear_solver_type == SPARSE_SCHUR &&
- options.sparse_linear_algebra_library_type == SUITE_SPARSE &&
- !SuiteSparse::IsConstrainedApproximateMinimumDegreeOrderingAvailable()) {
- pp->linear_solver_options.use_postordering = true;
- }
- OrderingToGroupSizes(options.linear_solver_ordering.get(),
- &pp->linear_solver_options.elimination_groups);
+ if (IsSchurType(pp->linear_solver_options.type)) {
+ OrderingToGroupSizes(options.linear_solver_ordering.get(),
+ &pp->linear_solver_options.elimination_groups);
- // Schur type solvers expect at least two elimination groups. If
- // there is only one elimination group, then it is guaranteed that
- // this group only contains e_blocks. Thus we add a dummy
- // elimination group with zero blocks in it.
- if (IsSchurType(pp->linear_solver_options.type) &&
- pp->linear_solver_options.elimination_groups.size() == 1) {
- pp->linear_solver_options.elimination_groups.push_back(0);
+ // Schur type solvers expect at least two elimination groups. If
+ // there is only one elimination group, then it is guaranteed that
+ // this group only contains e_blocks. Thus we add a dummy
+ // elimination group with zero blocks in it.
+ if (pp->linear_solver_options.elimination_groups.size() == 1) {
+ pp->linear_solver_options.elimination_groups.push_back(0);
+ }
+
+ if (options.linear_solver_type == SPARSE_SCHUR) {
+ // When using SPARSE_SCHUR, we ignore the user's postordering
+ // preferences in certain cases.
+ //
+ // 1. SUITE_SPARSE is the sparse linear algebra library requested
+ // but cholmod_camd is not available.
+ // 2. CX_SPARSE is the sparse linear algebra library requested.
+ //
+ // This ensures that the linear solver does not assume that a
+ // fill-reducing pre-ordering has been done.
+ //
+ // TODO(sameeragarwal): Implement the reordering of parameter
+ // blocks for CX_SPARSE.
+ if ((options.sparse_linear_algebra_library_type == SUITE_SPARSE &&
+ !SuiteSparse::
+ IsConstrainedApproximateMinimumDegreeOrderingAvailable()) ||
+ (options.sparse_linear_algebra_library_type == CX_SPARSE)) {
+ pp->linear_solver_options.use_postordering = true;
+ }
+ }
}
pp->linear_solver.reset(LinearSolver::Create(pp->linear_solver_options));
