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;