Metraipolis › archive › dc_622cf38ae50f
Accelerating Fourier--Motzkin elimination: redundancy removal and the choice of variable elimination order — arXiv:2609.07960
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.07960
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T14:29:55.518Z
- SHA-256 of the archived text
86a07338198c31381b15419bbda5745e144b644da05cf2887b65fd23790a6598- Stable URL of this page
https://metraipolis.com/documento/dc_622cf38ae50f
How to cite
Accelerating Fourier--Motzkin elimination: redundancy removal and the choice of variable elimination order — arXiv:2609.07960 — arXiv (en), https://arxiv.org/abs/2609.07960 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_622cf38ae50f (Metraipolis archive dc_622cf38ae50f, sha256 86a07338198c31381b15419bbda5745e144b644da05cf2887b65fd23790a6598)
BibTeX
@misc{dc622cf38ae50f,
title = {Accelerating Fourier--Motzkin elimination: redundancy removal and the choice of variable elimination order — arXiv:2609.07960},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.07960},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_622cf38ae50f; sha256 86a07338198c31381b15419bbda5745e144b644da05cf2887b65fd23790a6598},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.07960. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Fourier-Motzkin elimination computes an inequality description of the projection of a polyhedron onto a subset of its coordinates by eliminating one variable at a time. It is used in several areas of optimisation and computer science, and it is a standard way of obtaining the entropic constraints of a causal structure, where the marginalisation over the latent variables produces such a projection. Its limitation is the growth of the intermediate systems of inequalities, which can be doubly exponential in the number of eliminated variables even though the projection itself grows only as a single exponential. In practice the computational overload of the method therefore depends on two choices: how the redundant inequalities are removed after each step, and the order in which the variables are eliminated. We consider both. We first show, by an explicit example, that Imbert's redundancy test cannot be interleaved with redundancy removal by linear programming. We show that the two methods, however, can be combined soundly if the derivation records used by Imbert's test are re-initialised after every step at which linear programming is used. We then propose a rule for choosing the elimination order of the variables that gives a significant computational advantage, however, at the cost of increased resource usage. We demonstrate this advantage on some random polytopes, where the rule reduces the running time by factors of between 6 and 25 compared with the same elimination under a fixed order. For entropic descriptions of causal structures, with more than 250 inequalities and more than 100 variables to eliminate, our rule keeps the number of inequalities handled at each step one to two orders of magnitude lower than a fixed order. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in math.OC). Categorie arXiv: Computational Complexity (cs.CC) ; Combinatorics (math.CO); Numerical Analysis (math.NA); Optimization and Control (math.OC); Quantum Physics (quant-ph). Pagina del lavoro: https://arxiv.org/abs/2609.07960 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T14:09:21.760Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).