diff --git a/internal/ceres/implicit_schur_complement_test.cc b/internal/ceres/implicit_schur_complement_test.cc
index f948403..bd36672 100644
--- a/internal/ceres/implicit_schur_complement_test.cc
+++ b/internal/ceres/implicit_schur_complement_test.cc
@@ -83,7 +83,7 @@
     const int num_schur_rows = blhs.num_rows();
 
     LinearSolver::Options options;
-    options.num_eliminate_blocks = num_eliminate_blocks_;
+    options.elimination_groups.push_back(num_eliminate_blocks_);
     options.type = DENSE_SCHUR;
 
     scoped_ptr<SchurEliminatorBase> eliminator(
diff --git a/internal/ceres/iterative_schur_complement_solver.cc b/internal/ceres/iterative_schur_complement_solver.cc
index 679c41f..376a586 100644
--- a/internal/ceres/iterative_schur_complement_solver.cc
+++ b/internal/ceres/iterative_schur_complement_solver.cc
@@ -67,7 +67,7 @@
   // Initialize a ImplicitSchurComplement object.
   if (schur_complement_ == NULL) {
     schur_complement_.reset(
-        new ImplicitSchurComplement(options_.num_eliminate_blocks,
+        new ImplicitSchurComplement(options_.elimination_groups[0],
                                     options_.preconditioner_type == JACOBI));
   }
   schur_complement_->Init(*A, per_solve_options.D, b);
diff --git a/internal/ceres/iterative_schur_complement_solver_test.cc b/internal/ceres/iterative_schur_complement_solver_test.cc
index d034747..86e7825 100644
--- a/internal/ceres/iterative_schur_complement_solver_test.cc
+++ b/internal/ceres/iterative_schur_complement_solver_test.cc
@@ -89,7 +89,7 @@
     Vector reference_solution(num_cols_);
     qr->Solve(&dense_A, b_.get(), per_solve_options, reference_solution.data());
 
-    options.num_eliminate_blocks = num_eliminate_blocks_;
+    options.elimination_groups.push_back(num_eliminate_blocks_);
     options.max_num_iterations = num_cols_;
     IterativeSchurComplementSolver isc(options);
 
diff --git a/internal/ceres/linear_solver.h b/internal/ceres/linear_solver.h
index 31f8874..ee7fce2 100644
--- a/internal/ceres/linear_solver.h
+++ b/internal/ceres/linear_solver.h
@@ -35,6 +35,7 @@
 #define CERES_INTERNAL_LINEAR_SOLVER_H_
 
 #include <cstddef>
+#include <vector>
 
 #include <glog/logging.h>
 #include "ceres/block_sparse_matrix.h"
@@ -76,7 +77,6 @@
           min_num_iterations(1),
           max_num_iterations(1),
           num_threads(1),
-          num_eliminate_blocks(0),
           residual_reset_period(10),
           row_block_size(Dynamic),
           e_block_size(Dynamic),
@@ -100,15 +100,23 @@
     // If possible, how many threads can the solver use.
     int num_threads;
 
-    // Eliminate 0 to num_eliminate_blocks - 1 from the Normal
-    // equations to form a schur complement. Only used by the Schur
-    // complement based solver. The most common use for this parameter
-    // is in the case of structure from motion problems where we have
-    // camera blocks and point blocks. Then setting the
-    // num_eliminate_blocks to the number of points allows the solver
-    // to use the Schur complement trick. For more details see the
-    // description of this parameter in solver.h.
-    int num_eliminate_blocks;
+    // Hints about the order in which the parameter blocks should be
+    // eliminated by the linear solver.
+    //
+    // For example if elimination_groups is a vector of size k, then
+    // the linear solver is informed that it should eliminate the
+    // parameter blocks 0 - elimination_groups[0] - 1 first, and then
+    // elimination_groups[0] - elimination_groups[1] and so on. Within
+    // each elimination group, the linear solver is free to choose how
+    // the parameter blocks are ordered. Different linear solvers have
+    // differing requirements on elimination_groups.
+    //
+    // The most common use is for Schur type solvers, where there
+    // should be at least two elimination groups and the first
+    // elimination group must form an independent set in the normal
+    // equations. The first elimination group corresponds to the
+    // num_eliminate_blocks in the Schur type solvers.
+    vector<int> elimination_groups;
 
     // Iterative solvers, e.g. Preconditioned Conjugate Gradients
     // maintain a cheap estimate of the residual which may become
diff --git a/internal/ceres/schur_complement_solver.cc b/internal/ceres/schur_complement_solver.cc
index b9224d8..54f00dd 100644
--- a/internal/ceres/schur_complement_solver.cc
+++ b/internal/ceres/schur_complement_solver.cc
@@ -66,12 +66,12 @@
   if (eliminator_.get() == NULL) {
     InitStorage(A->block_structure());
     DetectStructure(*A->block_structure(),
-                    options_.num_eliminate_blocks,
+                    options_.elimination_groups[0],
                     &options_.row_block_size,
                     &options_.e_block_size,
                     &options_.f_block_size);
     eliminator_.reset(CHECK_NOTNULL(SchurEliminatorBase::Create(options_)));
-    eliminator_->Init(options_.num_eliminate_blocks, A->block_structure());
+    eliminator_->Init(options_.elimination_groups[0], A->block_structure());
   };
   const time_t init_time = time(NULL);
   fill(x, x + A->num_cols(), 0.0);
@@ -106,7 +106,7 @@
 // complement.
 void DenseSchurComplementSolver::InitStorage(
     const CompressedRowBlockStructure* bs) {
-  const int num_eliminate_blocks = options().num_eliminate_blocks;
+  const int num_eliminate_blocks = options().elimination_groups[0];
   const int num_col_blocks = bs->cols.size();
 
   vector<int> blocks(num_col_blocks - num_eliminate_blocks, 0);
@@ -178,7 +178,7 @@
 // initialize a BlockRandomAccessSparseMatrix object.
 void SparseSchurComplementSolver::InitStorage(
     const CompressedRowBlockStructure* bs) {
-  const int num_eliminate_blocks = options().num_eliminate_blocks;
+  const int num_eliminate_blocks = options().elimination_groups[0];
   const int num_col_blocks = bs->cols.size();
   const int num_row_blocks = bs->rows.size();
 
diff --git a/internal/ceres/schur_complement_solver.h b/internal/ceres/schur_complement_solver.h
index ea1b318..c382f95 100644
--- a/internal/ceres/schur_complement_solver.h
+++ b/internal/ceres/schur_complement_solver.h
@@ -97,13 +97,14 @@
 // The two solvers can be instantiated by calling
 // LinearSolver::CreateLinearSolver with LinearSolver::Options::type
 // set to DENSE_SCHUR and SPARSE_SCHUR
-// respectively. LinearSolver::Options::num_eliminate_blocks should be
+// respectively. LinearSolver::Options::elimination_groups[0] should be
 // at least 1.
 class SchurComplementSolver : public BlockSparseMatrixBaseSolver {
  public:
   explicit SchurComplementSolver(const LinearSolver::Options& options)
       : options_(options) {
-    CHECK_GT(options.num_eliminate_blocks, 0);
+    CHECK_GT(options.elimination_groups.size(), 1);
+    CHECK_GT(options.elimination_groups[0], 0);
   }
 
   // LinearSolver methods
diff --git a/internal/ceres/schur_complement_solver_test.cc b/internal/ceres/schur_complement_solver_test.cc
index 6c31c35..71c6cfd 100644
--- a/internal/ceres/schur_complement_solver_test.cc
+++ b/internal/ceres/schur_complement_solver_test.cc
@@ -98,7 +98,9 @@
       ceres::SparseLinearAlgebraLibraryType sparse_linear_algebra_library) {
     SetUpFromProblemId(problem_id);
     LinearSolver::Options options;
-    options.num_eliminate_blocks = num_eliminate_blocks;
+    options.elimination_groups.push_back(num_eliminate_blocks);
+    options.elimination_groups.push_back(
+        A->block_structure()->cols.size() - num_eliminate_blocks);
     options.type = linear_solver_type;
     options.sparse_linear_algebra_library = sparse_linear_algebra_library;
 
diff --git a/internal/ceres/schur_eliminator_test.cc b/internal/ceres/schur_eliminator_test.cc
index 0b55a14..56db598 100644
--- a/internal/ceres/schur_eliminator_test.cc
+++ b/internal/ceres/schur_eliminator_test.cc
@@ -149,10 +149,10 @@
     Vector rhs(schur_size);
 
     LinearSolver::Options options;
-    options.num_eliminate_blocks = num_eliminate_blocks;
+    options.elimination_groups.push_back(num_eliminate_blocks);
     if (use_static_structure) {
       DetectStructure(*bs,
-                      options.num_eliminate_blocks,
+                      num_eliminate_blocks,
                       &options.row_block_size,
                       &options.e_block_size,
                       &options.f_block_size);
diff --git a/internal/ceres/solver_impl.cc b/internal/ceres/solver_impl.cc
index 8f2f38b..4bedbe3 100644
--- a/internal/ceres/solver_impl.cc
+++ b/internal/ceres/solver_impl.cc
@@ -652,10 +652,19 @@
 #endif
 
   linear_solver_options.num_threads = options->num_linear_solver_threads;
-  linear_solver_options.num_eliminate_blocks =
-      options->num_eliminate_blocks;
+  if (options->num_eliminate_blocks > 0) {
+    linear_solver_options
+        .elimination_groups.push_back(options->num_eliminate_blocks);
+  }
 
-  if ((linear_solver_options.num_eliminate_blocks == 0) &&
+  // TODO(sameeragarwal): Fix this. Right now these are dummy values
+  // and violate the contract that elimination_groups should sum to
+  // the number of parameter blocks, but fixing this requires a bit
+  // more refactoring in solver_impl.cc, which is better done as we
+  // start deprecating the old API.
+  linear_solver_options.elimination_groups.push_back(1);
+
+  if (linear_solver_options.elimination_groups.size() == 1 &&
       IsSchurType(linear_solver_options.type)) {
 #if defined(CERES_NO_SUITESPARSE) && defined(CERES_NO_CXSPARSE)
     LOG(INFO) << "No elimination block remaining switching to DENSE_QR.";
diff --git a/internal/ceres/visibility_based_preconditioner.cc b/internal/ceres/visibility_based_preconditioner.cc
index 4caad03..ae26d91 100644
--- a/internal/ceres/visibility_based_preconditioner.cc
+++ b/internal/ceres/visibility_based_preconditioner.cc
@@ -70,12 +70,13 @@
       num_blocks_(0),
       num_clusters_(0),
       factor_(NULL) {
-  CHECK_GT(options_.num_eliminate_blocks, 0);
+  CHECK_GT(options_.elimination_groups.size(), 1);
+  CHECK_GT(options_.elimination_groups[0], 0);
   CHECK(options_.preconditioner_type == SCHUR_JACOBI ||
         options_.preconditioner_type == CLUSTER_JACOBI ||
         options_.preconditioner_type == CLUSTER_TRIDIAGONAL)
       << "Unknown preconditioner type: " << options_.preconditioner_type;
-  num_blocks_ = bs.cols.size() - options_.num_eliminate_blocks;
+  num_blocks_ = bs.cols.size() - options_.elimination_groups[0];
   CHECK_GT(num_blocks_, 0)
       << "Jacobian should have atleast 1 f_block for "
       << "visibility based preconditioning.";
@@ -83,7 +84,7 @@
   // Vector of camera block sizes
   block_size_.resize(num_blocks_);
   for (int i = 0; i < num_blocks_; ++i) {
-    block_size_[i] = bs.cols[i + options_.num_eliminate_blocks].size;
+    block_size_[i] = bs.cols[i + options_.elimination_groups[0]].size;
   }
 
   const time_t start_time = time(NULL);
@@ -155,7 +156,7 @@
 void VisibilityBasedPreconditioner::ComputeClusterJacobiSparsity(
     const CompressedRowBlockStructure& bs) {
   vector<set<int> > visibility;
-  ComputeVisibility(bs, options_.num_eliminate_blocks, &visibility);
+  ComputeVisibility(bs, options_.elimination_groups[0], &visibility);
   CHECK_EQ(num_blocks_, visibility.size());
   ClusterCameras(visibility);
   cluster_pairs_.clear();
@@ -173,7 +174,7 @@
 void VisibilityBasedPreconditioner::ComputeClusterTridiagonalSparsity(
     const CompressedRowBlockStructure& bs) {
   vector<set<int> > visibility;
-  ComputeVisibility(bs, options_.num_eliminate_blocks, &visibility);
+  ComputeVisibility(bs, options_.elimination_groups[0], &visibility);
   CHECK_EQ(num_blocks_, visibility.size());
   ClusterCameras(visibility);
 
@@ -253,7 +254,7 @@
 
   int r = 0;
   const int num_row_blocks = bs.rows.size();
-  const int num_eliminate_blocks = options_.num_eliminate_blocks;
+  const int num_eliminate_blocks = options_.elimination_groups[0];
 
   // Iterate over each row of the matrix. The block structure of the
   // matrix is assumed to be sorted in order of the e_blocks/point
@@ -331,16 +332,17 @@
 void VisibilityBasedPreconditioner::InitEliminator(
     const CompressedRowBlockStructure& bs) {
   LinearSolver::Options eliminator_options;
-  eliminator_options.num_eliminate_blocks = options_.num_eliminate_blocks;
+
+  eliminator_options.elimination_groups = options_.elimination_groups;
   eliminator_options.num_threads = options_.num_threads;
 
-  DetectStructure(bs, options_.num_eliminate_blocks,
+  DetectStructure(bs, options_.elimination_groups[0],
                   &eliminator_options.row_block_size,
                   &eliminator_options.e_block_size,
                   &eliminator_options.f_block_size);
 
   eliminator_.reset(SchurEliminatorBase::Create(eliminator_options));
-  eliminator_->Init(options_.num_eliminate_blocks, &bs);
+  eliminator_->Init(options_.elimination_groups[0], &bs);
 }
 
 // Update the values of the preconditioner matrix and factorize it.
diff --git a/internal/ceres/visibility_based_preconditioner_test.cc b/internal/ceres/visibility_based_preconditioner_test.cc
index 9973d69..8c5378d 100644
--- a/internal/ceres/visibility_based_preconditioner_test.cc
+++ b/internal/ceres/visibility_based_preconditioner_test.cc
@@ -80,7 +80,9 @@
     num_rows_ = A_->num_rows();
     num_eliminate_blocks_ = problem->num_eliminate_blocks;
     num_camera_blocks_ = num_col_blocks - num_eliminate_blocks_;
-    options_.num_eliminate_blocks = num_eliminate_blocks_;
+    options_.elimination_groups.push_back(num_eliminate_blocks_);
+    options_.elimination_groups.push_back(
+        A_->block_structure()->cols.size() - num_eliminate_blocks_);
 
     vector<int> blocks(num_col_blocks - num_eliminate_blocks_, 0);
     for (int i = num_eliminate_blocks_; i < num_col_blocks; ++i) {