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

internal/ceres/schur_complement_solver.cc

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);

internal/ceres/trust_region_preprocessor.cc

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));