Accelerating Fourier–Motzkin elimination using bit pattern trees

DOI10.1080/10556788.2020.1712600zbMath1491.15025OpenAlexW2999184561WikidataQ126360176 ScholiaQ126360176MaRDI QIDQ5865333

A. V. Churkin, Sergei I. Bastrakov, Nikolai Yu. Zolotykh

Publication date: 13 June 2022

Published in: Optimization Methods and Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/10556788.2020.1712600

zbMATH Keywords

convex polyhedravariable eliminationsystem of linear inequalitiesFourier-Motzkin eliminationChernikov rulesbit pattern tree

Mathematics Subject Classification ID

(n)-dimensional polytopes (52B11) Linear inequalities of matrices (15A39) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Iterative numerical methods for linear systems (65F10) Linear equations (linear algebraic aspects) (15A06)

Related Items

How to find the convex hull of all integer points in a polyhedron?

Uses Software

• PORTA
• qskeleton
• GitHub
• efmtool
• addibit

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient constraint/generator removal from double description of polyhedra
• Applications of polyhedral computations to the analysis and verification of hardware and software systems
• How good are convex hull algorithms?
• Introduction to global optimization
• DC programming: overview.
• Two variations of graph test in double description method
• Fast method for verifying Chernikov rules in Fourier-Motzkin elimination
• New modification of the double description method for constructing the skeleton of a polyhedral cone
• Multidimensional binary search trees used for associative searching
• Exploring the Dynamic Buchberger Algorithm
• The convolution of finite systems of linear inequalities
• Geometry of cuts and metrics