Opened 4 years ago
Closed 3 years ago
#22391 closed enhancement (fixed)
Always use PPL for facet normals of lattice polytopes
Reported by: | novoselt | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.1 |
Component: | geometry | Keywords: | sd91, sd90 |
Cc: | Merged in: | ||
Authors: | Andrey Novoseltsev | Reviewers: | Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | baf0a4a (Commits) | Commit: | baf0a4ad48cffc0a166b6db9ca9ba471f59c93eb |
Dependencies: | #22310 | Stopgaps: |
Description (last modified by )
A follow up to #22310. As promised there, this switch makes even full-dimensional polytopes faster, on the same example we now get
sage: timeit("LatticePolytope(lattice_polytope.cross_polytope(3).vertices()).facet_normals()") 625 loops, best of 3: 976 µs per loop
The reason is that dimension computation used to be quite complicated.
Next in the chain of lattice polytope improvements is #22524
Change History (17)
comment:1 Changed 4 years ago by
- Branch set to u/novoselt/PPL_for_normals
comment:2 Changed 4 years ago by
- Commit set to b4410f11f98d3bb09d4a2018187b6ff840ea7c87
- Status changed from new to needs_review
comment:3 Changed 4 years ago by
- Description modified (diff)
comment:4 Changed 3 years ago by
I successfully installed this patch and tried some variants on the example. Speed seems to work as advertised:
sage: sim = ReflexivePolytope(3,0) sage: timeit("sim.facet_normals()") 625 loops, best of 3: 576 ns per loop
comment:5 follow-up: ↓ 6 Changed 3 years ago by
Have you tried using normaliz? In dimension >= 10 it is likely to be faster. For that reason, it is good to have an optional keyword method=
or algorithm=
that simplifies speed comparisons.
comment:6 in reply to: ↑ 5 Changed 3 years ago by
Replying to vdelecroix:
Have you tried using normaliz? In dimension >= 10 it is likely to be faster. For that reason, it is good to have an optional keyword
method=
oralgorithm=
that simplifies speed comparisons.
The interest here is mostly in polytopes of dimensions 3-4-5, when the bottleneck is often the interface between programs. Also, the old code was quite convoluted for many reasons and adding different algorithms would be tricky. One of the goals of this and related tickets was to clean up the mess to indeed allow using different backends for certain operations.
comment:7 Changed 3 years ago by
- Keywords sd91 added
comment:8 Changed 3 years ago by
- Keywords sd90 added
comment:9 Changed 3 years ago by
I tried building again, and now this patch fails, with errors involving sage-ursula/src/build/cythonized/sage/
. My guess is that the transition from Sage 7.6 to the current development branch is too great. Do you mind updating the patch?
comment:10 Changed 3 years ago by
- Status changed from needs_review to needs_work
comment:11 Changed 3 years ago by
Can you please be more specific in how it fails? The branch merges cleanly and passes tests according to the patchbot.
comment:12 Changed 3 years ago by
It also works for me. I am guessing what happened is @ursula just used the branch, effectively downgrading her version of Sage to that of the branch, and ran sage -b
, which does not rebuild the necessary parts of Sage. In general, I always make sure to merge it ontop of (my version of) develop
to avoid regressing Sage (which will include long compilation time). If that is not what [@ursula] did, then try running make build
and then sage -t
.
comment:13 Changed 3 years ago by
- Branch changed from u/novoselt/PPL_for_normals to public/polytopes/PPL_for_normals-22391
- Commit changed from b4410f11f98d3bb09d4a2018187b6ff840ea7c87 to baf0a4ad48cffc0a166b6db9ca9ba471f59c93eb
- Milestone changed from sage-7.6 to sage-8.1
- Reviewers set to Travis Scrimshaw
- Status changed from needs_work to needs_review
comment:14 Changed 3 years ago by
- Status changed from needs_review to positive_review
Thank you!!!
Of course your changes look good - anything to get it in ;-) A small question however:
TypeError: the point M(1, 1) and - 2-d cone in 2-d lattice N have incompatible lattices! + 2-d cone in 2-d lattice N have incompatible lattices
Your new line apart from dropping the exclamation point due to exception formatting change also adds a space in front of the second part of the broken line. Is this also the style recommended somewhere? I can't recall ever reading it.
comment:15 Changed 3 years ago by
Not really, but I feel its gives better grouping that it is part of the error message and not some new line of output, similar to indenting function blocks.
comment:16 Changed 3 years ago by
Also, Python does not use sentence ending punctuation for any exceptions (or initial uppercase letters).
comment:17 Changed 3 years ago by
- Branch changed from public/polytopes/PPL_for_normals-22391 to baf0a4ad48cffc0a166b6db9ca9ba471f59c93eb
- Resolution set to fixed
- Status changed from positive_review to closed
Last 10 new commits:
Fix doctests - mostly due to different order of vertices
Use PPL for facet normals of full-dimensional polytopes
Update a lot of toric doctests for the new facet order
Merge tag '7.6.beta3' into PPL_for_normals
Always use PPL for LatticePolytope.facet_normals()
Update docstrings for facet normals and constants
Use PPL for LatticePolytope.dim()
Don't use embedding in LatticePolytope.distances()
Implement point containment test for LatticePolytope
Do not rely on distances for containment check