An existing algorithm [2] computes all valid facewise layer orders of a given crease pattern by (1) decomposing the problem into smaller independent subproblems in polynomial time, and (2) solving each subproblem in exponential time. In this paper, we improve on part (1) of this algorithm by using additional polynomial-time methods to reduce the size of independent subproblems, which can yield exponential improvement in the evaluation of part (2). We do this by first recognizing that, when layer orders are taken as elements in the two-element field \(\mathbb {F}_{2}\) , constraints that are linear can be solved efficiently. We can also extract linear constraints from the non-linear constraints to reduce problem size further. Lastly, we can use linear transformations to maximize separation into subproblems, thus minimizing subproblem size. Finally, experimental results show the practicality of our approach, demonstrating not only a substantial reduction in subproblem size leading into part (2), but also a reduction in computation time compared to part (1) of the original algorithm for many examples.