Opened 8 years ago

Last modified 19 months ago

#18199 new enhancement

sage.geometry.polyhedron should have an lrs (lrslib) backend

Reported by: Matthias Köppe Owned by:
Priority: major Milestone: sage-wishlist
Component: geometry Keywords: polyhedron, lrs
Cc: Vincent Delecroix, Yuan Zhou, Nathann Cohen, gh-kliem Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #18127 Stopgaps:

Status badges

Description (last modified by Matthias Köppe)

Sage already has lrs as an optional package (#18127 renames it lrslib).

For higher-dimensional polytopes, computing vertices by lrs is often much faster than the implementations of the double description method in cddlib and ppl. lrslib 6.2 (#20886) has two modes of parallel computation, plrs and mplrs, see ​http://cgm.cs.mcgill.ca/~avis/C/lrs.html

lrs also has very fast and convenient code for removing redundant inequalities ("redund"). See https://groups.google.com/forum/#!topic/sage-support/WRpS5OgFMm8

Sage should have a backend_lrs.py to make use of the existing lrs package.

Links to older discussions regarding lrs: https://groups.google.com/forum/#!topic/sage-support/AZRzY7JyG_Y https://groups.google.com/forum/#!topic/sage-devel/oH6Jrjs-HUY

As has been said in these discussions, lrs also has a key benefit that it can generate the vertices as a stream, with very little memory use. This feature could be exposed using Python generators, using the Polyhedron methods Vrep_generator(), vertex_generator(), ray_generator(), line_generator().

See also: polymake (#20892) has an interface to at least some features of lrs

Change History (7)

comment:1 Changed 8 years ago by Matthias Köppe

Cc: Yuan Zhou added

comment:2 Changed 8 years ago by Matthias Köppe

Cc: Nathann Cohen added

comment:3 Changed 8 years ago by Matthias Köppe

Description: modified (diff)

comment:4 Changed 7 years ago by Matthias Köppe

Dependencies: #18127
Description: modified (diff)
Summary: sage.geometry.polyhedron should have an lrs backendsage.geometry.polyhedron should have an lrs (lrslib) backend

comment:5 Changed 7 years ago by Nathann Cohen

I may have time to work on this in a couple of weeks.

comment:6 Changed 6 years ago by Matthias Köppe

Description: modified (diff)

comment:7 Changed 19 months ago by Matthias Köppe

Cc: gh-kliem added
Note: See TracTickets for help on using tickets.