Sage: Ticket #18183: Implement two matroid polytopes
https://trac.sagemath.org/ticket/18183
<p>
To a matroid one can associate two polytopes.
</p>
<ul><li>one with bases as vertices
</li><li>one with indep. sets as vertices
</li></ul><p>
The former is a facet of the latter.
</p>
<p>
Here is an implementation.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/18183
Trac 1.1.6chapotonTue, 14 Apr 2015 08:17:24 GMTstatus changed; commit, branch set
https://trac.sagemath.org/ticket/18183#comment:1
https://trac.sagemath.org/ticket/18183#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>641d76c39dfa5619c1b8759c52d855be2a917088</em>
</li>
<li><strong>branch</strong>
set to <em>u/chapoton/18183</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=641d76c39dfa5619c1b8759c52d855be2a917088"><span class="icon"></span>641d76c</a></td><td><code>trac #18XXX two matroid polytopes</code>
</td></tr></table>
TicketvdelecroixTue, 14 Apr 2015 09:28:43 GMT
https://trac.sagemath.org/ticket/18183#comment:2
https://trac.sagemath.org/ticket/18183#comment:2
<p>
Nice commit message ;-) You know that you can modify it afterwards by doing
</p>
<pre class="wiki">git commit --amend
</pre>
TicketvdelecroixTue, 14 Apr 2015 09:33:34 GMT
https://trac.sagemath.org/ticket/18183#comment:3
https://trac.sagemath.org/ticket/18183#comment:3
<p>
Could you add a link to the published version of the article <a class="ext-link" href="http://link.springer.com/article/10.1007%2Fs00454-008-9080-z"><span class="icon"></span>http://link.springer.com/article/10.1007%2Fs00454-008-9080-z</a> (and keep the arXiv one)?
</p>
<p>
Isn't there any interesting feature of these polytopes that would be cool to have in the documentation? Right now you only show that you can construct them... not very fancy.
</p>
<p>
Code looks good otherwise.
</p>
<p>
Vincent
</p>
TicketvdelecroixTue, 14 Apr 2015 09:34:08 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/18183#comment:4
https://trac.sagemath.org/ticket/18183#comment:4
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>documentation</em>
</li>
</ul>
TicketgitTue, 14 Apr 2015 09:58:46 GMTcommit changed
https://trac.sagemath.org/ticket/18183#comment:5
https://trac.sagemath.org/ticket/18183#comment:5
<ul>
<li><strong>commit</strong>
changed from <em>641d76c39dfa5619c1b8759c52d855be2a917088</em> to <em>6484e7198d41b716f4cb70dcf56ea7d849a6ce90</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6484e7198d41b716f4cb70dcf56ea7d849a6ce90"><span class="icon"></span>6484e71</a></td><td><code>trac #18183 more precise reference with doi</code>
</td></tr></table>
TicketchapotonTue, 14 Apr 2015 10:00:47 GMTstatus changed
https://trac.sagemath.org/ticket/18183#comment:6
https://trac.sagemath.org/ticket/18183#comment:6
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Thanks for having a look.
</p>
<p>
I have added the publication data, and the doi
</p>
<p>
I have nothing fancy to add in the doctest, sorry.
</p>
<p>
If we had the Ehrhart polynomial, we could check that their coeffs are positive..
</p>
TicketvdelecroixTue, 14 Apr 2015 10:24:07 GMT
https://trac.sagemath.org/ticket/18183#comment:7
https://trac.sagemath.org/ticket/18183#comment:7
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18183#comment:6" title="Comment 6">chapoton</a>:
</p>
<blockquote class="citation">
<p>
Thanks for having a look.
</p>
<p>
I have added the publication data, and the doi
</p>
<p>
I have nothing fancy to add in the doctest, sorry.
</p>
<p>
If we had the Ehrhart polynomial, we could check that their coeffs are positive..
</p>
</blockquote>
<p>
We do! This is in Latte (see <a class="closed ticket" href="https://trac.sagemath.org/ticket/15180" title="enhancement: create experimental package LattE Integrale (closed: fixed)">#15180</a>).
</p>
<ol><li>do <code>sage -i latte_int</code>
</li></ol><ol start="2"><li>
<pre class="wiki">def latte_input_file(P, filename='/tmp/latte.in'):
assert P.n_equations() == 0
f = open(filename, 'w')
f.write("{} {}\n".format(P.n_inequalities(), P.ambient_dim()+1))
for l in P.inequality_generator():
f.write(' '.join(map(str,l)))
f.write('\n')
f.close()
</pre></li></ol><ol start="3"><li>Then generate the file with the above code and run
<pre class="wiki"> $ sage -sh
$ count --ehrhart-polynomial /tmp/latte.in
...
Ehrhart polynomial: + 1 * t^0 + 3 * t^1 + 3 * t^2 + 1 * t^3
$ exit
</pre></li></ol><p>
Would be really cool to have that properly interfaced within Sage!
</p>
<p>
Vincent
</p>
TicketncohenTue, 14 Apr 2015 12:12:41 GMT
https://trac.sagemath.org/ticket/18183#comment:8
https://trac.sagemath.org/ticket/18183#comment:8
<p>
Algorithmicaly it looks a bit weird to do something like that:
</p>
<pre class="wiki">vertices = [ambient.sum(vector_e[convert[i]] for i in IS)
for r in range(self.full_rank() + 1)
for IS in self.independent_r_sets(r)]
</pre><p>
You enumerate the 'r+1' independent sets without using the information you got from the sets of order 'r'.
</p>
<p>
I don't know if it can be useful here, but there is something *very* related in Sage:
</p>
<p>
<a href="http://www.sagemath.org/doc/reference/combinat/sage/combinat/subsets_hereditary.html">http://www.sagemath.org/doc/reference/combinat/sage/combinat/subsets_hereditary.html</a>
</p>
<p>
Nathann
</p>
<p>
P.S.:
</p>
<pre class="wiki">+ REFERENCE:
+
+ [DLHK2007]_
</pre>
TicketchapotonTue, 14 Apr 2015 12:21:17 GMT
https://trac.sagemath.org/ticket/18183#comment:9
https://trac.sagemath.org/ticket/18183#comment:9
<p>
Well, I see your point. The true problem is that there is no <code>independent_sets</code> method for matroids.
</p>
<p>
what do you mean about the ref ?
</p>
TicketncohenTue, 14 Apr 2015 12:38:34 GMT
https://trac.sagemath.org/ticket/18183#comment:10
https://trac.sagemath.org/ticket/18183#comment:10
<p>
Hellooooooooo,
</p>
<blockquote class="citation">
<p>
Well, I see your point. The true problem is that there is no <code>independent_sets</code> method for matroids.
</p>
</blockquote>
<p>
You can get one like that:
</p>
<pre class="wiki">def independent_sets_iterator(M):
from sage.combinat.subsets_hereditary import subsets_with_hereditary_property
for x in subsets_with_hereditary_property(M.is_independent,M.groundset()):
yield x
</pre><p>
Disclaimers:
</p>
<ul><li>It is a 'fake' iterator, i.e. the amount of memory it requires is far from
constant. It does not store all bases at once, but you will store at some
point the 'independent sets of size r or r+1' for every r
</li></ul><ul><li>I have no idea if the method is optimal algorithmically. It is meant to work
for any 'hereditary' function (a property verified by
<code>Matroid.is_independent</code>), and in particular does not use any property of
matroids
</li></ul><ul><li>I suspect that it is asymptotically faster than what you do right now. The
matroid algorithm to enumerate all independent sets of size 'r' is to try all
'r'-subset and run a <code>is_independent</code> test.
</li></ul><ul><li>This implementation is at a much higher level than the Matroid
implementation: the matroid code works on bitsets, while
<code>subsets_with_hereditary_property</code> works on lists of arbitrary objects. There
is a (possibly big) loss of time there.
</li></ul><ul><li>There is a nice customization inside of <code>subsets_with_hereditary_property</code>,
which is why I implemented this function: if it detects that <code>{a,b,c}</code> is not
an independent set it will never try a superset of <code>{a,b,c}</code> again (this is
achieved through some caching of the answers of the test function.
</li></ul><blockquote class="citation">
<p>
what do you mean about the ref ?
</p>
</blockquote>
<p>
Oh sorry. I thought that it was a half-finishef entry, I had not noticed that
you were only refering to another one (which is properly written).
</p>
<p>
Nathann
</p>
TicketchapotonTue, 14 Apr 2015 12:54:33 GMT
https://trac.sagemath.org/ticket/18183#comment:11
https://trac.sagemath.org/ticket/18183#comment:11
<p>
It seems that the current branch is slightly faster..
</p>
<pre class="wiki">sage: M=matroids.named_matroids.Q10()
sage: %timeit P = M.independence_matroid_polytope()
10 loops, best of 3: 135 ms per loop
</pre><p>
compared to the one using your iterator:
</p>
<pre class="wiki">sage: M=matroids.named_matroids.Q10()
sage: %timeit P = M.independence_matroid_polytope()
10 loops, best of 3: 143 ms per loop
</pre><p>
So I propose to let to another ticket the work to have a proper independent_sets method.
</p>
TicketchapotonWed, 15 Apr 2015 06:38:18 GMTmilestone changed
https://trac.sagemath.org/ticket/18183#comment:12
https://trac.sagemath.org/ticket/18183#comment:12
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.6</em> to <em>sage-6.7</em>
</li>
</ul>
TicketvdelecroixWed, 15 Apr 2015 08:38:31 GMT
https://trac.sagemath.org/ticket/18183#comment:13
https://trac.sagemath.org/ticket/18183#comment:13
<p>
Hum. I did have a look at matroids <code>independent_r_sets</code> method. And the way to generate all independent set is to generate all sets and filter those which are independent... really!
</p>
<pre class="wiki">res = []
for X in combinations(self.groundset(), r):
X = frozenset(X)
if self._rank(X) == len(X):
res.append(X)
return res
</pre>
TicketncohenWed, 15 Apr 2015 08:41:45 GMT
https://trac.sagemath.org/ticket/18183#comment:14
https://trac.sagemath.org/ticket/18183#comment:14
<p>
This is the reason why I believe that the <code>independent_sets_iterator</code> I mentionned above will be asymptotically faster.
</p>
TicketvdelecroixWed, 15 Apr 2015 09:32:42 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/18183#comment:15
https://trac.sagemath.org/ticket/18183#comment:15
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Vincent Delecroix</em>
</li>
</ul>
<p>
This ticket is good to go!
</p>
<p>
I will try to implement something more serious for independent sets in matroids. The proposition of Nathann is not ideal since we do not want to store the "no sets" in the iteration. The boolean function is cheap in the present case.
</p>
TicketncohenWed, 15 Apr 2015 09:34:28 GMT
https://trac.sagemath.org/ticket/18183#comment:16
https://trac.sagemath.org/ticket/18183#comment:16
<blockquote class="citation">
<p>
I will try to implement something more serious for independent sets in matroids. The proposition of Nathann is not ideal since we do not want to store the "no sets" in the iteration. The boolean function is cheap in the present case.
</p>
</blockquote>
<p>
You do store them, but you store one bit for each of them. So it is not terribly large either. Why are you sure that the function is cheap in this case by the way?
</p>
<p>
Nathann
</p>
TicketncohenWed, 15 Apr 2015 09:35:26 GMT
https://trac.sagemath.org/ticket/18183#comment:17
https://trac.sagemath.org/ticket/18183#comment:17
<p>
err. Not 'one bit for each of them'. One bit for all inclusionwise minimal no-sets. Actually, I'd be ready to bet that storing all independent sets of size r is more expensive that that already.
</p>
TicketvbraunWed, 15 Apr 2015 13:58:15 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/18183#comment:18
https://trac.sagemath.org/ticket/18183#comment:18
<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>branch</strong>
changed from <em>u/chapoton/18183</em> to <em>6484e7198d41b716f4cb70dcf56ea7d849a6ce90</em>
</li>
</ul>
Ticket