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: |
Description (last modified by )
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
Cc: | Yuan Zhou added |
---|
comment:2 Changed 8 years ago by
Cc: | Nathann Cohen added |
---|
comment:3 Changed 8 years ago by
Description: | modified (diff) |
---|
comment:4 Changed 7 years ago by
Dependencies: | → #18127 |
---|---|
Description: | modified (diff) |
Summary: | sage.geometry.polyhedron should have an lrs backend → sage.geometry.polyhedron should have an lrs (lrslib) backend |
comment:5 Changed 7 years ago by
comment:6 Changed 6 years ago by
Description: | modified (diff) |
---|
comment:7 Changed 19 months ago by
Cc: | gh-kliem added |
---|
I may have time to work on this in a couple of weeks.