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

1 Introduction

• For entropic causal-structure descriptions, eliminating latent-variable entropy coordinates projects the polyhedral constraints onto observed variables.The constraints combine Shannon inequalities with conditional-independence equalities implied by the graph.Source: §1 · pp. 1–2
• Doubly exponential intermediate growth makes redundancy removal and variable order central to Fourier–Motzkin elimination’s computational cost.The projection itself grows only as a single exponential, and the method’s practical cost depends on how redundancies are removed and which variables are eliminated first.Source: §1 · p. 2
• Interleaving Imbert’s test with LP redundancy removal can delete every inequality of a projection, but resetting derivation records after each LP step makes the combination sound.Imbert’s certificates use the complete generated set, which an LP step may alter; the paper’s block alternation is one valid pattern.Source: §1 · p. 2
• On random polytopes, the proposed elimination-order rule cuts wall-clock time by factors of 6–25; on large causal instances, it keeps per-step inequality counts one to two orders of magnitude lower than a fixed order.The causal instances each have more than 250 inequalities and more than 100 variables to eliminate; tentative eliminations are pruned and can run in parallel.Source: §1 · p. 2

2.1 The elimination step

• Eliminating a variable pairs every positive-coefficient upper bound with every negative-coefficient lower bound, while retaining inequalities that do not contain it.The output contains |I+||I−| + |I0| inequalities; if either bound set is empty, no pairs are formed.Source: §2.1 · p. 3

2.2 Correctness

• Each elimination step describes exactly the projection onto the remaining variables, and variables can be eliminated in any order.When both lower and upper bounds exist, feasibility requires the largest lower bound not to exceed the smallest upper bound; a value between them supplies the eliminated coordinate.Source: §2.2 · pp. 3–4

2.3 Two further examples

• In the three-dimensional example, eliminating z yields the shadow on the x–y plane, and the generated inequality 0 ≤ 4 is redundant.The example illustrates how pairing bounds creates projected inequalities, some of which can then be removed.Source: §2.3 · p. 5

2.4 Growth of the intermediate systems

• Unpruned systems can grow doubly exponentially, while the projection has a singly exponential description; after complete pruning, full-dimensional intermediate projections have at most O(m^(t+1)) inequalities after t steps.The projection bound follows from inequalities implied by non-negative combinations of at most d + 1 original inequalities; the pruned-system bound applies when the projection at that stage is full-dimensional.Source: §2.4 · pp. 5–6

3.1 The linear-programming test

• The LP test decides redundancy exactly by testing each inequality against the others with a linear programme, but each test involves the current system and can be expensive.Inequalities are tested sequentially, deleting each redundant inequality before testing the next.Source: §3.1 · p. 6

3.2 Imbert’s test

• Imbert’s test tracks each inequality’s root-inequality history and eliminated-variable records; its condition is sufficient, but not necessary, for redundancy and costs almost nothing to apply.Imbert introduced the derivation-based test.Source: §3.2 · p. 7

3.3 The two tests cannot be interleaved

• Carrying Imbert histories across LP deletions is unsound: a later inequality may be discarded after its certificate’s supporting inequality is removed, producing a system whose solution set strictly contains the projection.In the example, the interleaved procedure outputs the empty system.Source: §3.3 · pp. 7–8

3.4 A sound combination

• Sound alternation requires discarding Imbert’s records after every LP step and reinitialising them from the current system; a final LP pass yields a non-redundant description of the projection.The proof organizes steps between LP applications into epochs; experiments used an epoch length T = 3.Source: §3.4 · pp. 8–9
• On the Section 5 instances, Imbert’s test detects too few redundancies, allowing intermediate systems to grow until LP steps cost more than applying LP throughout.The paper reports that the alternating algorithm is faster on some instances, but not on those in Section 5.Source: §3.4 · p. 9

4.1 The greedy rule

• The usual greedy rule minimizes ν(s), the inequalities produced by eliminating s, but that count includes redundancies and can lead to many more non-redundant inequalities later.The authors report that this rule was much slower on large instances than random elimination orders.Source: §4.1 · pp. 9–10

4.2 Lookahead on the number of non-redundant inequalities

• One-step look-ahead tentatively eliminates each remaining variable, prunes the result with the LP test, and selects the variable leaving the smallest system.The tentative eliminations are independent and can run in parallel, one per core.Source: §4.2 · p. 10, §4.1 · p. 10

