Sage: Ticket #8986: Add support for convex rational polyhedral cones
https://trac.sagemath.org/ticket/8986
<p>
This patch is a part of the following series adding support for cones/fans and toric varieties to Sage:
</p>
<p>
Prerequisites:
</p>
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/8675" title="defect: Remove AmbientSpace._constructor and fix consequences (closed: fixed)">#8675</a> - Remove <code>AmbientSpace._constructor</code> and fix consequences
</p>
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/8682" title="defect: Improve AlgebraicScheme_subscheme.__init__ and AmbientSpace._validate (closed: fixed)">#8682</a> - Improve <code>AlgebraicScheme_subscheme.__init__</code> and <code>AmbientSpace._validate</code>
</p>
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/8694" title="defect: Improve schemes printing and LaTeXing (closed: fixed)">#8694</a> - Improve schemes printing and LaTeXing
</p>
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/8934" title="defect: Trivial bug in computing faces of non-full-dimensional lattice polytopes (closed: fixed)">#8934</a> - Trivial bug in computing faces of non-full-dimensional lattice polytopes
</p>
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/8936" title="enhancement: Expose facet inequalities for lattice polytopes (closed: fixed)">#8936</a> - Expose facet inequalities for lattice polytopes
</p>
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/8941" title="enhancement: _latex_ and origin for lattice polytopes (closed: fixed)">#8941</a> - <code>_latex_</code> and <code>origin</code> for lattice polytopes
</p>
<p>
Main patches adding new modules:
</p>
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/9062" title="enhancement: Add support for toric lattices (closed: fixed)">#9062</a> - Add support for toric lattices
</p>
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/8986" title="enhancement: Add support for convex rational polyhedral cones (closed: fixed)">#8986</a> - Add support for convex rational polyhedral cones
</p>
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/8987" title="enhancement: Add support for rational polyhedral fans (closed: fixed)">#8987</a> - Add support for rational polyhedral fans
</p>
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/8988" title="enhancement: Add support for toric varieties (closed: fixed)">#8988</a> - Add support for toric varieties
</p>
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/8989" title="enhancement: Add support for Fano toric varieties (closed: fixed)">#8989</a> - Add support for Fano toric varieties
</p>
<p>
Everything was tested on sage.math using sage-4.4.2.rc0.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/8986
Trac 1.1.6novoseltTue, 18 May 2010 09:31:39 GMTstatus, description changed; author, milestone set
https://trac.sagemath.org/ticket/8986#comment:1
https://trac.sagemath.org/ticket/8986#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
set to <em>Andrey Novoseltsev</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/8986?action=diff&version=1">diff</a>)
</li>
<li><strong>milestone</strong>
set to <em>sage-4.4.2</em>
</li>
</ul>
TicketnovoseltFri, 21 May 2010 03:57:16 GMTstatus changed
https://trac.sagemath.org/ticket/8986#comment:2
https://trac.sagemath.org/ticket/8986#comment:2
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
I will make some adjustments to this module following discussion here:
<a class="ext-link" href="http://groups.google.com/group/sage-devel/browse_thread/thread/17743e17d67838ae"><span class="icon"></span>http://groups.google.com/group/sage-devel/browse_thread/thread/17743e17d67838ae</a>
</p>
TicketnovoseltFri, 28 May 2010 21:39:29 GMTdescription changed; cc set
https://trac.sagemath.org/ticket/8986#comment:3
https://trac.sagemath.org/ticket/8986#comment:3
<ul>
<li><strong>cc</strong>
<em>vbraun</em> added
</li>
<li><strong>description</strong>
modified (<a href="/ticket/8986?action=diff&version=3">diff</a>)
</li>
</ul>
<p>
New version of the patch depends on <a class="closed ticket" href="https://trac.sagemath.org/ticket/9062" title="enhancement: Add support for toric lattices (closed: fixed)">#9062</a> and actually makes some improvements to toric lattices. Switch of caching technique to allow efficient extension of class hierarchy is still pending.
</p>
TicketnovoseltSat, 29 May 2010 19:24:48 GMTstatus changed
https://trac.sagemath.org/ticket/8986#comment:4
https://trac.sagemath.org/ticket/8986#comment:4
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketvbraunFri, 04 Jun 2010 13:16:02 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/8986#comment:5
https://trac.sagemath.org/ticket/8986#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>reviewer</strong>
set to <em>Volker Braun</em>
</li>
</ul>
<p>
Looks good! I have two comments:
</p>
<h2 id="Strictsubcone">Strict subcone</h2>
<p>
I find <code>ConvexRationalPolyhedralCone.strict_subcone()</code> confusing: It does return a quotient cone, not a subcone. Maybe we can call it <code>strict_quotient()</code>?
</p>
<h2 id="pointincone">point in cone</h2>
<p>
<code>IntegralRayCollection.__contains__(ray)</code> tests whether <code>ray</code> is a reference to one of the generating rays. But this is then inherited by <code>ConvexRationalPolyhedralCone</code> Naively, I would have expected that it tests whether something is in the cone:
</p>
<pre class="wiki">sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
sage: N = octant.lattice()
sage: n = N(1,1,1)
sage: n.set_immutable()
sage: n in octant
False
sage: (1,0,0) in octant
False
</pre><p>
Similarly there are issues with the immutablity as shown in the doctest.
</p>
<p>
I would suggest the following:
</p>
<p>
1) get rid of <code>IntegralRayCollection.__contains__(ray)</code>. If you need to test membership, its easy enough to search <code>self.rays()</code> or <code>self.rays_set()</code>:
</p>
<pre class="wiki">sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
sage: N = octant.lattice()
sage: N(1,0,0) in octant.rays() # no problem with immutability
True
sage: n = N(1,0,0)
sage: n.set_immutable()
sage: n in octant.ray_set() # slightly more efficient and its clear why n must be immutable
True
</pre><p>
2) tighten the rules for comparison of N/M-lattice objects:
</p>
<pre class="wiki">sage: M = N.dual()
sage: M(1,0,0) == N(1,0,0) # this should raise an error
False
sage: (1,0,0) == N(1,0,0) # should probably return true
False
sage: M(1,0,0) == (1,0,0) # should probably return true as well
False
sage: (1,0,0) == (1,0,0) # works as expected
True
</pre><p>
This would fix the following:
</p>
<pre class="wiki">sage: (1,0,0) in octant.rays() # this should return true
False
sage: M(1,0,0) in octant.rays() # this should definitely raise an error
False
</pre><p>
3) add methods <code>contains(n)</code> to <code>ConvexRationalPolyhedralCone</code> to test whether a N-lattice point is contained in the cone, e.g. (untested)
</p>
<pre class="wiki"> def contains(self, *Nlist):
"""
Returns whether the cone contains the N-lattice points ``*Nlist``.
EXAMPLES::
sage: cone = Cone([[1,0],[0,1]])
sage: n = cone.ray(0) + cone.ray(1)
sage: cone.contains(n)
True
sage: cone.contains( N(1,1), N(-1,1) )
False
sage: cone.contains([ N(1,1), N(-1,1) ])
False
"""
pts = flatten(Nlist)
assert all(n in self._lattice() for n in pts), 'The points '+str(pts)+' must be in the N-lattice.'
return all( self.polyhedron().contains(n) for n in pts )
</pre><p>
4) <code>ConvexRationalPolyhedralCone.__contains__()</code> just calls <code>contains()</code>. This is syntactic sugar, but <code>__</code> methods alone don't show up in the documentation.
</p>
TicketnovoseltFri, 04 Jun 2010 16:09:57 GMT
https://trac.sagemath.org/ticket/8986#comment:6
https://trac.sagemath.org/ticket/8986#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8986#comment:5" title="Comment 5">vbraun</a>:
</p>
<blockquote class="citation">
<p>
I find <code>ConvexRationalPolyhedralCone.strict_subcone()</code> confusing: It does return a quotient cone, not a subcone. Maybe we can call it <code>strict_quotient()</code>?
</p>
</blockquote>
<p>
Agreed. I just had to construct this object for equivalence checks and didn't really know how to call it.
</p>
<blockquote class="citation">
<p>
1) get rid of <code>IntegralRayCollection.__contains__(ray)</code>. If you need to test membership, its easy enough to search <code>self.rays()</code> or <code>self.rays_set()</code>:
</p>
</blockquote>
<p>
Agreed.
</p>
<blockquote class="citation">
<p>
2) tighten the rules for comparison of N/M-lattice objects:
</p>
</blockquote>
<pre class="wiki">sage: M(1,0,0) == N(1,0,0) # this should raise an error
False
</pre><p>
Disagreed. Maybe it is silly to ask if an apple is equal to a car, but there is nothing criminal in it. I think that in general in Python you can compare any two objects and sort lists containing arbitrary objects. So I think that <code>False</code> is the correct answer in this case.
</p>
<blockquote class="citation">
</blockquote>
<pre class="wiki">sage: (1,0,0) == N(1,0,0) # should probably return true
False
sage: M(1,0,0) == (1,0,0) # should probably return true as well
False
</pre><p>
I kind of don't like that we have here a==b and c==a, but b!=c... Do you really want to have it in? It may be actually non-trivial to implement. I already had to tweak the coercion system so that sometimes it allows "non-toric-lattice" objects to be involved and sometimes it does not. In particular I had to make sure that elements of toric lattices are NOT coerced into ZZ<sup>n.
</sup></p>
<p>
So if you insist, I will try to make it work, but I cannot guarantee that I will be successful and personally I think that we should not change it, as long as this behaviour is clearly documented. (Probably it is not, but that's something which definitely can be fixed ;-))
</p>
<blockquote class="citation">
</blockquote>
<pre class="wiki">sage: M(1,0,0) in octant.rays() # this should definitely raise an error
False
</pre><p>
Again, I don't think that there should be any errors raised by comparison operations. <code>False</code> is an accurate answer to this question - and octant in the N-lattice does not contain any points of the M-lattice.
</p>
<blockquote class="citation">
<p>
3) add methods <code>contains(n)</code> to <code>ConvexRationalPolyhedralCone</code> to test whether a N-lattice point is contained in the cone, e.g. (untested)
</p>
</blockquote>
<p>
Agreed. It was on my list of things to do in the future, might as well do it now.
</p>
<blockquote class="citation">
<p>
4) <code>ConvexRationalPolyhedralCone.__contains__()</code> just calls <code>contains()</code>. This is syntactic sugar, but <code>__</code> methods alone don't show up in the documentation.
</p>
</blockquote>
<p>
Very good point!!! I knew that they don't show up, but didn't think about just making a "common method" alias.
</p>
<p>
Please comment on the points of disagreement and I will try to fix the issues in a couple of days. Thanks for a careful review!
</p>
TicketvbraunFri, 04 Jun 2010 16:31:40 GMT
https://trac.sagemath.org/ticket/8986#comment:7
https://trac.sagemath.org/ticket/8986#comment:7
<p>
I see your point that e.g. python sets will use the comparison and its probably a bad idea to tinker too much with it. So I agree with you that we should keep it the way it is and make the <code>contains()</code> method throw an error if the argument is not in the N-lattice. Some warning in the toric lattices documentation might be good that '==' always compares objects and says nothing about equivalence.
</p>
TicketnovoseltFri, 04 Jun 2010 17:41:46 GMT
https://trac.sagemath.org/ticket/8986#comment:8
https://trac.sagemath.org/ticket/8986#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8986#comment:7" title="Comment 7">vbraun</a>:
</p>
<blockquote class="citation">
<p>
I see your point that e.g. python sets will use the comparison and its probably a bad idea to tinker too much with it. So I agree with you that we should keep it the way it is and make the <code>contains()</code> method throw an error if the argument is not in the N-lattice. Some warning in the toric lattices documentation might be good that '==' always compares objects and says nothing about equivalence.
</p>
</blockquote>
<p>
So you want different behaviour for <code>contains</code> and <code>__contains__</code>? I just checked the following to see how things are in Sage now:
</p>
<pre class="wiki">sage: g = Graph()
sage: R = QQ["x,y"]
sage: g in R
False
</pre><p>
To be consistent, I think that <code>x in cone</code> should accept any argument and return <code>False</code> if <code>x</code> is an object of any type that definitely cannot be in the cone. And I think it would be confusing to have different behaviour for <code>contains</code> and <code>__contains__</code>. In what kind of situations do you think it would be desirable to have an exception raised instead? Current framework already does not allow mixing elements of wrong toric lattices or even easily converting elements of one to another, so it does not seem to me that the current version will lead to any wrong results.
</p>
TicketvbraunSat, 05 Jun 2010 11:12:20 GMT
https://trac.sagemath.org/ticket/8986#comment:9
https://trac.sagemath.org/ticket/8986#comment:9
<p>
No, I definitely want <code>__contains__()</code> and <code>contains()</code> to be the same. I'm only concerned that a novice user of the package will write
</p>
<pre class="wiki">sage: cone = Cone([[1,0],[0,1]])
sage: (1,1) in cone
False
</pre><p>
and get the (in his eyes) wrong answer without any clue as to what went wrong. If that would be my first interaction with the package, I'd be convinced that its computations cannot be trusted :-). Once you understand the code it is of course obvious why it returned False. The difference to your example, where a ring is not in a graph, is that here it depends on the details of the coercion (or not) between <code>ZZ^n</code> and <code>ToricLattice</code> that will not be familiar to all users.
</p>
<p>
One could narrow it down to only raise an exception on tests that run into this problem, like a test along the lines of
</p>
<pre class="wiki">if (!is_ToricLatticeElement(n)):
try:
[ ZZ(i) for i in n ]
raise ValueError, 'You probably want '+str(n)+' to be a N-lattice element.'
except:
return False # whatever n is, its not in the cone
</pre><p>
Let me know what you think!
</p>
TicketnovoseltSat, 05 Jun 2010 17:22:40 GMT
https://trac.sagemath.org/ticket/8986#comment:10
https://trac.sagemath.org/ticket/8986#comment:10
<p>
Well, I am still against exceptions, however I have just checked this:
</p>
<pre class="wiki">sage: F5 = GF(5)
sage: F7 = GF(7)
sage: 2 == F5(2)
True
sage: 2 == F7(2)
True
sage: F5(2) == F7(2)
False
</pre><p>
So, since I like so much to invoke consistency reasons in my arguments, I retract my first reaction on 2) in your proposal. I think I will try to allow coercion of <code>ZZ^n</code> to any toric lattice of dimension <code>n</code>, but not backwards. Explicit casting from lattices to <code>ZZ^n</code> will be possible, but to go between two different toric lattices one will have to create a homomorphism or use double casting, i.e. I think that M(N(1,1)) should throw a <code>TypeError</code>. So the code from your comment will work like this:
</p>
<pre class="wiki">sage: M = N.dual()
sage: M(1,0,0) == N(1,0,0) # this should raise an error - NO, RETURN FALSE
False
sage: (1,0,0) == N(1,0,0) # should probably return true - YES
False
sage: M(1,0,0) == (1,0,0) # should probably return true as well - YES
False
sage: (1,0,0) == (1,0,0) # works as expected - YES
True
sage: (1,0,0) in octant.rays() # this should return true - YES
False
sage: M(1,0,0) in octant.rays() # this should definitely raise an error - NO, RETURN FALSE
False
</pre><p>
I think this way it's OK to be sloppy about lattices, especially if one just does not care about them. If one uses the very last command, then clearly (s)he is aware of toric lattices and should be able to interpret this <code>False</code> correctly.
</p>
TicketvbraunSat, 05 Jun 2010 19:46:59 GMT
https://trac.sagemath.org/ticket/8986#comment:11
https://trac.sagemath.org/ticket/8986#comment:11
<p>
Actually, your last example <code>M(1,0,0) in octant.rays()</code> is precisely where I would like some feedback to the user that he is probably doing something wrong. Confusing the polytope with its dual is precisely what a beginner in toric geometry might do, and I think it would be very helpful if there were more feedback than a successful completion of the command.
</p>
<p>
How about we don't raise exceptions and keep your "mathematical" sense of membership but use the python <code>warnings</code> module to print a warning. By default the warning would only occur the first time when the user aims for his foot...
</p>
TicketnovoseltSat, 05 Jun 2010 19:54:57 GMT
https://trac.sagemath.org/ticket/8986#comment:12
https://trac.sagemath.org/ticket/8986#comment:12
<p>
OK! Will work on this.
</p>
TicketnovoseltSun, 06 Jun 2010 03:00:08 GMT
https://trac.sagemath.org/ticket/8986#comment:13
https://trac.sagemath.org/ticket/8986#comment:13
<p>
I have realized that <code>(1,0,0)</code> in the examples above is not a vector, but just a tuple. Then I have done the following test:
</p>
<pre class="wiki">sage: (1,0,0) == vector([1,0,0])
False
sage: vector([1,0,0]) == (1,0,0)
False
sage: vector([1,0,0]) + (1,0,0)
TypeError: unsupported operand parent(s) for '+': 'Ambient free module of rank 3 over the principal ideal domain Integer Ring' and '<type 'tuple'>'
sage: (1,0,0) + (1,0,0)
(1, 0, 0, 1, 0, 0)
</pre><p>
It is not really an issue of the coercion, it is just not possible to always use tuples as a replacement for lattice points. We made it, however, very easy to work with them:
</p>
<pre class="wiki">sage: N(1,0,0) + N(1,0,0)
N(2, 0, 0)
</pre><p>
So I think that equality tests will remain as they are now. Operations involving "pure" vectors may need more work, perhaps:
</p>
<pre class="wiki">sage: N(1,0,0) + vector((1,0,0))
N(2, 0, 0)
sage: vector((1,0,0)) + N(1,0,0)
(2, 0, 0)
</pre><p>
although this does not bother me too much and I would suggest leaving this as is until we see where and how it can cause problems. (Making the second line return <code>N(2,0,0)</code> can be a bit tricky.)
</p>
<p>
Will post a new patch once I figure out how to work with warnings (never used them before).
</p>
TicketnovoseltSun, 06 Jun 2010 04:43:36 GMTattachment set
https://trac.sagemath.org/ticket/8986
https://trac.sagemath.org/ticket/8986
<ul>
<li><strong>attachment</strong>
set to <em>trac_8986_add_support_for_convex_rational_polyhedral_cones.patch</em>
</li>
</ul>
<p>
Reviewer's comments taken into account.
</p>
TicketnovoseltSun, 06 Jun 2010 05:21:11 GMTstatus changed
https://trac.sagemath.org/ticket/8986#comment:14
https://trac.sagemath.org/ticket/8986#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
OK, I think I have addressed all the points in the original review except 2) which is pretty much impossible to realize completely (originally I was thinking of (1,1,1) as vectors, but they are just tuples, see the above comment for vector behaviour in this situation). I have added a general warning about tuples in the main <code>ToricLattice</code> documentation.
</p>
<p>
I added <code>__contains__</code> to <code>ToricLattice</code>, since I discovered that the inherited implementation is not suitable.
</p>
<p>
I added <code>__contains__</code>, <code>_contains</code>, and <code>contains</code> to cones. The real job is done in <code>_contains</code>, two others call it. The reason for the third function is an attempt to make warnings show where the actual potential mistake was, which requires the same calling depth. Unfortunately, in my tests it worked as I wanted only if it was triggered by some library code, in the notebook for created functions and attached files it just shows <code>main</code>. But that may change and maybe the terminal behaves differently. Now <code>cone.contains(stuff)</code> will try its best to return <code>True</code> by interpreting <code>stuff</code> as a point in the ambient space of <code>cone</code>, i.e. in <code>cone.lattice().base_extend(RR)</code>. However, it will catch points from foreign lattices first and return <code>False</code> with a warning, visible the first time for each location.
</p>
<p>
That's how reviewer's code works with the new version of the patch:
</p>
<pre class="wiki">sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
sage: N = octant.lattice()
sage: n = N(1,1,1)
sage: n.set_immutable()
sage: n in octant # True was desired
True
sage: (1,0,0) in octant # True was desired
True
sage: N(1,0,0) in octant.rays() # was and should be True
True
sage: n = N(1,0,0)
sage: n.set_immutable()
sage: n in octant.ray_set() # was and should be True
True
sage: M = N.dual()
sage: M(1,0,0) == N(1,0,0) # Error was desired
False
sage: (1,0,0) == N(1,0,0) # True was desired, but difficult to get
False
sage: M(1,0,0) == (1,0,0) # True was desired, but difficult to get
False
sage: (1,0,0) == (1,0,0) # works as expected
True
sage: (1,0,0) in octant.rays() # True was desired, but difficult to get
False
sage: M(1,0,0) in octant.rays() # Error was desired
False
sage: cone = Cone([[1,0],[0,1]])
sage: (1,1) in cone # Was False
True
sage: M = cone.lattice().dual()
sage: M(1,1) in cone # Now gives warning on the first attempt
__main__:1: UserWarning: you have checked if a cone contains a point from another lattice, this is always False!
False
</pre><p>
I suppose two lines marked "Error was desired" can also give a warning the first time they are invoked, if we implement a custom <code>__eq__</code> in addition to <code>__cmp__</code> for <code>ToricLatticeElement</code>. Should this be done?
</p>
TicketvbraunSun, 06 Jun 2010 13:25:51 GMT
https://trac.sagemath.org/ticket/8986#comment:15
https://trac.sagemath.org/ticket/8986#comment:15
<p>
I think the == comparison is not so critical, as it is the default python behavior to compare actual objects. Should not cause any confusion as long as one is somewhat familiar with Sage. So I'm happy with that.
</p>
<p>
The <code>Polyhedron</code> class already has a <code>contains()</code> method that tests for inclusion (I wrote it with toric varieties in mind :-). <code>ConvexRationalPolyhedralCone._contains()</code> could have called that, saving a few lines of duplicate code. Not that big a deal, though. I'm happy to give it a positive review either way. Let me know what you think.
</p>
<p>
</p>
TicketnovoseltSun, 06 Jun 2010 16:10:52 GMT
https://trac.sagemath.org/ticket/8986#comment:16
https://trac.sagemath.org/ticket/8986#comment:16
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8986#comment:15" title="Comment 15">vbraun</a>:
</p>
<blockquote class="citation">
<p>
The <code>Polyhedron</code> class already has a <code>contains()</code> method that tests for inclusion (I wrote it with toric varieties in mind :-). <code>ConvexRationalPolyhedralCone._contains()</code> could have called that, saving a few lines of duplicate code. Not that big a deal, though. I'm happy to give it a positive review either way. Let me know what you think.
</p>
</blockquote>
<p>
So does <code>LatticePolytope</code> class, which was written with the same goal in mind ;-) As I have already complained somewhere, any calls to underlying <code>LatticePolytope</code> or <code>Polyhedron</code> objects can trigger system calls to other programs, which in many cases gives a huge overhead (compared to the rest of involved computations). So in this case I preferred to use a "native" way for cones to check if a point is inside. Of course, computing facet normals the first time will eventually call PALP to get facet normals of the corresponding polytope, but:<br />
1) there is a way to compute facet normals for a lot of polytopes (e.g. corresponding to all cones of a fan) with a single call to PALP, in which case the overhead is negligible;<br />
2) if a cone was pickled and unpickled, it definitely does not have polytope objects anymore, but it may still have facet normals, if they were computed before pickling;<br />
3) we may eventually write our own initial computation of facet normals at least in some cases, for example, for complete fans.
</p>
<p>
Regarding 1) - the first call to <code>ReflexivePolytopes(3)</code> takes currently 5-10s. It reads a text file with vertices and then precomputes a bunch of stuff to save time later. Computing all this stuff without using group calls to PALP was taking about 15 minutes. I don't see any reasons why such calls cannot be done for Polyhedra, but I don't know how easy that would be. Do you think there is any point trying to implement it?
</p>
<p>
To summarize: please give a positive review to the present version ;-)
</p>
TicketvbraunSun, 06 Jun 2010 18:15:56 GMTstatus changed
https://trac.sagemath.org/ticket/8986#comment:17
https://trac.sagemath.org/ticket/8986#comment:17
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Oh I didn't notice that you use <a class="missing wiki">LatticePolytope?</a>/PALP to compute the facet normals. That limits the dimension a bit, but good enough for now. I think cython-izing <code>polyhedra</code> to call libcdd directly would be easy enough, but thats for the future :-)
</p>
<p>
So to summarize, I think the patch is ready for for inclusion. It also applies cleanly on top of Sage 4.4.3. Positive review.
</p>
TicketnovoseltSun, 06 Jun 2010 19:27:09 GMT
https://trac.sagemath.org/ticket/8986#comment:18
https://trac.sagemath.org/ticket/8986#comment:18
<p>
Thank you!
</p>
<p>
Dimension limit is exactly why I started using <code>Polyhedra</code>, however I didn't quite like the timings. For example, this is what I get on geom.math with toric patches applied:
</p>
<pre class="wiki">sage: %time
sage: o = lattice_polytope.octahedron(6) # no PALP calls
CPU time: 0.00 s, Wall time: 0.00 s
sage: %time
sage: len(o.faces()) # PALP call to get incidences (no Hasse diagram)
6
CPU time: 0.07 s, Wall time: 0.13 s
sage: %time
sage: f = FaceFan(o)
CPU time: 0.03 s, Wall time: 0.06 s
sage: %time
sage: f.cone_lattice() # some calls to PALP
Finite poset containing 730 elements
CPU time: 0.18 s, Wall time: 0.32 s
sage: %time
sage: p = Polyhedron(vertices=o.vertices().columns()) # almost all time is in cdd
CPU time: 0.02 s, Wall time: 3.84 s
sage: %time
sage: p.face_lattice() # all time in Sage
Finite poset containing 730 elements
CPU time: 8.36 s, Wall time: 8.36 s
</pre><p>
Given the construction time of <code>p</code>, I am not even sure if calling cdd as a library will help a lot, but you mentioned that you also had some other library in mind. So while I am definitely interested in going to dimensions higher than 6, so far PALP seems to be the way to go. One possible modification for the future is to use PALP when possible and switch to alternatives when it does not work.
</p>
TicketnovoseltThu, 01 Jul 2010 16:22:04 GMTattachment set
https://trac.sagemath.org/ticket/8986
https://trac.sagemath.org/ticket/8986
<ul>
<li><strong>attachment</strong>
set to <em>trac_8986_cmp_fix.patch</em>
</li>
</ul>
TicketnovoseltThu, 01 Jul 2010 16:24:44 GMTstatus changed
https://trac.sagemath.org/ticket/8986#comment:19
https://trac.sagemath.org/ticket/8986#comment:19
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
I made a systematic mistake in doctests of <code>__cmp__</code> methods of all patches, discovered in <a class="closed ticket" href="https://trac.sagemath.org/ticket/9062" title="enhancement: Add support for toric lattices (closed: fixed)">#9062</a>. So now I am posting these one-line patches to fix them, please review!
</p>
TicketnovoseltThu, 01 Jul 2010 16:25:20 GMTcc, status changed
https://trac.sagemath.org/ticket/8986#comment:20
https://trac.sagemath.org/ticket/8986#comment:20
<ul>
<li><strong>cc</strong>
<em>davidloeffler</em> added
</li>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketvbraunThu, 01 Jul 2010 16:31:05 GMT
https://trac.sagemath.org/ticket/8986#comment:21
https://trac.sagemath.org/ticket/8986#comment:21
<p>
I noticed that, too. I haven't gotten around to fix it because I ran into this strange doctest failure in Sage-4.5alpha1 that worked beautifully in sage-4.4.4:
</p>
<pre class="wiki">File "/home/vbraun/opt/sage-4.5.alpha1/devel/sage-main/sage/geometry/cone.py", line 1535:
sage: c.faces()
Exception raised:
Traceback (most recent call last):
File "/home/vbraun/opt/sage-4.5.alpha1/local/bin/ncadoctest.py", line 1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/home/vbraun/opt/sage-4.5.alpha1/local/bin/sagedoctest.py", line 38, in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
File "/home/vbraun/opt/sage-4.5.alpha1/local/bin/ncadoctest.py", line 1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_33[10]>", line 1, in <module>
c.faces()###line 1535:
sage: c.faces()
File "/home/vbraun/opt/sage-4.5.alpha1/local/lib/python/site-packages/sage/geometry/cone.py", line 1554, in faces
for level in self.face_lattice().level_sets())
File "/home/vbraun/opt/sage-4.5.alpha1/local/lib/python/site-packages/sage/geometry/cone.py", line 1433, in face_lattice
ray_to_facets, facet_to_rays, ConeFace)
File "/home/vbraun/opt/sage-4.5.alpha1/local/lib/python/site-packages/sage/geometry/cone.py", line 2259, in hasse_diagram_from_incidences
for atom, coatoms in enumerate(atom_to_coatoms))
File "/home/vbraun/opt/sage-4.5.alpha1/local/lib/python/site-packages/sage/geometry/cone.py", line 2259, in <genexpr>
for atom, coatoms in enumerate(atom_to_coatoms))
KeyError: (frozenset([0]), frozenset([0]))
</pre><p>
Andrey, since its your code maybe you'll understand what is going on.
</p>
TicketnovoseltThu, 01 Jul 2010 16:36:04 GMTstatus changed
https://trac.sagemath.org/ticket/8986#comment:22
https://trac.sagemath.org/ticket/8986#comment:22
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Thanks for finding it, will work on!
</p>
TicketnovoseltThu, 01 Jul 2010 22:01:07 GMT
https://trac.sagemath.org/ticket/8986#comment:23
https://trac.sagemath.org/ticket/8986#comment:23
<p>
I have finally built a copy of 4.5.alpha1 on geom.math and cannot reproduce this error, all tests passed. The error message above does not make any sense to me - how can a <code>KeyError</code> appear during enumeration of a list? Do you get the same error consistently every time? What configuration are you testing it on? Did you build 4.5.alpha1 from scratch? I will also run tests on my own computer, but it will take a few more hours to finish the build.
</p>
TicketnovoseltFri, 02 Jul 2010 02:08:44 GMTstatus changed
https://trac.sagemath.org/ticket/8986#comment:24
https://trac.sagemath.org/ticket/8986#comment:24
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
I installed 4.5.alpha1 on my machine (although it is not extremely different from geom: quite fresh Ubuntu 10.4 64bit running in a <a class="missing wiki">VirtualBox?</a>) and still don't have any issues...
</p>
<p>
By the way, I just noticed that the lines shown in the above exception do not exist in the patch on this ticket. Cone module is severely altered by the next ticket, in particular the Hasse diagram function was changed. Could it be that you accidentally skipped rebuilding sage after popping/pushing some patches of the sequence? That would probably lead to errors, although I would expect much more than one and with more sensible messages...
</p>
<p>
Anyway, I claim that this ticket works fine for me on top of 4.5.alpha1, as well as others in the sequence.
</p>
TicketdavidloefflerFri, 02 Jul 2010 09:01:39 GMT
https://trac.sagemath.org/ticket/8986#comment:25
https://trac.sagemath.org/ticket/8986#comment:25
<p>
Just a remark: it works fine for me as well, 4.5.alpha1 on 64-bit SuSE Linux, as long as I have <a class="closed ticket" href="https://trac.sagemath.org/ticket/9062" title="enhancement: Add support for toric lattices (closed: fixed)">#9062</a> installed. Volker: could you tell us exactly what setup you were using when it didn't work for you, and what patches you did/did not have installed at the time?
</p>
TicketvbraunFri, 02 Jul 2010 10:01:24 GMTstatus changed
https://trac.sagemath.org/ticket/8986#comment:26
https://trac.sagemath.org/ticket/8986#comment:26
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
I rebuilt 4.5.alpha1 overnight and it works now. Not sure what caused the problem. I can't rule out that I forgot to rebuild and/or some patch. Another possible problem was that I originally used parallel make for sage which died half way through because of a missing file. Since restarting the compilation succeeded, I had assumed that everything built OK.
</p>
<p>
In any case, the toric code works so I'll set it back to <code>positive_review</code>.
</p>
TicketmpatelTue, 20 Jul 2010 08:47:04 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/8986#comment:27
https://trac.sagemath.org/ticket/8986#comment:27
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.5.2.alpha0</em>
</li>
</ul>
TicketmpatelSat, 24 Jul 2010 02:58:54 GMT
https://trac.sagemath.org/ticket/8986#comment:28
https://trac.sagemath.org/ticket/8986#comment:28
<p>
One or more of <a class="closed ticket" href="https://trac.sagemath.org/ticket/8986" title="enhancement: Add support for convex rational polyhedral cones (closed: fixed)">#8986</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/8987" title="enhancement: Add support for rational polyhedral fans (closed: fixed)">#8987</a>, and <a class="closed ticket" href="https://trac.sagemath.org/ticket/9062" title="enhancement: Add support for toric lattices (closed: fixed)">#9062</a> <em>may</em> cause the doctest failures listed at <a class="closed ticket" href="https://trac.sagemath.org/ticket/9590" title="defect: Doctest failures in cone.py and toric_lattice_element.pyx on 32-bit Linux (closed: fixed)">#9590</a>.
</p>
Ticket