⚛️ quantum physics

Accelerating Fourier--Motzkin elimination: redundancy removal and the choice of variable elimination order

This paper addresses the computational inefficiency of Fourier-Motzkin elimination by proposing a method to safely combine Imbert's redundancy test with linear programming and introducing a variable elimination ordering rule that significantly reduces processing time and inequality counts, particularly for entropic causal structures.

Original authors: Shashaank Khanna

Published 2026-09-09

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Shashaank Khanna

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of mathematics and computer science, there is a persistent challenge involving shapes defined by straight lines and flat surfaces, known as polyhedra. Imagine a complex, multi-sided object floating in space, defined by a set of rules or inequalities that tell you which points are inside and which are outside. Scientists and engineers often need to understand what this object looks like if they ignore certain dimensions, effectively flattening it onto a lower-dimensional surface. This process, called projection, is crucial for solving problems in fields ranging from designing computer chips to understanding how information flows through networks. However, when mathematicians try to calculate these flattened shapes by removing variables one by one, a notorious problem arises: the number of rules describing the shape can explode. A method developed decades ago, known as Fourier–Motzkin elimination, is the standard tool for this job, but it often generates a massive, unmanageable avalanche of redundant rules, making the calculation impossible for anything but the simplest shapes.

Shashaank Khanna, a researcher working between the University of York and Aix-Marseille University, has tackled this explosion of complexity by refining how the method works. The core issue is that the standard approach creates far more inequalities than are actually needed, many of which are duplicates or unnecessary variations of others. To fix this, the method must constantly check for and remove these extra rules. Khanna investigated two common ways to do this checking: one that is fast but sometimes misses rules, and another that is slow but perfectly accurate. He discovered that a popular strategy of mixing these two methods—using the fast check first and then the slow one—actually breaks the math, causing the system to delete essential rules and produce a wrong answer. By proving this failure with a specific example, he showed that the two methods cannot simply be interleaved. Instead, he demonstrated that they can be combined safely, but only if the computer resets its memory of how each rule was created every time the slow, accurate check is performed. This ensures that the fast check is always working with a complete and correct set of information.

Beyond fixing the checking process, Khanna addressed the order in which variables are removed, a choice that dramatically affects how long the calculation takes. The traditional approach is greedy, meaning it always picks the variable that seems to create the fewest new rules in the very next step. However, Khanna found that this short-sighted strategy often leads to a much larger mess later on. He proposed a new rule that looks one step ahead: instead of just counting the immediate output, the computer tentatively tries removing every remaining variable, cleans up the resulting mess, and then picks the one that leaves the smallest number of rules. Because these trial runs are independent, they can be performed simultaneously on multiple computer processors. This approach, while requiring more computing power upfront, drastically reduces the total time needed. In tests on random shapes, this new ordering rule sped up the process by factors of six to twenty-five compared to the fixed order.

The impact is even more significant for a specific type of problem involving causal structures, which are diagrams used to map out how different events influence one another, often in the study of quantum physics or complex networks. When researchers try to determine the possible correlations between observed variables in these structures, they must eliminate dozens of hidden variables, leading to systems with hundreds of inequalities. In these difficult cases, Khanna's method kept the number of rules the computer had to handle at each step one to two orders of magnitude lower than the standard fixed order. This reduction turned calculations that were previously too expensive to attempt into manageable tasks. The paper concludes that while finding the perfect order might be impossible, this practical, one-step-ahead strategy makes the entropic analysis of complex causal structures feasible, opening the door to studying systems with more than a hundred variables that were previously out of reach.

Technical Summary: Accelerating Fourier–Motzkin Elimination

Problem Statement
Fourier–Motzkin (FM) elimination is a standard algorithm for computing the projection of a polyhedron onto a subset of its coordinates by eliminating variables one at a time. While the method is fundamental to integer programming, robust optimization, compiler optimization, and the derivation of entropic constraints for causal structures, it suffers from a severe computational bottleneck. Eliminating a single variable from a system of $m$ inequalities can generate up to $m^2/4$ new inequalities. Consequently, $d$ successive eliminations can produce a doubly exponential number of intermediate inequalities, even though the final projection admits a description of only singly exponential size.

In practice, the feasibility of FM elimination depends on two critical choices:

Redundancy Removal: How to efficiently identify and discard inequalities implied by others after each elimination step.
Elimination Order: The sequence in which variables are eliminated, which significantly impacts the growth of the intermediate system.

The paper addresses the inefficiency of standard implementations, particularly in the context of entropic descriptions of causal structures, where systems often involve hundreds of inequalities and over 100 variables to eliminate.

