diff --git a/mlir/lib/Dialect/SparseTensor/Transforms/Sparsification.cpp b/mlir/lib/Dialect/SparseTensor/Transforms/Sparsification.cpp
--- a/mlir/lib/Dialect/SparseTensor/Transforms/Sparsification.cpp
+++ b/mlir/lib/Dialect/SparseTensor/Transforms/Sparsification.cpp
@@ -114,10 +114,17 @@
 /// that adheres to the given topological sort.
 static AffineMap permute(MLIRContext *context, AffineMap m,
                          std::vector<unsigned> &topSort) {
-  unsigned sz = topSort.size();
-  SmallVector<unsigned, 4> perm(sz);
-  for (unsigned i = 0; i < sz; i++)
-    perm[i] = m.getPermutedPosition(topSort[i]);
+  // Construct the inverse of `m`; to avoid the asymptotic complexity
+  // of calling `m.getPermutedPosition` repeatedly.
+  unsigned invSz = m.getNumResults();
+  SmallVector<unsigned, 4> inv(invSz);
+  for (unsigned i = 0; i < invSz; i++)
+    inv[i] = m.getDimPosition(i);
+  // Construct the permutation.
+  unsigned permSz = topSort.size();
+  SmallVector<unsigned, 4> perm(permSz);
+  for (unsigned i = 0; i < permSz; i++)
+    perm[i] = inv[topSort[i]];
   return AffineMap::getPermutationMap(perm, context);
 }