#19587: Implement the Chow ring of a matroid
-------------------------------------+-------------------------------------
Reporter: tscrim | Owner: tscrim
Type: enhancement | Status: positive_review
Priority: major | Milestone: sage-6.10
Component: matroid theory | Resolution:
Keywords: | Merged in:
Authors: Travis Scrimshaw | Reviewers: Rudi Pendavingh
Report Upstream: N/A | Work issues:
Branch: | Commit:
public/matroids/chow_ring-19587 | 7bb4a54b8c4c0fb622f9ea9bb7aeef2aec1518fa
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by tscrim):
Replying to [comment:2 Rudi]:
> I reviewed the code. I was worried that I might not have the necessary
background to verify if the algebra is correct, but the definition of the
chow ring is right on page two of the paper you refer to and is pretty
straightforward. Your implementation follows the definition exactly.
>
> The code also works on my favorite fringe cases, the empty matroid,
several other rank-0 matroids, some uniform matroids, and on various other
small matroids.
That's good to hear; I didn't necessarily check on them... <.< >.>
> As far as I can tell the code is correct, looks good, survives
doctesting, so positive review! Thank you for keeping sage up to speed
with the very latest developments in matroid theory this way.
Thank you for doing the review Rudi.
> The running time of your code does increase steeply with the size/rank
of the matroid.
> {{{
> sage: M=matroids.Uniform(3,5)
> sage: M.chow_ring().gens()
> }}}
> is more or less instantaneous, but M=matroids.Uniform(4,5) simply does
not finish on my machine, and neither does M=matroids.Uniform(3,6). Also,
the computation for P8 gets killed by my linux machine, probably due to
excessive resource hogging.
I'm not too surprised because, as you said, it is roughly quadratic in the
number of flats and along with the linear relations, this gives a lot of
relations for computing the Gröbner basis. If I understand my quick
Googling correctly, this grows exponentially in the number of relations.
I can create the Chow rings relatively quickly, but getting the Gröbner
basis is what really takes the time. Using `U(3,6)` has 45 relations, and
a bunch of the linear relations have 10+ terms. However, the `gens()` does
work fairly quickly over `GF(2)` (where it has 352 polynomials) and `QQ`
(with 407 polynomials). So the only thing we could really add to it at
this point is a note saying to try it over other rings/fields (or make
Singular go faster over `ZZ`)...
--
Ticket URL: <http://trac.sagemath.org/ticket/19587#comment:4>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
