Add Nested Dissection ordering method to SuiteSparse
Change-Id: I5e00977839d9d5ce914bda0978d81e97e28fc673
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
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