Methodology and Key Contributions

1. Sound Combination of Redundancy Tests
The paper investigates the combination of two common redundancy tests:

The Linear Programming (LP) Test: Solves an LP for each inequality to determine redundancy exactly. It is accurate but computationally expensive.
Imbert's Test: Inspects the derivation history of an inequality (the set of root inequalities used to form it) to detect redundancy. It is computationally cheap but incomplete (it detects only a subset of redundancies).
Proposition 2 (The Interleaving Failure): The author demonstrates via a counterexample that simply interleaving Imbert's test with the LP test (applying Imbert's test, then the LP test, and carrying forward derivation records) is unsound. Imbert's test certifies redundancy based on the presence of specific inequalities in the current set. If the LP test removes an inequality that serves as a "certificate" for the redundancy of a subsequent inequality, Imbert's test may fail to flag that subsequent inequality, or conversely, the removal of a certificate can lead to the erroneous deletion of necessary inequalities. In the provided example, this flawed combination results in the deletion of the entire projection.
Theorem 2 (Sound Combination): The paper proposes a sound protocol for combining these tests. The derivation records used by Imbert's test must be re-initialized after every step where the LP test is applied. In this protocol, the system resulting from the LP test becomes the new "root" for subsequent steps. This ensures that Imbert's test only flags redundancies relative to the current, verified set of inequalities. The author implements this via an "epoch" strategy (Algorithm 1), where Imbert's test runs for $T$ steps, followed by one step of LP testing and re-initialization.

2. Heuristic for Elimination Order
The paper critiques the standard "greedy" rule, which selects the variable that minimizes the number of inequalities produced in the immediate next step ( $\nu(s)$ ). The author argues that this metric is a poor proxy for total cost because it includes redundant inequalities and ignores the impact on future steps. On their instances, the greedy rule often performed worse than a random elimination order.

Look-Ahead Rule (Algorithm 2): The author proposes a one-step look-ahead heuristic. For the current system, the algorithm tentatively eliminates every remaining variable, applies the LP test to prune the resulting systems, and counts the number of non-redundant inequalities remaining ( $\hat{\nu}(s)$ ). The variable that leaves the fewest non-redundant inequalities is selected for elimination.
Parallelization: Since these tentative eliminations are independent, they are executed in parallel across available CPU cores.
Reusability: Once the optimal order $\sigma$ is found, the projection can be recomputed using a single sequential pass with no search overhead. This allows the cost of finding the order to be separated from the cost of using it, facilitating reuse in related computations (e.g., marginalizing the same causal structure with different constraints).

Results

The author evaluated their methods on two types of instances: random polytopes and systems derived from causal structures (entropic constraints).

Random Polytopes: On six random polytopes with 15 variables (12 to be eliminated), the look-ahead rule reduced wall-clock running times by factors between 6 and 25 compared to a fixed elimination order.
Causal Structures: For instances with over 250 initial inequalities and more than 100 variables to eliminate, the look-ahead rule kept the number of non-redundant inequalities handled at each step one to two orders of magnitude lower than a fixed order. This reduction prevented the intermediate systems from exploding, making the computation of entropic constraints for these complex structures tractable.
Redundancy Counts: Under fixed orders, the number of redundant inequalities frequently spiked to $10^4$ , requiring extensive LP processing. Under the look-ahead order, the number of non-redundant inequalities decreased almost monotonically, and redundant counts remained low.

Significance and Claims

The paper claims that the efficiency of FM elimination is more dependent on the elimination order than on the specific redundancy test used, provided the tests are combined soundly.

Practical Impact: The proposed look-ahead rule makes the entropic marginalization of causal structures with over 100 eliminated coordinates practicable, a task that was previously often intractable due to computational overload.
Theoretical Contribution: The paper clarifies the conditions under which fast heuristic tests (Imbert's) and exact tests (LP) can be safely combined, correcting a common assumption that they can be freely interleaved.
Modesty: The author acknowledges that their look-ahead rule is a heuristic (one-step depth) and does not guarantee optimality. They note that the worst-case doubly exponential growth described in Proposition 1 is not excluded, and that deeper look-aheads or different ordering strategies might perform better on other instances. They also note that the wall-clock speedup relies on parallel resources; the total processor time is higher, though the quality of the resulting order justifies the cost.

In conclusion, the work provides a robust framework for accelerating FM elimination by correcting the combination of redundancy tests and introducing a parallelizable, look-ahead ordering strategy that significantly reduces the computational burden in high-dimensional projection problems.

More like this