Opened 5 years ago

Closed 5 years ago

#18183 closed enhancement (fixed)

Implement two matroid polytopes

Reported by: chapoton Owned by:
Priority: major Milestone: sage-6.7
Component: matroid theory Keywords: matroid polytope
Cc: Merged in:
Authors: Frédéric Chapoton Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues: documentation
Branch: 6484e71 (Commits) Commit: 6484e7198d41b716f4cb70dcf56ea7d849a6ce90
Dependencies: Stopgaps:

Description

To a matroid one can associate two polytopes.

  • one with bases as vertices
  • one with indep. sets as vertices

The former is a facet of the latter.

Here is an implementation.

Change History (18)

comment:1 Changed 5 years ago by chapoton

  • Branch set to u/chapoton/18183
  • Commit set to 641d76c39dfa5619c1b8759c52d855be2a917088
  • Status changed from new to needs_review

New commits:

641d76ctrac #18XXX two matroid polytopes

comment:2 Changed 5 years ago by vdelecroix

Nice commit message ;-) You know that you can modify it afterwards by doing

git commit --amend

comment:3 Changed 5 years ago by vdelecroix

Could you add a link to the published version of the article http://link.springer.com/article/10.1007%2Fs00454-008-9080-z (and keep the arXiv one)?

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.

Code looks good otherwise.

Vincent

comment:4 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to needs_work
  • Work issues set to documentation

comment:5 Changed 5 years ago by git

  • Commit changed from 641d76c39dfa5619c1b8759c52d855be2a917088 to 6484e7198d41b716f4cb70dcf56ea7d849a6ce90

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

6484e71trac #18183 more precise reference with doi

comment:6 follow-up: Changed 5 years ago by chapoton

  • Status changed from needs_work to needs_review

Thanks for having a look.

I have added the publication data, and the doi

I have nothing fancy to add in the doctest, sorry.

If we had the Ehrhart polynomial, we could check that their coeffs are positive..

comment:7 in reply to: ↑ 6 Changed 5 years ago by vdelecroix

Replying to chapoton:

Thanks for having a look.

I have added the publication data, and the doi

I have nothing fancy to add in the doctest, sorry.

If we had the Ehrhart polynomial, we could check that their coeffs are positive..

We do! This is in Latte (see #15180).

  1. do sage -i latte_int
  1. 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()
    
  1. Then generate the file with the above code and run
     $ sage -sh
     $ count --ehrhart-polynomial /tmp/latte.in
     ...
     Ehrhart polynomial:  + 1 * t^0 + 3 * t^1 + 3 * t^2 + 1 * t^3
     $ exit
    

Would be really cool to have that properly interfaced within Sage!

Vincent

Last edited 5 years ago by vdelecroix (previous) (diff)

comment:8 Changed 5 years ago by ncohen

Algorithmicaly it looks a bit weird to do something like that:

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)]

You enumerate the 'r+1' independent sets without using the information you got from the sets of order 'r'.

I don't know if it can be useful here, but there is something *very* related in Sage:

http://www.sagemath.org/doc/reference/combinat/sage/combinat/subsets_hereditary.html

Nathann

P.S.:

+        REFERENCE:
+
+        [DLHK2007]_
Last edited 5 years ago by ncohen (previous) (diff)

comment:9 follow-up: Changed 5 years ago by chapoton

Well, I see your point. The true problem is that there is no independent_sets method for matroids.

what do you mean about the ref ?

comment:10 in reply to: ↑ 9 Changed 5 years ago by ncohen

Hellooooooooo,

Well, I see your point. The true problem is that there is no independent_sets method for matroids.

You can get one like that:

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

Disclaimers:

  • 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
  • I have no idea if the method is optimal algorithmically. It is meant to work for any 'hereditary' function (a property verified by Matroid.is_independent), and in particular does not use any property of matroids
  • 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 is_independent test.
  • This implementation is at a much higher level than the Matroid implementation: the matroid code works on bitsets, while subsets_with_hereditary_property works on lists of arbitrary objects. There is a (possibly big) loss of time there.
  • There is a nice customization inside of subsets_with_hereditary_property, which is why I implemented this function: if it detects that {a,b,c} is not an independent set it will never try a superset of {a,b,c} again (this is achieved through some caching of the answers of the test function.

what do you mean about the ref ?

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).

Nathann

Last edited 5 years ago by ncohen (previous) (diff)

comment:11 Changed 5 years ago by chapoton

It seems that the current branch is slightly faster..

sage: M=matroids.named_matroids.Q10()
sage: %timeit  P = M.independence_matroid_polytope()
10 loops, best of 3: 135 ms per loop

compared to the one using your iterator:

sage: M=matroids.named_matroids.Q10()
sage: %timeit  P = M.independence_matroid_polytope()
10 loops, best of 3: 143 ms per loop

So I propose to let to another ticket the work to have a proper independent_sets method.

comment:12 Changed 5 years ago by chapoton

  • Milestone changed from sage-6.6 to sage-6.7

comment:13 Changed 5 years ago by vdelecroix

Hum. I did have a look at matroids independent_r_sets method. And the way to generate all independent set is to generate all sets and filter those which are independent... really!

res = []
for X in combinations(self.groundset(), r):
    X = frozenset(X)
    if self._rank(X) == len(X):
        res.append(X)
    return res

comment:14 Changed 5 years ago by ncohen

This is the reason why I believe that the independent_sets_iterator I mentionned above will be asymptotically faster.

Last edited 5 years ago by ncohen (previous) (diff)

comment:15 follow-up: Changed 5 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

This ticket is good to go!

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.

comment:16 in reply to: ↑ 15 Changed 5 years ago by ncohen

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.

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?

Nathann

comment:17 Changed 5 years ago by ncohen

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.

comment:18 Changed 5 years ago by vbraun

  • Branch changed from u/chapoton/18183 to 6484e7198d41b716f4cb70dcf56ea7d849a6ce90
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.