4.3 Cost

• Look-ahead costs up to r tentative eliminations per step, but smaller intermediate systems reduce later step costs; the rule is heuristic, not optimal.The authors note that deeper look-ahead or a different order may do better, and that the worst-case behavior remains possible.Source: §4.3 · p. 10

4.4 Reusing the order

• Once found, the order can be replayed with ordinary sequential elimination, separating the cost of finding it from the cost of using it.The authors also suggest trying an order found for one marginalisation again when the same causal structure is marginalised with different additional constraints.Source: §4.4 · pp. 10–11

• For N ≥4, the Shannon cone strictly contains the closure of entropy vectors, so constraints computed from it inherit this limitation, though the polyhedral computation itself is unaffected.Source: §5 · p. 11
• Graph-implied conditional-independence equalities are added to elemental Shannon inequalities, then every entropy coordinate involving a latent node is eliminated to obtain constraints on observed variables.The resulting system is satisfied by observed variables in every classical model of the causal structure.Source: §5 · p. 11
• With four observed and three latent nodes, the computation starts from 679 elemental inequalities and eliminates 112 of 127 coordinates, beyond straightforward Fourier–Motzkin implementation.Source: §5 · p. 11

6 Computational results

• The experiments compare the same elimination and LP test under Algorithm 2’s order versus a fixed order on four systems with over 250 initial non-redundant inequalities and over 100 variables to eliminate.The implementation uses one tentative elimination per worker.Source: §6.1 · p. 12, §6 · p. 12

6.2 Random polytopes

• For six random polytopes in 15 variables, from each of which 12 variables were eliminated, the look-ahead rule ran faster than the fixed order by factors of 6 to 25.Source: §6.2 · p. 12

6.1 Causal structures

• For four causal-structure systems, fixed-order redundant-inequality counts repeatedly reached one or two orders of magnitude above retained counts, while look-ahead counts stayed within a small factor.The fixed-order run reached about 10^4 redundant inequalities in the first instance.Source: §6.1 · p. 12, Figure 3 · p. 14

6.3 Remarks on the comparison

• Algorithm 2’s wall-clock comparison uses more resources than the single-core fixed-order run, and fewer available cores can reduce its gain.Finding the order distributes up to r tentative eliminations per step across available cores.Source: §6.3 · p. 15

7 Conclusion

• By factors of up to 25, the non-redundant-inequality order reduced running times and made entropic marginalisation with more than a hundred eliminated coordinates practicable.The one-step look-ahead runs in parallel; the resulting order can be replayed on a single core and reused in related computations.Source: §7 · p. 15
• Imbert’s and LP redundancy tests combine soundly only when derivation records are re-initialised after every step that uses the LP test.Interleaving them without re-initialisation is unsound because Imbert’s certificates refer to the complete generated set, which LP pruning changes.Source: §7 · p. 15
• The authors identify look-ahead cost, learning an ordering rule, optimal-order complexity, and stronger derivation-record tests as open questions.A depth-k look-ahead costs r^k tentative eliminations per step, and when that cost pays remains an open question.Source: §7 · p. 15

Additional Note

• Preliminary results had appeared in the author’s PhD thesis.Source: Additional Note · p. 15
• The article identifies itself as a preliminary version.Source: Additional Note · p. 15
• An updated version was expected to add some results and make the entire code publicly available.Source: Additional Note · p. 15

A Proofs

• After all variables are eliminated, the projection is either empty or the single point of R^0, depending on whether all numerical inequalities hold.Source: A Proofs · p. 16
• At each elimination stage, the feasible values of the next variable form an interval, so sequential choices within those intervals produce a point of the original polyhedron.Conversely, each point in the polyhedron yields values in the corresponding intervals at every stage.Source: A Proofs · p. 16
• Eliminating one variable from m inequalities yields at most max(m, floor(m²/4)) inequalities (m when all coefficients are zero); a stage with m_d inequalities yields at most max(m_d, m_d²/4) next.Source: A Proofs · p. 16
• An extreme ray of the projection cone has support of at most d + 1, bounding the number of such rays by subsets of the original inequalities of that size.The inequalities from these rays describe the projection, and a non-redundant description has no more inequalities than the extreme-ray description.Source: A Proofs · pp. 16–17