Abstract: Non-linear system solvers are generally ineffective at solving systems of linear equations. Even though the underlying algorithm of the Triangularize command of the RegularChains library will end up performing a Bareiss-like algorithm on an input linear system over the integers, the implementation of Triangularize happily falls back to a true linear system solver when appropriate.
In this talk, we turn our attention to systems of linear inequalities. Not only solving such systems is central to polyhedral geometry but it is also a way to speed up the underlying algorithm of RegularChains commands like RealTriangularize. Our experimentation is done with the Basic Polynomial Algebra Subprograms (BPAS) library, where the algorithms of the RegularChains library are being integrated. We describe and compare various implementation strategies (including multi-threading) of state-of-the-art algorithms.
