LRSLIB(1)

📦 version 0.71b, in debian bookworm, ubuntu jammy, ubuntu noble

✨ LRSLIB — the manual, but make it cute ✨

okay bestie, sit down, hydrate, because this is lrslib — it lives in the lrslib 7.1 manual, and it's lowkey one of the most iconic toolkits in polyhedral computation. no cap. 💖

🌸 NAME 🌸

lrslib: the whole vibe is converting between representations of convex polyhedra, removing redundant inequalities, doing convex hull computation, solving linear programs in exact precision, and computing Nash-equibria in 2-person games. she does it all, fr fr. 👑

✨ SYNOPSIS ✨

the way you summon her:

lrs [input-file] [output-file]
redund [input-file] [output-file]
mpirun -np num-proc mplrs input-file [output-file] [options]
lrsnash [options] [input-file]
hvref/xvref [input-file]

periodt. that's the whole lineup. 🫶

💅 DESCRIPTION 💅

so here's the tea. a polyhedron can be described two ways: as 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 stuffed with programs that manipulate these representations, and here's the iconic part — all computations are done in exact arithmetic. no floating-point drama. no rounding girlies. 💯

lrs converts an H-representation of a polyhedron to its V-representation and vice versa — which are known, respectively, as the vertex enumeration and facet enumeration problems (peep Example (1) below, she's right there). and she's multi-talented: lrs can also solve a linear program, remove linearities from a system, and extract a subset of columns. main character energy only. ✨

redund removes redundant inequalities in an input H-representation and outputs the ones that survived. if you hand her a V-representation instead, she outputs all extreme points and extreme rays. and the bestie behavior? both outputs can be piped directly into lrs. we love a seamless handoff. redund is actually a link to lrs which performs these functions via the redund and redund_list options. iykyk. 🔗

mplrs is Skip Jordan's parallel wrapper for lrs/redund. parallelize, slay, repeat. 🔥

lrsnash is Terje Lensberg's application of lrs for finding Nash-equilibria in 2-person games. game theory said let me cook. 🎮

hvref/xvref produce a cross reference list between H- and V-representations. little cross-reference icons, doing their thing. 🦋

🌈 ARITHMETIC 🌈

okay this part is genuinely iconic so pay attention. from version 7.1, lrs/redund/mplrs use hybrid arithmetic with overflow checking — she starts in 64bit integers, moves to 128bit (if available), and then lands on GMP. it's giving glow-up pipeline. ⭐

the overflow checking is conservative to improve performance, like:

  • 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

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, but make it exact. 🏃♀️💨

various arithmetic versions are available and can be built from the makefile:

📓 NOTES 📓

User's guide for lrslib

read it, bestie, it's the lore. 📖

🎀 AUTHOR 🎀

David Avis <avis at cs dot mcgill dot ca >

💜 SEE ALSO 💜

and that's the whole page!! this one's from July 2009, refreshed on 2020.06.10, shipping as part of lrslib 7.1. go compute something convex, you got this. 💖✨🎀🦋🌸💅🫶

📦 where this page comes from