Add Nested Dissection ordering method to SuiteSparse

Change-Id: I5e00977839d9d5ce914bda0978d81e97e28fc673

internal/ceres/suitesparse.cc

diff --git a/internal/ceres/suitesparse.cc b/internal/ceres/suitesparse.cc
index 06b4379..4eba49e 100644
--- a/internal/ceres/suitesparse.cc
+++ b/internal/ceres/suitesparse.cc
@@ -336,6 +336,18 @@
   return cholmod_amd(matrix, nullptr, 0, ordering, &cc_);
 }
 
+bool SuiteSparse::NestedDissectionOrdering(cholmod_sparse* matrix,
+                                           int* ordering) {
+#ifdef CERES_NO_METIS
+  return false;
+#else
+  std::vector<int> CParent(matrix->nrow, 0);
+  std::vector<int> CMember(matrix->nrow, 0);
+  return cholmod_nested_dissection(
+      matrix, nullptr, 0, ordering, CParent.data(), CMember.data(), &cc_);
+#endif
+}
+
 bool SuiteSparse::ConstrainedApproximateMinimumDegreeOrdering(
     cholmod_sparse* matrix, int* constraints, int* ordering) {
 #ifndef CERES_NO_CAMD

internal/ceres/suitesparse.h

diff --git a/internal/ceres/suitesparse.h b/internal/ceres/suitesparse.h
index 816d2f1..ad7b0da 100644
--- a/internal/ceres/suitesparse.h
+++ b/internal/ceres/suitesparse.h
@@ -237,6 +237,9 @@
   // ordering.
   bool ApproximateMinimumDegreeOrdering(cholmod_sparse* matrix, int* ordering);
 
+  // Find a fill reducing ordering using nested dissection.
+  bool NestedDissectionOrdering(cholmod_sparse* matrix, int* ordering);
+
   // Before SuiteSparse version 4.2.0, cholmod_camd was only enabled
   // if SuiteSparse was compiled with Metis support. This makes
   // calling and linking into cholmod_camd problematic even though it
@@ -251,6 +254,16 @@
     return (SUITESPARSE_VERSION > 4001);
   }
 
+  // Nested dissection is only available if SuiteSparse is compiled
+  // with Metis support.
+  static bool IsNestedDissectionAvailable() {
+#ifdef CERES_NO_METIS
+    return false;
+#else
+    return true;
+#endif
+  }
+
   // Find a fill reducing approximate minimum degree
   // ordering. constraints is an array which associates with each
   // column of the matrix an elimination group. i.e., all columns in