Opened 5 years ago
Last modified 5 years ago
#19365 needs_info defect
Bug in lattice_polytope.positive_integer_relations
Reported by: | tmonteil | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.10 |
Component: | geometry | Keywords: | |
Cc: | vdelecroix, chapoton, mkoeppe, rws | Merged in: | |
Authors: | Vincent Delecroix | Reviewers: | Andrey Novoseltsev, Thierry Monteil |
Report Upstream: | N/A | Work issues: | |
Branch: | public/19365 (Commits, GitHub, GitLab) | Commit: | 651684a41026bee07a49be83b238b059e72693bc |
Dependencies: | Stopgaps: |
Description (last modified by )
Reported on this ask question:
sage: vertices = [(1,1,-1,-1,-1),(-1,-1,1,1,-1),(1,-1,-1,-1,1),(-1,1,1,1,1),(1,-1,1,-1,-1)] sage: p = LatticePolytope(vertices) sage: lattice_polytope.positive_integer_relations(p.vertices().column_matrix()) TypeError: unable to make sense of Maxima expression '"Problemnotfeasible!"' in Sage
Note that there is a non-negative nontrivial integer relation:
sage: p.vertices().column_matrix().right_kernel() Free module of degree 5 and rank 1 over Integer Ring Echelon basis matrix: [1 1 1 1 0]
Change History (13)
comment:1 Changed 5 years ago by
comment:2 Changed 5 years ago by
- Cc vdelecroix added
- Description modified (diff)
- Milestone changed from sage-6.9 to sage-6.10
... changed a missing )
in the description...
comment:3 Changed 5 years ago by
- Branch set to public/19365
- Commit set to 6f9c08689431553677b73a19f1319add1470af5c
- Status changed from new to needs_review
comment:4 follow-up: ↓ 5 Changed 5 years ago by
- if x.str() == r'?Problem\not\feasible\!': - raise ValueError("cannot find required relations")
Why wasn't this triggered in the old code?
I suggest you run some timing on this code too, and see what it reports when there isn't a relation, etc. I wonder why this non-generic code was used?
comment:5 in reply to: ↑ 4 Changed 5 years ago by
Replying to kcrisman:
- if x.str() == r'?Problem\not\feasible\!': - raise ValueError("cannot find required relations")Why wasn't this triggered in the old code?
I suggest you run some timing on this code too, and see what it reports when there isn't a relation, etc. I wonder why this non-generic code was used?
Timing against what? The old code crashes on most examples...
comment:6 follow-up: ↓ 8 Changed 5 years ago by
- Status changed from needs_review to needs_work
The new version obviously has a different return type.
There is also some helper Maxima method that can be removed if it is not used anymore.
Timings against the old code are indeed irrelevant - that was just something that I managed to get into a working code back when I was young ;-)
comment:7 Changed 5 years ago by
- Commit changed from 6f9c08689431553677b73a19f1319add1470af5c to 651684a41026bee07a49be83b238b059e72693bc
comment:8 in reply to: ↑ 6 Changed 5 years ago by
- Status changed from needs_work to needs_review
Replying to novoselt:
The new version obviously has a different return type.
Right. Fixed.
There is also some helper Maxima method that can be removed if it is not used anymore.
Right. Deprecated.
comment:9 Changed 5 years ago by
- Reviewers set to Andrey Novoseltsev
- Status changed from needs_review to positive_review
comment:10 Changed 5 years ago by
- Reviewers changed from Andrey Novoseltsev to Andrey Novoseltsev, Thierry Monteil
- Status changed from positive_review to needs_work
The example provided in the doc is:
sage: points = [(1,1,-1,-1,-1), (-1,-1,1,1,-1), (1,-1,-1,-1,1), ....: (-1,1,1,1,1), (1,-1,1,-1,-1)] sage: positive_integer_relations(points) [(1, 0, 0, 1, 0)]
Could you explain how (1,1,-1,-1,-1) + (-1,1,1,1,1) == 0
?
The result should be [(1, 1, 1, 1, 0)]
, see the ask question for the expected answer.
Given a list of tuples, is it more natural to interpret it as a list of vectors, or as a list of rows of a matrix whose columns are vectors ? We might argue that the doc says that the points "are given as columns of a matrix". But when the doc writes points = [(1,1,-1,-1,-1), (-1,-1,1,1,-1), (1,-1,-1,-1,1), (-1,1,1,1,1), (1,-1,1,-1,-1)]
, should the user consider this as a natural way to define the vectors [(1, -1, 1, -1, 1), (1, -1, -1, 1, -1), (-1, 1, -1, 1, 1), (-1, 1, -1, 1, -1), (-1, -1, 1, 1, -1)]
?
It could be even worse if the user explicitely writes points = [vector([1,1,-1,-1,-1]), vector([-1,-1,1,1,-1]), vector([1,-1,-1,-1,1]), vector([-1,1,1,1,1]), vector([1,-1,1,-1,-1])]
so that no ambiguity appears on her side, but the first line of the code M = matrix(points)
, silently forgot all this information.
comment:11 Changed 5 years ago by
Good point. The old code would break right away on anything but the matrix and it looked at first as a good idea to have matrix constructor built in, but apparently it is not. I agree that both input and output formats of this function are not the best possible ones, but that's what it has been for ages (like since 2006/7), so let's keep it. Those who want to use this function have to do the conversion or write a new one and deprecate this one.
Interestingly, it is not used anywhere in Sage (I thought that somewhere in toric code it may be handy) but I am pretty sure I used it at some point in my worksheets.
comment:13 Changed 5 years ago by
- Cc rws added
- Status changed from needs_work to needs_info
After #20766, the example in the description gives:
sage: vertices = [(1,1,-1,-1,-1),(-1,-1,1,1,-1),(1,-1,-1,-1,1),(-1,1,1,1,1),(1,-1,1,-1,-1)] sage: p = LatticePolytope(vertices) sage: lattice_polytope.positive_integer_relations(p.vertices().column_matrix()) MIPSolverException: PPL : There is no feasible solution
See also #19367, which however I think is, if not orthogonal, at least not spanned by this question.