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;