Provide optional METIS support
* Split `CERES_NO_METIS` into two defines: `CERES_NO_PARTITION` and
`CERES_NO_METIS`. The former refers to METIS support in SuiteSparse,
the latter to the Eigen's MetisSupport module. This enables the use of
sparse matrix reordering independent from SuiteSparse.
* Run Linux, macOS, and macOS Github workflows with METIS enabled
SuiteSparse.
Fixes #808
Change-Id: I5076b7e1268d32cc3e7e56650edcbaf7fb3b59ce
diff --git a/.github/workflows/linux.yml b/.github/workflows/linux.yml
index 1214fd0..4f9d29b 100644
--- a/.github/workflows/linux.yml
+++ b/.github/workflows/linux.yml
@@ -46,6 +46,7 @@
libgflags-dev \
libgoogle-glog-dev \
liblapack-dev \
+ libmetis-dev \
libsuitesparse-dev \
ninja-build
diff --git a/.github/workflows/macos.yml b/.github/workflows/macos.yml
index 431ad6c..03e5f8d 100644
--- a/.github/workflows/macos.yml
+++ b/.github/workflows/macos.yml
@@ -48,6 +48,7 @@
gflags \
glog \
google-benchmark \
+ metis \
ninja \
suite-sparse
diff --git a/.github/workflows/windows.yml b/.github/workflows/windows.yml
index 3c4a5a5..b7e5a2f 100644
--- a/.github/workflows/windows.yml
+++ b/.github/workflows/windows.yml
@@ -92,12 +92,12 @@
uses: actions/cache@v2
with:
path: suitesparse/
- key: ${{matrix.msvc}}-suitesparse-5.11.0-cmake.2-${{matrix.arch}}-${{matrix.build_type}}-${{matrix.lib}}
+ key: ${{matrix.msvc}}-suitesparse-5.12.0-cmake.3-${{matrix.arch}}-${{matrix.build_type}}-${{matrix.lib}}
- name: Download SuiteSparse
if: steps.cache-suitesparse.outputs.cache-hit != 'true'
run: |
- (New-Object System.Net.WebClient).DownloadFile("https://github.com/sergiud/SuiteSparse/releases/download/5.11.0-cmake.2/SuiteSparse-5.11.0-cmake.2-${{matrix.marker}}-Win64-${{matrix.build_type}}-${{matrix.lib}}-gpl.zip", "suitesparse.zip");
+ (New-Object System.Net.WebClient).DownloadFile("https://github.com/sergiud/SuiteSparse/releases/download/5.12.0-cmake.3/SuiteSparse-5.12.0-cmake.3-${{matrix.marker}}-Win64-${{matrix.build_type}}-${{matrix.lib}}-gpl-metis.zip", "suitesparse.zip");
Expand-Archive -Path suitesparse.zip -DestinationPath ${{github.workspace}}/suitesparse;
- name: Cache Eigen
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 21eaefb..f0d86f5 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -119,7 +119,9 @@
enable_testing()
include(CeresThreadingModels)
+include(CMakeDependentOption)
include(PrettyPrintCMakeList)
+
find_available_ceres_threading_models(CERES_THREADING_MODELS_AVAILABLE)
pretty_print_cmake_list(PRETTY_CERES_THREADING_MODELS_AVAILABLE
${CERES_THREADING_MODELS_AVAILABLE})
@@ -155,6 +157,7 @@
# Enable the use of Eigen as a sparse linear algebra library for
# solving the nonlinear least squares problems.
option(EIGENSPARSE "Enable Eigen as a sparse linear algebra library." ON)
+cmake_dependent_option(EIGENMETIS "Enable Eigen METIS support." ON EIGENSPARSE OFF)
option(EXPORT_BUILD_DIR
"Export build directory using CMake (enables external use without install)." OFF)
option(BUILD_TESTING "Enable tests" ON)
@@ -265,7 +268,8 @@
# built with SuiteSparse support.
# Check for SuiteSparse and dependencies.
- find_package(SuiteSparse 4.5.6 COMPONENTS CHOLMOD SPQR)
+ find_package(SuiteSparse 4.5.6 COMPONENTS CHOLMOD SPQR
+ OPTIONAL_COMPONENTS Partition)
if (SuiteSparse_FOUND)
set(SuiteSparse_DEPENDENCY "find_dependency(SuiteSparse ${SuiteSparse_VERSION})")
# By default, if all of SuiteSparse's dependencies are found, Ceres is
@@ -290,6 +294,30 @@
list(APPEND CERES_COMPILE_OPTIONS CERES_NO_SUITESPARSE)
endif (SUITESPARSE)
+if (NOT SuiteSparse_Partition_FOUND)
+ list (APPEND CERES_COMPILE_OPTIONS CERES_NO_CHOLMOD_PARTITION)
+endif (NOT SuiteSparse_Partition_FOUND)
+
+if (EIGENMETIS)
+ find_package (METIS)
+ if (METIS_FOUND)
+ # Since METIS is a private dependency of Ceres, it requires access to the
+ # link-only METIS::METIS target to avoid undefined linker errors in projects
+ # relying on Ceres. We do not actually need to propagate anything besides
+ # the link libraries (such as include directories.)
+ set(METIS_DEPENDENCY "find_dependency(METIS ${METIS_VERSION})")
+ # METIS find module must be installed unless a package config is being used.
+ if (NOT METIS_DIR)
+ install(FILES ${Ceres_SOURCE_DIR}/cmake/FindMETIS.cmake
+ DESTINATION ${RELATIVE_CMAKECONFIG_INSTALL_DIR})
+ endif (NOT METIS_DIR)
+ endif (METIS_FOUND)
+endif (EIGENMETIS)
+
+if (NOT EIGENMETIS OR NOT METIS_FOUND)
+ list (APPEND CERES_COMPILE_OPTIONS CERES_NO_EIGEN_METIS)
+endif (NOT EIGENMETIS OR NOT METIS_FOUND)
+
if (ACCELERATESPARSE)
find_package(AccelerateSparse)
if (AccelerateSparse_FOUND)
diff --git a/bazel/ceres.bzl b/bazel/ceres.bzl
index 87dca32..f293424 100644
--- a/bazel/ceres.bzl
+++ b/bazel/ceres.bzl
@@ -203,15 +203,16 @@
# part of a Skylark Ceres target macro.
# https://github.com/ceres-solver/ceres-solver/issues/396
defines = [
- "CERES_NO_SUITESPARSE",
- "CERES_NO_METIS",
- "CERES_NO_ACCELERATE_SPARSE",
- "CERES_NO_LAPACK",
- "CERES_USE_EIGEN_SPARSE",
- "CERES_USE_CXX_THREADS",
- "CERES_NO_CUDA",
"CERES_EXPORT=",
+ "CERES_NO_ACCELERATE_SPARSE",
+ "CERES_NO_CHOLMOD_PARTITION",
+ "CERES_NO_CUDA",
+ "CERES_NO_EIGEN_METIS",
"CERES_NO_EXPORT=",
+ "CERES_NO_LAPACK",
+ "CERES_NO_SUITESPARSE",
+ "CERES_USE_CXX_THREADS",
+ "CERES_USE_EIGEN_SPARSE",
],
includes = [
"config",
diff --git a/cmake/CeresConfig.cmake.in b/cmake/CeresConfig.cmake.in
index 32108e4..33d8078 100644
--- a/cmake/CeresConfig.cmake.in
+++ b/cmake/CeresConfig.cmake.in
@@ -177,6 +177,7 @@
include(CMakeFindDependencyMacro)
# Optional dependencies
+@METIS_DEPENDENCY@
@OpenMP_DEPENDENCY@
@SuiteSparse_DEPENDENCY@
@Threads_DEPENDENCY@
diff --git a/cmake/FindSuiteSparse.cmake b/cmake/FindSuiteSparse.cmake
index 768b5df..4e05930 100644
--- a/cmake/FindSuiteSparse.cmake
+++ b/cmake/FindSuiteSparse.cmake
@@ -78,6 +78,9 @@
``SuiteSparse::CHOLMOD``
Sparse Supernodal Cholesky Factorization and Update/Downdate (CHOLMOD)
+``SuiteSparse::Partition``
+ CHOLMOD with METIS support
+
``SuiteSparse::SPQR``
Multifrontal Sparse QR (SuiteSparseQR)
@@ -124,6 +127,8 @@
set (SuiteSparse_FOUND TRUE)
include (CheckLibraryExists)
+include (CheckSymbolExists)
+include (CMakePushCheckState)
# Config is a base component and thus always required
set (SuiteSparse_IMPLICIT_COMPONENTS Config)
@@ -299,6 +304,11 @@
endif (NOT LAPACK_FOUND)
foreach (component IN LISTS SuiteSparse_FIND_COMPONENTS)
+ if (component STREQUAL Partition)
+ # Partition is a meta component that neither provides additional headers nor
+ # a separate library. It is strictly part of CHOLMOD.
+ continue ()
+ endif (component STREQUAL Partition)
string (TOLOWER ${component} component_library)
if (component STREQUAL "Config")
@@ -417,17 +427,8 @@
endif (NOT EXISTS ${SuiteSparse_VERSION_FILE})
endif (TARGET SuiteSparse::Config)
-# METIS (Optional dependency).
-find_package (METIS)
-
# CHOLMOD requires AMD CAMD CCOLAMD COLAMD
if (TARGET SuiteSparse::CHOLMOD)
- # METIS is optional
- if (TARGET METIS::METIS)
- set_property (TARGET SuiteSparse::CHOLMOD APPEND PROPERTY
- INTERFACE_LINK_LIBRARIES METIS::METIS)
- endif (TARGET METIS::METIS)
-
foreach (component IN ITEMS AMD CAMD CCOLAMD COLAMD)
if (TARGET SuiteSparse::${component})
set_property (TARGET SuiteSparse::CHOLMOD APPEND PROPERTY
@@ -464,6 +465,44 @@
endforeach (component IN LISTS SuiteSparse_FIND_COMPONENTS)
endif (TARGET SuiteSparse::Config)
+# Check whether CHOLMOD was compiled with METIS support. The check can be
+# performed only after the main components have been set up.
+if (TARGET SuiteSparse::CHOLMOD)
+ # NOTE If SuiteSparse was compiled as a static library we'll need to link
+ # against METIS already during the check. Otherwise, the check can fail due to
+ # undefined references even though SuiteSparse was compiled with METIS.
+ find_package (METIS)
+
+ if (TARGET METIS::METIS)
+ cmake_push_check_state (RESET)
+ set (CMAKE_REQUIRED_LIBRARIES SuiteSparse::CHOLMOD METIS::METIS)
+ check_symbol_exists (cholmod_metis cholmod.h SuiteSparse_CHOLMOD_USES_METIS)
+ cmake_pop_check_state ()
+
+ if (SuiteSparse_CHOLMOD_USES_METIS)
+ set_property (TARGET SuiteSparse::CHOLMOD APPEND PROPERTY
+ INTERFACE_LINK_LIBRARIES $<LINK_ONLY:METIS::METIS>)
+
+ # Provide the SuiteSparse::Partition component whose availability indicates
+ # that CHOLMOD was compiled with the Partition module.
+ if (NOT TARGET SuiteSparse::Partition)
+ add_library (SuiteSparse::Partition IMPORTED INTERFACE)
+ endif (NOT TARGET SuiteSparse::Partition)
+
+ set_property (TARGET SuiteSparse::Partition APPEND PROPERTY
+ INTERFACE_LINK_LIBRARIES SuiteSparse::CHOLMOD)
+ endif (SuiteSparse_CHOLMOD_USES_METIS)
+ endif (TARGET METIS::METIS)
+endif (TARGET SuiteSparse::CHOLMOD)
+
+# We do not use suitesparse_find_component to find Partition and therefore must
+# handle the availability in an extra step.
+if (TARGET SuiteSparse::Partition)
+ set (SuiteSparse_Partition_FOUND TRUE)
+else (TARGET SuiteSparse::Partition)
+ set (SuiteSparse_Partition_FOUND FALSE)
+endif (TARGET SuiteSparse::Partition)
+
suitesparse_reset_find_library_prefix()
# Handle REQUIRED and QUIET arguments to FIND_PACKAGE
diff --git a/cmake/config.h.in b/cmake/config.h.in
index 66a195a..4007955 100644
--- a/cmake/config.h.in
+++ b/cmake/config.h.in
@@ -76,6 +76,11 @@
@CERES_USE_OPENMP@
// If defined Ceres was compiled with modern C++ multithreading.
@CERES_USE_CXX_THREADS@
+// If defined, Ceres was compiled with a version of SuiteSparse/CHOLMOD without
+// the Partition module (requires METIS).
+@CERES_NO_CHOLMOD_PARTITION@
+// If defined Ceres was compiled without support for METIS via Eigen.
+@CERES_NO_EIGEN_METIS@
// If defined, Ceres was compiled with a version MSVC >= 2005 which
// deprecated the standard POSIX names for bessel functions, replacing them
diff --git a/internal/ceres/CMakeLists.txt b/internal/ceres/CMakeLists.txt
index 4c9bfe7..4e5008b 100644
--- a/internal/ceres/CMakeLists.txt
+++ b/internal/ceres/CMakeLists.txt
@@ -124,8 +124,18 @@
add_definitions(-DCERES_SUITESPARSE_VERSION="${SuiteSparse_VERSION}")
list(APPEND CERES_LIBRARY_PRIVATE_DEPENDENCIES SuiteSparse::CHOLMOD
SuiteSparse::SPQR)
+
+ if (SuiteSparse_Partition_FOUND)
+ list(APPEND CERES_LIBRARY_PRIVATE_DEPENDENCIES SuiteSparse::Partition)
+ endif (SuiteSparse_Partition_FOUND)
endif (SUITESPARSE AND SuiteSparse_FOUND)
+if (EIGENMETIS AND METIS_FOUND)
+ # Define version information for use in Solver::FullReport.
+ add_definitions(-DCERES_METIS_VERSION="${METIS_VERSION}")
+ list(APPEND CERES_LIBRARY_PRIVATE_DEPENDENCIES METIS::METIS)
+endif (EIGENMETIS AND METIS_FOUND)
+
if (ACCELERATESPARSE AND AccelerateSparse_FOUND)
list(APPEND CERES_LIBRARY_PRIVATE_DEPENDENCIES ${AccelerateSparse_LIBRARIES})
endif()
diff --git a/internal/ceres/dynamic_sparse_normal_cholesky_solver_test.cc b/internal/ceres/dynamic_sparse_normal_cholesky_solver_test.cc
index b0c218d..f9ff443 100644
--- a/internal/ceres/dynamic_sparse_normal_cholesky_solver_test.cc
+++ b/internal/ceres/dynamic_sparse_normal_cholesky_solver_test.cc
@@ -117,7 +117,7 @@
TestSolver(SUITE_SPARSE, OrderingType::AMD);
}
-#ifndef CERES_NO_METIS
+#ifndef CERES_NO_CHOLMOD_PARTITION
TEST_F(DynamicSparseNormalCholeskySolverTest, SuiteSparseNESDIS) {
TestSolver(SUITE_SPARSE, OrderingType::NESDIS);
}
@@ -129,7 +129,7 @@
TestSolver(EIGEN_SPARSE, OrderingType::AMD);
}
-#ifndef CERES_NO_METIS
+#ifndef CERES_NO_EIGEN_METIS
TEST_F(DynamicSparseNormalCholeskySolverTest, EigenNESDIS) {
TestSolver(EIGEN_SPARSE, OrderingType::NESDIS);
}
diff --git a/internal/ceres/eigensparse.cc b/internal/ceres/eigensparse.cc
index 3be222e..982608a 100644
--- a/internal/ceres/eigensparse.cc
+++ b/internal/ceres/eigensparse.cc
@@ -36,7 +36,7 @@
#include <sstream>
-#ifndef CERES_NO_METIS
+#ifndef CERES_NO_EIGEN_METIS
#include <iostream> // This is needed because MetisSupport depends on iostream.
#include "Eigen/MetisSupport"
@@ -157,7 +157,7 @@
if (ordering_type == OrderingType::AMD) {
return std::make_unique<EigenSparseCholeskyTemplate<WithAMDOrdering>>();
-#ifndef CERES_NO_METIS
+#ifndef CERES_NO_EIGEN_METIS
} else if (ordering_type == OrderingType::NESDIS) {
using WithMetisOrdering = Eigen::SimplicialLDLT<Eigen::SparseMatrix<double>,
Eigen::Upper,
@@ -190,7 +190,7 @@
Eigen::NaturalOrdering<int>>;
if (ordering_type == OrderingType::AMD) {
return std::make_unique<EigenSparseCholeskyTemplate<WithAMDOrdering>>();
-#ifndef CERES_NO_METIS
+#ifndef CERES_NO_EIGEN_METIS
} else if (ordering_type == OrderingType::NESDIS) {
using WithMetisOrdering = Eigen::SimplicialLDLT<Eigen::SparseMatrix<float>,
Eigen::Upper,
diff --git a/internal/ceres/eigensparse.h b/internal/ceres/eigensparse.h
index 58d15eb..04cdbad 100644
--- a/internal/ceres/eigensparse.h
+++ b/internal/ceres/eigensparse.h
@@ -51,7 +51,7 @@
class EigenSparse {
public:
static constexpr bool IsNestedDissectionAvailable() noexcept {
-#ifdef CERES_NO_METIS
+#ifdef CERES_NO_EIGEN_METIS
return false;
#else
return true;
diff --git a/internal/ceres/reorder_program.cc b/internal/ceres/reorder_program.cc
index 9f89c4b..eb37dc3 100644
--- a/internal/ceres/reorder_program.cc
+++ b/internal/ceres/reorder_program.cc
@@ -51,7 +51,7 @@
#ifdef CERES_USE_EIGEN_SPARSE
-#ifndef CERES_NO_METIS
+#ifndef CERES_NO_EIGEN_METIS
#include <iostream> // Need this because MetisSupport refers to std::cerr.
#include "Eigen/MetisSupport"
@@ -191,7 +191,7 @@
Eigen::AMDOrdering<int> amd_ordering;
amd_ordering(block_hessian, perm);
} else {
-#ifndef CERES_NO_METIS
+#ifndef CERES_NO_EIGEN_METIS
Eigen::MetisOrdering<int> metis_ordering;
metis_ordering(block_hessian, perm);
#else
@@ -400,7 +400,7 @@
Eigen::AMDOrdering<int> amd_ordering;
amd_ordering(block_schur_complement, perm);
} else {
-#ifndef CERES_NO_METIS
+#ifndef CERES_NO_EIGEN_METIS
Eigen::MetisOrdering<int> metis_ordering;
metis_ordering(block_schur_complement, perm);
#else
diff --git a/internal/ceres/schur_complement_solver_test.cc b/internal/ceres/schur_complement_solver_test.cc
index 233a599..9ec9ffe 100644
--- a/internal/ceres/schur_complement_solver_test.cc
+++ b/internal/ceres/schur_complement_solver_test.cc
@@ -215,7 +215,7 @@
3, true, SPARSE_SCHUR, EIGEN, SUITE_SPARSE, OrderingType::AMD);
}
-#ifndef CERES_NO_METIS
+#ifndef CERES_NO_EIGEN_METIS
TEST_F(SchurComplementSolverTest,
SparseSchurWithSuiteSparseSmallProblemNESDIS) {
ComputeAndCompareSolutions(
@@ -230,7 +230,7 @@
ComputeAndCompareSolutions(
3, true, SPARSE_SCHUR, EIGEN, SUITE_SPARSE, OrderingType::NESDIS);
}
-#endif // CERES_NO_METIS
+#endif // CERES_NO_EIGEN_METIS
#endif // CERES_NO_SUITESPARSE
#ifndef CERES_NO_ACCELERATE_SPARSE
@@ -275,7 +275,7 @@
2, true, SPARSE_SCHUR, EIGEN, EIGEN_SPARSE, OrderingType::AMD);
}
-#ifndef CERES_NO_METIS
+#ifndef CERES_NO_EIGEN_METIS
TEST_F(SchurComplementSolverTest,
SparseSchurWithEigenSparseSmallProblemNESDIS) {
ComputeAndCompareSolutions(
@@ -300,7 +300,7 @@
3, true, SPARSE_SCHUR, EIGEN, EIGEN_SPARSE, OrderingType::AMD);
}
-#ifndef CERES_NO_METIS
+#ifndef CERES_NO_EIGEN_METIS
TEST_F(SchurComplementSolverTest,
SparseSchurWithEigenSparseLargeProblemNESDIS) {
ComputeAndCompareSolutions(
diff --git a/internal/ceres/solver_utils.cc b/internal/ceres/solver_utils.cc
index 968b958..7cf1f32 100644
--- a/internal/ceres/solver_utils.cc
+++ b/internal/ceres/solver_utils.cc
@@ -62,10 +62,9 @@
"-suitesparse-(" CERES_SUITESPARSE_VERSION ")"
#endif
-// TODO(sergiud) Capture METIS version
-// #ifndef CERES_NO_METIS
-// "-metis-(" CERES_METIS_VERSION ")"
-// #endif
+#ifndef CERES_NO_EIGEN_METIS
+ "-metis-(" CERES_METIS_VERSION ")"
+#endif
#ifndef CERES_NO_ACCELERATE_SPARSE
"-acceleratesparse"
diff --git a/internal/ceres/suitesparse.cc b/internal/ceres/suitesparse.cc
index 88ef935..85fc5b2 100644
--- a/internal/ceres/suitesparse.cc
+++ b/internal/ceres/suitesparse.cc
@@ -345,7 +345,7 @@
return cholmod_amd(matrix, nullptr, 0, ordering, &cc_);
}
-#ifdef CERES_NO_METIS
+#ifdef CERES_NO_CHOLMOD_PARTITION
return false;
#else
std::vector<int> CParent(matrix->nrow, 0);
@@ -361,7 +361,7 @@
}
bool SuiteSparse::IsNestedDissectionAvailable() {
-#ifdef CERES_NO_METIS
+#ifdef CERES_NO_CHOLMOD_PARTITION
return false;
#else
return true;
