Opened 8 years ago

Closed 8 years ago

#16180 closed enhancement (fixed)

Subdivide fans using PPL

Reported by: novoselt Owned by:
Priority: major Milestone: sage-6.3
Component: geometry Keywords: toric
Cc: vbraun, jkeitel Merged in:
Authors: Andrey Novoseltsev Reviewers: Jan Keitel
Report Upstream: N/A Work issues:
Branch: 59c8c94 (Commits, GitHub, GitLab) Commit: 59c8c9475223e98aeb604a79d22427605f20b5fb
Dependencies: Stopgaps:

Status badges

Description (last modified by novoselt)

Current Fan.subdivide() method cannot deal with fans generated by non-full-dimensional cones since it relies on PALP. In addition it is overly complicated. So let's use PPL cones for subdivision, since our toric cones already rely on them a lot. Speed-wise new method seems to work 2-3 times faster than the old one, but main advantages are brevity of code and absence of artificial limitations.

I've also cleaned up related code a bit and deprecated Cone.lattice_polytope whose primary purpose was to use PALP for subdivision.

Change History (11)

comment:1 Changed 8 years ago by novoselt

  • Branch set to u/novoselt/subdivide_fans_using_ppl

comment:2 Changed 8 years ago by novoselt

  • Authors set to Andrey Novoseltsev
  • Cc vbraun added
  • Commit set to dc35d9d1dd0d10678213344f59e38481f934c338
  • Component changed from PLEASE CHANGE to geometry
  • Description modified (diff)
  • Keywords toric added
  • Status changed from new to needs_review
  • Type changed from PLEASE CHANGE to enhancement

New commits:

a692959Use PPL for fan subdivision.
17cb30bFix doctests due to different facet ordering in PPL and PALP.
dc35d9dDeprecate Cone.lattice_polytope() and drop cache for Cone.polyhedron().

comment:3 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:4 Changed 8 years ago by novoselt

  • Cc jkeitel added

comment:5 Changed 8 years ago by jkeitel

  • Branch changed from u/novoselt/subdivide_fans_using_ppl to u/jkeitel/subdivide_fans_using_ppl
  • Commit changed from dc35d9d1dd0d10678213344f59e38481f934c338 to f7f0dd54706d14d4d909715903581604ad133dc9
  • Reviewers set to Jan Keitel

Hi Andrey,

I've looked at the patch at it looks good - it's always nice to get rid of LatticePolytope. ;-) One quick question: Is there any reason you're not caching the polyhedron() method of Cone?

New commits:

bd66bcdMerge branch 'develop' into u/novoselt/subdivide_fans_using_ppl
f7f0dd5Ticket 16180: Two minor formatting changes.

comment:6 Changed 8 years ago by novoselt

Well don't hate it please, there is nothing wrong with the class, only with its backend which was designed for a quite specific purpose ;-) And of course bounded polytopes are not the best way to represent unbounded cones.

As for caching - why should we cache polyhedron()? It is a complicated data structure which will take memory and can cause issues in pickling (this was the main reason for the change here, if I recall correctly - I was trying to simplify pickling code), it is not used extensively in internal computations, and I don't think there are many reasons for users to construct them. On the other hand it definitely can be handy if you want to do some generic operations like shifting the cone from the origin.

Were there any conflicts during merge? (I never liked what is shown when you click on "merge commit.")

comment:7 Changed 8 years ago by git

  • Commit changed from f7f0dd54706d14d4d909715903581604ad133dc9 to 59c8c9475223e98aeb604a79d22427605f20b5fb

Branch pushed to git repo; I updated commit sha1. New commits:

59c8c94Change two Trac occurences to proper syntax.

comment:8 Changed 8 years ago by jkeitel

No, the merge went through cleanly. I just merged the development branch in to see whether it is working with the current version. Otherwise I wouldn't have noticed the doctest warning because of the line number, since that has only recently been included (#16626). And I then based the new commit on the merged branch since it saved a lot of time when building Sage. I hope Volker will forgive the extra commit.

I just noticed that polytope() only seems to get used in the doctests - so not caching does make perfect sense. If you're happy, then you can set this to positive review.

comment:9 Changed 8 years ago by vbraun

  • Status changed from needs_review to positive_review

Thanks, lgtm!

comment:10 Changed 8 years ago by novoselt

Thank you! Looking at your changes made me realize that toric stuff existed for 4 years already! Life is fast...

comment:11 Changed 8 years ago by vbraun

  • Branch changed from u/jkeitel/subdivide_fans_using_ppl to 59c8c9475223e98aeb604a79d22427605f20b5fb
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.