lrslib(5)

🌸 lrslib — the whole vibe 💖

ok so bestie, welcome to lrslib, version 7.3 — the manual page, the lore, the moment. This is the page that tells you what the whole lrslib family does, and honestly? It's giving "small library, absolutely enormous brain". 💅

Here's the elevator pitch, in the original's own words: convert between representations of convex polyhedra, remove redundant inequalities, find minimum representations, convex hull computation, solve linear programs in exact precision, compute Nash-equilibria in 2-person games. Like. Slay. 👑

---

✨ NAME ✨

lrslib — it converts between representations of convex polyhedra, it removes redundant inequalities, it finds minimum representations, it does convex hull computation, it solves linear programs in exact precision, and it computes Nash-equilibria in 2-person games. That's the whole résumé. Main character energy fr fr. 🌈

---

🎀 SYNOPSIS 🎀

Here's every single invocation, copied character for character because we do not play with the commands:

lrs [input-file] [output-file]

redund [input-file] [output-file]

minrep [input-file] [output-file]

fel [input-file] [output-file]

mpirun -np num-proc mplrs input-file [output-file] [options]

lrsnash [options] [input-file]

hvref/xvref [input-file]

polyv [input-file]

---

🦋 DESCRIPTION 🦋

ok so here's the tea. 🫖

A polyhedron can be described by a list of inequalities (that's the H-representation) or as a list of its vertices and extreme rays (that's the V-representation). lrslib is a C library containing programs to manipulate these representations. And the part that makes me feral? All computations are done in exact arithmetic. No float nonsense. None. 💀✨

lrs(1) converts an H-representation of a polyhedron to its V-representation and vice versa — known respectively as the vertex enumeration and facet enumeration problems (peep Example (1) below 👀). lrs can also be used to solve a linear program, remove linearities from a system, and extract a subset of columns. Multi-talented icon. 💅

redund(1) removes redundant inequalities in an input H-representation and outputs the remaining inequalities. For a V-representation input it outputs all extreme points and extreme rays. Both outputs can be piped directly into lrs. And plot twist: redund is a link to lrs which performs these functions via the redund and redund_list options. Sneaky. Obsessed. 🙈

minrep(1) performs the same functions as redund(1) but in addition searches for hidden linearities in the input. These are made explicit in the output, which is a minimum representation of the polyhedron. It said "let me find the secret ones too" and honestly? Ate. 🔥

fel(1) projects an input H-representation onto a given set of variables using Fourier-Motzkin elimination. For a V-representation it extracts the specified columns. The output is non-redundant and can be can be piped directly into lrs. (yes, the "can be can be" is the original's, and I'm keeping it, no notes 💖). fel is a link to lrs which performs these functions via the eliminate and project options.

mplrs(1) is Skip Jordan's parallel wrapper for lrs/redund/minrep/fel. Parallel. Wrapper. We love a collaborative queen. 🧚

lrsnash(1) is Terje Lensberg's application of lrs for finding Nash-equilibria in 2-person games. Game theory bestie. 🎮

hvref(1) and xvref(1) produce a cross reference list between H- and V-representations. Very "here's who knows who". 🫶

polyv(1) is Skip Jordan's utility to create logical formulas for checking equivalence between H- and V- representations, or determining whether a given inequality is redundant after eliminating variables, without eliminating the variables. Yes. The math version of doing it without doing it. Iconic. ⭐

---

🧮 ARITHMETIC 🧮

ok so this is the section where things get numerically spicy. 🌶️

lrsarith(5) — from version 7.1, lrs/redund/mplrs use hybrid arithmetic with overflow checking, starting in 64bit integers, moving to 128bit (if available) and then GMP. It's a whole glow-up pipeline for numbers.

Overflow checking is conservative to improve performance: eg. with 64 bit arithmetic, a*b triggers overflow if either a or b is at least 2^31, and a+b triggers an overflow if either a or b is at least 2^62. Yes bestie, that's aggressive and yes, it's on purpose. 😤

Typically problems that can be solved in 64bits run 3-4 times faster than with GMP and inputs solvable in 128bits run twice as fast as GMP. Speed. 💨

Various arithmetic versions are available and can be built from the makefile. Build her up. 🛠️✨

---

📝 NOTES 📝

User's guide for lrslib

• http://cgm.cs.mcgill.ca/~avis/C/lrslib/USERGUIDE.html

go read it, it's the extended lore. 📚

---

👑 AUTHOR 👑

David Avis <avis at cs dot mcgill dot ca >

---

🔗 SEE ALSO 🔗

• lrs (1), redund(1), minrep(1), mplrs(1), fel(1), lrsnash(1), hvref(1), xvref(1), polyv(1), lrsarith(5)

---

and that's the whole page bestie!! 💖 this is lrslib version 7.3, dated January 2024 / 2024.01.31. exact arithmetic, exact vibes, no cap. periodt. 🎀✨🦋