#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:
-------------------------------------+-------------------------------------
Changes (by Rudi):
* status: needs_review => positive_review
* reviewer: => Rudi Pendavingh
Comment:
Hi Travis,
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 one 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.
As far as I can tell the code is correct, looks good, survives doctesting,
so positive review! Thank you for keeping the sage up to speed with the
very latest developments in matroid theory this way.
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.
Looking at the definition of chow ring, that makes sense. The full set of
flats is simply a very very big set of generators already for small
matroids. Just looking at the definition (and blissfully unaware of any
further theory), I wonder if computing the chow ring recursively may be
more efficient, e.g. first computing the chow ring of the truncation, then
adding the generators and relations involving the hyperplanes. Or perhaps
another recursion, where you first compute a deletion or contraction
minor.
--
Ticket URL: <http://trac.sagemath.org/ticket/19587#comment:2>
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.
