Huge patch on Trac 7477: Matroid theory

[Stefan van Zwam]

Dear Sage developers,

Over the past two years I've been working with several people on bringing Matroid Theory to Sage. We wanted this to be research-level code that will remain relevant for a long time, so we decided to have the design mature for a while before integrating it with Sage. By now we have test-driven the code (it produces output consistent with the theory and with computations carried out by other software for matroid theory), and it is already in use by people in the matroid theory community who install it separately on top of Sage.

The code has now been submitted, see

http://trac.sagemath.org/sage_trac/ticket/7477

There are about 21,000 lines of code, and 500 functions with docstrings. While it is doable to check that it plays nice with the rest of Sage and follows all coding conventions (I'm  sure it does), a full code review sounds like a hard task. So I write you to solicit opinions on how to proceed. Four suggestions have been made on the ticket:

1) Treat it as if it were an spkg, and accept with only a cursory review

2) Try to assemble a team of reviewers, each responsible for part of the code

3) Chop it up into separate, smaller pieces and have those submitted as separate tickets

4) Get the authors of the package to review each others' code

Options (3) and (4) are not very feasible. The core part of the code has close links all over the place, and I think I can't get it much below 9,000 lines of code without a lot of extra work. It would also mean rewriting all docstrings since we can't use the catalog of matroids for our examples. As for (4), Rudi Pendavingh and I are responsible for the bulk of this code, and each of us has had a hand in pretty much every part of it. 

That leaves (1) and (2). I hope to get the other users/developers to review parts of it, but so far I have not heard of any commitments, and I fear it would still take a long time to get it accepted. I'd rather see that time spent building a user base and ironing out any bugs uncovered in actual use.

What do you all think?

Regards,

Stefan.

P.S. The impact on the rest of Sage is the following:

* add a directory sage.matroids

* lazy_import two items, a function "Matroid" and a package "matroids", on startup

* add an entry "Matroid theory" to the reference manual.

[Moutons Matheux]

Dear Stefan,

  It is splendid, the rapid progress in bringing the matroid code to this level. Surely the only way to proceed is to start using it.

That's what we do anyway, when writing code. First level errors are all over the place, and rapidly come to light. This has already

been the case. If somewhat later, up comes a counterexample to Rota's conjecture, there will then be a furious and deep verification of the code,

with many enthusiastic participants burning the midnight oil.

Looking forward to our gathering in June.

I have never been able to come up with a satisfactory definition of an "screen image" of a matroid of rank higher than four,

though I did struggle to produce one or two in the old book. Perhaps I'll just write some postscript code that will work for low-rank

matroids, and leave it at that. I promised to do this, but have so far made no steps in that direction. Does anyone have

a heuristic for placing points? Or for determining in what sense an image can be "improved" by moving points around?

In writing Postscript code for drawings of matroids, I have always done this by "hand". This usually amounts simply to

minimising the number and degree of distortions of hopefully-straight lines, and to grouping coplanar points so they

can be sensed as polygonal faces of 3-d structural forms.

On the other hand, I did update to Python 3 my code for studying the Whitney algebra of a matroid,

and in particular, for straightening in that algebra, i.e.: finding integer linear relations among monomials (tensor products

of independent sets, as words, of given shape and content), in particular, those relating an arbitrary such monomial to

a set of "standard" monomials, the earliest such adequate set of monomials, in lexicographic order. Rudi tells me this

must have something to do with Mr Groebner. I would be delighted to include this in the Sage package.

best wishes,

Henry

--
 
---
You received this message because you are subscribed to the Google Groups "sage-matroid" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-matroid...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Stefan]

How easy/feasible would it be to create an spkg and propose it to be added as an optional package?

Is that another possibility?

It is a possibility, and would be pretty feasible, but an inferior solution. From our point of view (and our audience), having the code be an actual part of Sage is just more convenient. It makes sure we have full access to the bug reporting of Trac, and it lowers the threshold for contributions by other developers. Also, it is harder for other parts of the Sage library (graphs, linear codes, ...) to use the matroid routines when they are hidden in an optional package.

--Stefan.

[Nathann Cohen]

> It is a possibility, and would be pretty feasible, but an inferior solution.
> From our point of view (and our audience), having the code be an actual part
> of Sage is just more convenient. It makes sure we have full access to the
> bug reporting of Trac, and it lowers the threshold for contributions by
> other developers. Also, it is harder for other parts of the Sage library
> (graphs, linear codes, ...) to use the matroid routines when they are hidden
> in an optional package.

Annnnnd future additions to the SPKG will not have to be reviewed
either, and the documentation does not appear on Sage's website.

And they cannot really say to everybody that they can just download
the SPKG and use it in Sage, for if they attempt to use new features
of Sage with their code somebody who runs an old version of Sage can
install their SPKG, which uses functions that are not included in his
version.

I would vote for 1 among all alternatives... and trust the authors. As
simple as that. I also do believe that considering the code they
produced, they would be the first to fix bugs when they will be
reported, be it a small problem or a larger one. It seems to be a work
of care and good will :-)

Nathann

[Stefan van Zwam]

Dear Henry,

I only asked for visualization of the rank-3 matroids. In rank 4 geometric pictures are already insufficient sometimes. However, for some of the fixed rank-4 ones from our catalog (such as the Vámos), we might want to include a standard picture, maybe allowing the labels of the points to be added in dynamically.

I'm looking forward to the meeting too! We will discuss this further then.

Cheers,

Stefan.

[Rudi Pendavingh]

Dear Henry,

You and I briefly discussed the visualization of matroids of higher rank than 4 in Maastricht, last year. One idea was to picture the connectivity properties, e.g the tree that visualizes the 3-separations of the matroid. But this 'advanced connectivity' should first be implemented itself. Also, this can never be the only visualization option, since most matroids will have no low-rank separations.

I agree with Stefan that we should focus on drawing 'projective' pictures of low-rank matroids first.

The graph theory package has a 'show' option, and it is perhaps interesting to see how they decide the placement of vertices. That placement of points (within a 'picture frame') seems to be a tough problem, for both graphs and matroids.

Cheers,

Rudi

[Rob Beezer]

Dear sage-devel,

Late to the party, as usual.  I've been following the  sage-matroid  list since its inception, helping out where I can.  Stefan, Rudi and others, have been *very* responsive to bug reports on their work-in-progress.  The current users are a very knowledgeable bunch (both in mathematics and combinatorial computing), so the discussions about design decisions have been very thoughtful.  I have a lot of confidence in the quality of this contribution.

While I had hoped this did not become a "patch bomb", I do agree with much of what Nathann has said.

(1) The code is being used currently for research problems, so subtle bugs are being actively ferreted out.  These are being fixed rapidly.

(2) The (computational) matroid community will be a good addition to Sage's stable.

(3) Development will be much faster and broader when this work is integrated into Sage proper.  Much of the traffic on  sage-matroid  involves pecularities of implementing/running this as an add-on.

(4) Stressing other parts of Sage (eg matrix code) should lead to improvements there.

So I would be in favor of accepting this en masse if it had a knowledgeable review for fitting into Sage, as Nathann and Volcker propose.  I also hope that the matroid community can commit to working with other developers in improving the matrix code (and perhaps other areas) to the point where they do not need to reimplement existing functionality.  We are already seeing some of this at http://trac.sagemath.org/14627, so hopefully that can continue.

Finally, thanks to the  sage-matroid  group for all their hard work on this.  It is going to be another jewel in Sage's crown.

Rob

[Dima Pasechnik]

On Friday, 24 May 2013 04:31:46 UTC+8, Rob Beezer wrote:

So I would be in favor of accepting this en masse if it had a knowledgeable review for fitting into Sage, as Nathann and Volcker propose. 

I second this, too.

Dima

 

[Volker Braun]

On Thursday, May 23, 2013 9:31:46 PM UTC+1, Rob Beezer wrote:

So I would be in favor of accepting this en masse if it had a knowledgeable review for fitting into Sage, as Nathann and Volcker propose.

I agree with everything except the spelling of my name ;-)

 

[Nathann Cohen]

> I agree with everything except the spelling of my name ;-)

Sooooooooooo how do we do ? We check that the ticket is up to date,
does not break doctests, and we set it to "positive review" with as
reviewer "The Sage Team" ? :-P

Otherwise they may have to rebase their patch every second day.

Nathann

[Volker Braun]

I think the following needs to be addressed:

  * segmentation faults due to recent changes in Sage

  * either replace the private reimplementation of matrices or give a good reason for why it is necessary

Then it is imho ready for inclusion.

[Volker Braun]

On Saturday, May 25, 2013 2:39:36 AM UTC+1, Travis Scrimshaw wrote:

  * either replace the private reimplementation of matrices or give a good reason for why it is necessary 

Wasn't the second point addressed in http://trac.sagemath.org/14627, so shouldn't the matrices be replaced?

Well I hope so but there might be another performance bottleneck that the matroid code hits. Maybe one of the authors can tell us more about it?

PS - the extra c in Volcker makes your name sound ckooler :P

Oh boy ;-)

 

[Stefan]

On Saturday, May 25, 2013 6:38:00 AM UTC-4, Volker Braun wrote:

On Saturday, May 25, 2013 2:39:36 AM UTC+1, Travis Scrimshaw wrote:

  * either replace the private reimplementation of matrices or give a good reason for why it is necessary 

Wasn't the second point addressed in http://trac.sagemath.org/14627, so shouldn't the matrices be replaced?

Well I hope so but there might be another performance bottleneck that the matroid code hits. Maybe one of the authors can tell us more about it?

I'd have to check carefully. There's likely to be some performance loss even when all obvious bottlenecks are accounted for, because for our special classes BinaryMatrix, TernaryMatrix, QuaternaryMatrix we use inline get() and set() methods that bypass the Sage finite field elements. We want this code to push the limits of matroid computation, so we'd hate to incur even a 10% speed loss.

And as Travis said, issues with the documentation etc. can be fixed over time. We intend to use, improve, and expand this code for a long, long time.

--Stefan.

[Stefan]

I'd have to check carefully. There's likely to be some performance loss even when all obvious bottlenecks are accounted for, because for our special classes BinaryMatrix, TernaryMatrix, QuaternaryMatrix we use inline get() and set() methods that bypass the Sage finite field elements. We want this code to push the limits of matroid computation, so we'd hate to incur even a 10% speed loss.

Oh, we also use bitpacking for GF(3) and GF(4), which in Sage is done only for binary matrices currently, if I'm not mistaken.

[Volker Braun]

On Saturday, May 25, 2013 3:51:06 PM UTC+1, Stefan wrote:

There's likely to be some performance loss even when all obvious bottlenecks are accounted for, because for our special classes BinaryMatrix, TernaryMatrix, QuaternaryMatrix we use inline get() and set() methods that bypass the Sage finite field elements.

Only if get/setting matrix elements is actually the bottleneck. But once you are actually doing something with the matrices then e.g. Strassen-Winograd will run circles around the naive O(N^3) multiplication that you have in there.

[Stefan van Zwam]

Multiplication occurs only a handful of times (when computing invariants). The real bottleneck is this method (focus on self._A which is the matrix):

    cdef bint __exchange(self, long x, long y):

        """

        Put element indexed by ``x`` into basis, taking out element ``y``. Assumptions are that this is a valid basis exchange.

        .. NOTE::

            Safe for noncommutative rings.

        """

        cdef long px, py, r

        px = self._prow[x]

        py = self._prow[y]

        piv = self._A.get_unsafe(px, py)

        pivi = piv ** (-1)

        self._A.row_scale(px, pivi)

        self._A.set_unsafe(px, py, pivi + self._one)       # pivoting without column scaling. Add extra so column does not need adjusting

        for r in xrange(self._A.nrows()):            # if A and A' are the matrices before and after pivoting, then

            a = self._A.get_unsafe(r, py)       # ker[I A] equals ker[I A'] except for the labelling of the columns

            if a and r != px:

                self._A.row_add(r, px, -a)

        self._A.set_unsafe(px, py, pivi)

        self._prow[y] = px

        self._prow[x] = py

        BasisExchangeMatroid.__exchange(self, x, y)

--Stefan.

[Volker Braun]

If that is actually the bottleneck then the relevant matrices just need to override add_multiple_of_row_c with a specialized version instead of using the generic one from matrix0.

It seems that renaming Sage's add_multiple_of_row() into row_add() etc. in your code is just making it unnecessarily difficult to switch to Sage matrices.

[Stefan van Zwam]

Hi Volker, and everyone else on sage-devel,

I did some speed tests with an old version of the code that still used Sage matrices (commit 6d9e689 on bitbucket, with a few tweaks to make it run on Sage 5.10.beta4). Each of these tests performs a matroid computation through extensive pivoting.

I ran three versions of the test:

* Sage matrices
* Same algorithm, using a LeanMatrix instance
* Optimized algorithm for this class of matroids

for four different classes of matroids:

* Binary
* Ternary
* Quaternary
* Regular

Without patch 14627 (on Sage 5.9.beta3):

Comparing the speed of various classes.
==========================================================
Binary matroids:
Sage matrix:
5 loops, best of 5: 101 ms per loop
lean_matrix.BinaryMatrix:
5 loops, best of 5: 21.2 ms per loop
BinaryMatroid and BinaryMatrix:
5 loops, best of 5: 3.08 ms per loop
==========================================================
Ternary matroids:
Sage matrix:
5 loops, best of 5: 5.7 s per loop
lean_matrix.TernaryMatrix:
5 loops, best of 5: 1.29 s per loop
TernaryMatroid:
5 loops, best of 5: 7.98 ms per loop
==========================================================
Quaternary matroids:
Sage matrix:
5 loops, best of 5: 186 ms per loop
lean_matrix.QuaternaryMatrix:
5 loops, best of 5: 205 ms per loop
QuaternaryMatroid and QuaternaryMatrix:
5 loops, best of 5: 13.4 ms per loop
==========================================================
Regular matroids:
Sage matrix:
5 loops, best of 5: 753 ms per loop
lean_matrix.IntegerMatrix:
5 loops, best of 5: 49.3 ms per loop
RegularMatroid and IntegerMatrix:
5 loops, best of 5: 19.8 ms per loop

With patch 14627 (on Sage 5.10.beta4):

Comparing the speed of various classes.
==========================================================
Binary matroids:
Sage matrix:
5 loops, best of 5: 91.2 ms per loop
lean_matrix.BinaryMatrix:
5 loops, best of 5: 21.4 ms per loop
BinaryMatroid and BinaryMatrix:
5 loops, best of 5: 3.24 ms per loop
==========================================================
Ternary matroids:
Sage matrix:
5 loops, best of 5: 240 ms per loop
lean_matrix.TernaryMatrix:
5 loops, best of 5: 1.2 s per loop
TernaryMatroid:
5 loops, best of 5: 8.17 ms per loop
==========================================================
Quaternary matroids:
Sage matrix:
5 loops, best of 5: 434 ms per loop
lean_matrix.QuaternaryMatrix:
5 loops, best of 5: 162 ms per loop
QuaternaryMatroid and QuaternaryMatrix:
5 loops, best of 5: 11.3 ms per loop
==========================================================
Regular matroids:
Sage matrix:
5 loops, best of 5: 687 ms per loop
lean_matrix.IntegerMatrix:
5 loops, best of 5: 45.7 ms per loop
RegularMatroid and IntegerMatrix:
5 loops, best of 5: 18.6 ms per loop


Conclusions:

The only speedup obtained from 14627 is for prime fields (and it is HUGE: a factor 20). But our custom class still outperforms Sage's matrices by at least a factor 3 much of the time. With the more specialized routines that exploit the bit packed representation of the matrix, the speedup is even more significant.

It will require significant effort to bring Sage's matrices up to the same speed. For ternary matroids, it won't happen until Martin Albrecht has generalized M4Ri(e) to fields of other characteristic. So I propose to keep the LeanMatrix code for now, opening a ticket titled something like "Bring Sage matrices into the matroid code without performance loss" for a later date.

--Stefan.

P.S. It looks like GF(4)-matrices had a speed regression between 5.9 and 5.10?!

[Volker Braun]

Overall timings aren't really that useful, without profiling there is no way to tell what part is slow. Can you at least give your own matrix class the same interface as Sage matrices? It should only be a matter of switching from ... import ... as MyMatrix. If they are not interchangeable then nobody will be able to profile it and no progress will be made.

[Volker Braun]

On Tuesday, May 28, 2013 4:52:29 PM UTC+1, Dima Pasechnik wrote:

Also, did you try implementing this using numpy arrays? 

Numpy doesn't support bitpacked Z/n Z so thats of no use.

[Stefan]

Hi Travis,

Thanks for your suggestion! I'll experiment with it later today.

Also, if you're not really using matrices, such as doing a significant number of multiplications/using category model/etc., but instead as a nice data structure, I'd be more inclined to say to strip out the non speed-essential methods, making it as lightweight and specific as possible and converting to proper matrices when needed, and include it into sage (after perhaps changing the name). How does this sound to everyone?

That is, in fact, what we've done. The class LeanMatrix and its subclasses only implement the essential (to us) operations, using cdef methods for speed. They are only used internally: the user inputs Sage matrices, and whenever the code returns a matrix, it's a Sage matrix (some advanced, underscored, methods are an exception, but those are mainly for internal use). 

--Stefan.

[Stefan]

That method is the generic version, which works for arbitrary rings (including non-commutative ones). The BinaryMatroid, TernaryMatroid, QuaternaryMatroid classes have optimized versions already.

--Stefan.

[Dima Pasechnik]

On 2013-05-28, Volker Braun <vbrau...@gmail.com> wrote:
> ------=_Part_216_25030331.1369757141712
> Content-Type: text/plain; charset=ISO-8859-1

>
> On Tuesday, May 28, 2013 4:52:29 PM UTC+1, Dima Pasechnik wrote:
>
>> Also, did you try implementing this using numpy arrays?
>
>
> Numpy doesn't support bitpacked Z/n Z so thats of no use.

how about fflas_ffpack (or linpack?) then?
They talk about fast multiplication, but surely fast addition should be
there, too...

[Stefan van Zwam]

http://trac.sagemath.org/sage_trac/ticket/7477

In case you haven't been following the discussion on Sage Trac, let me repost what Rob Beezer just wrote:

This looks real good to me. I'm with Volker at Sage Days 48 and he has reviewed the code (and integration with Sage). I'll check off on the documentation, which looks excellent. The HTML output looks good, as do the 145 pages of the PDF reference manual.
All doctests in sage/matroids pass on 5.10rc2 with dependencies.
So, positive review.
Be prepared for a few hiccups once this gets merged into a beta and gets tested across a diverse collection of systems. Hooefully this will also go into an early stage of the 5.11 series. Thanks for your patience with the review process.
And thanks for the major contribution to Sage. I hope this makes your meeting later this month even more productive.
Next up: a thematic tutorial! ;-)
Rob 

 

So, barring unforeseen complications on other systems, our code should be part of Sage 5.11!

--Stefan.

[Rob Beezer]

Yes, congratulations to everybody for all their work on this. Of course, the
code is a lot of very careful work, but the authors of the documentation should
be recognized for the size of that task, which in old money (145 printed pages)
is easily recognizable as a sizeable accomplishment.

Rob

On 06/18/2013 12:01 PM, Stefan van Zwam wrote:
> http://trac.sagemath.org/sage_trac/ticket/7477

[Stefan van Zwam]

On Tuesday, June 18, 2013 3:14:43 PM UTC-4, Rob Beezer wrote:

Yes, congratulations to everybody for all their work on this.  Of course, the
code is a lot of very careful work, but the authors of the documentation should
be recognized for the size of that task, which in old money (145 printed pages)
is easily recognizable as a sizeable accomplishment.

And that's only the non-underscored methods ;) 

[Rudi Pendavingh]

> So, barring unforeseen complications on other systems, our code should be part of Sage 5.11!

Stefan, I am extremely impressed with the way the integration into Sage took place. You were completely on top of it, and I'm sure that the prompt way you and Michael responded to all the comments and requests of the Sage community have made a huge difference. Terrific work!

And I think we should really thank Rob, Nathann, Volker and all the Sage community. Even after giving them our 'patch bomb', they responded in the most positive and constructive way throughout.

Cheers,

Rudi

[Dillon Mayhew]

Agreed, congratulations to all, including Rudi. I'm sure this is going to be a real asset to the matroid community.

Dillon 

[Michael Welsh]

On 19/06/2013, at 7:01 AM, Stefan van Zwam <stefan...@gmail.com> wrote:
>
> So, barring unforeseen complications on other systems, our code should be
> part of Sage 5.11!

And merged into 5.11-beta3.

[Michael Welsh]

Actually merged into 5.12-beta1. yay!
http://boxen.math.washington.edu/home/release/sage-5.12.beta1/tickets.html#t7477

[Henry Crapo]

On 2 May 2013, at 20:40, Stefan van Zwam <stefan...@gmail.com> wrote:

I'd rather see that time spent building a user base and ironing out any bugs uncovered in actual use.

This is my preference. But with added switch: that all who use the code report to some specific person, 

for each non-trivial usage,

what type of computations were performed, 

with what ease of utilisation/interaction, 

and with what satisfaction as to results produced (with respect to both pertinence and volume). 

Said more simply, it can be useful to have not only "bug-reports",

 but positive signals of confidence and utility, ease of use.

Henry

[Henry Crapo]

Dear Rudi,

Thank you for your suggestions. I'll be tempted also to re-read Bill Tutte's "How to Draw a Graph".
The electrical network approach might well carry over in some sense to matroids.

I am just finishing the uphill road following surgery 2/8 on the bladder/prostate. All is well,
but it will be September before I am back home for a good spell, ready to open my math books
and programs.

Perhaps there's a big-bang approach, starting from all points at centre screen, and searching for
directions and relative degrees of separation for points, or some sense of relative anti-gravity repulsion (vectorial,
that is, directional), either of pipartitions of the set of points, or simply for pairs of points. (Tiong Seng and I did this when
defining "shelling" for isostatic graphs.)

Is that crazy enough for a Saturday morning? (Given that two points not want to sit one upon another,
in which compass direction should they prefer to separate? This being a question of neighbours.)

I haven't yet been able to get my photos together for the blog, but have not forgotten.

with best wishes,
Henry


On 4 May 2013, at 09:53, Rudi Pendavingh <rudi.pe...@gmail.com> wrote:

> Dear Henry,
>
> You and I briefly discussed the visualization of matroids of higher rank than 4 in Maastricht, last year. One idea was to picture the connectivity properties, e.g the tree that visualizes the 3-separations of the matroid. But this 'advanced connectivity' should first be implemented itself. Also, this can never be the only visualization option, since most matroids will have no low-rank separations.
>
> I agree with Stefan that we should focus on drawing 'projective' pictures of low-rank matroids first.
>
> The graph theory package has a 'show' option, and it is perhaps interesting to see how they decide the placement of vertices. That placement of points (within a 'picture frame') seems to be a tough problem, for both graphs and matroids.
>
> Cheers,
>
> Rudi
>
> On 4 mei 2013, at 00:51, Stefan van Zwam <stefan...@gmail.com> wrote:
>
>> Dear Henry,
>>
>> I only asked for visualization of the rank-3 matroids. In rank 4 geometric pictures are already insufficient sometimes. However, for some of the fixed rank-4 ones from our catalog (such as the Vámos), we might want to include a standard picture, maybe allowing the labels of the points to be added in dynamically.
>>
>> I'm looking forward to the meeting too! We will discuss this further then.
>>
>> Cheers,
>>
>> Stefan.
>>
>> On 3 mei 2013, at 03:17, Moutons Matheux wrote:
>>
>>> Dear Stefan,
>>>
>>> It is splendid, the rapid progress in bringing the matroid code to this level. Surely the only way to proceed is to start using it.
>>> That's what we do anyway, when writing code. First level errors are all over the place, and rapidly come to light. This has already
>>> been the case. If somewhat later, up comes a counterexample to Rota's conjecture, there will then be a furious and deep verification of the code,
>>> with many enthusiastic participants burning the midnight oil.
>>>
>>> Looking forward to our gathering in June.
>>>
>>> I have never been able to come up with a satisfactory definition of an "screen image" of a matroid of rank higher than four,
>>> though I did struggle to produce one or two in the old book. Perhaps I'll just write some postscript code that will work for low-rank
>>> matroids, and leave it at that. I promised to do this, but have so far made no steps in that direction. Does anyone have
>>> a heuristic for placing points? Or for determining in what sense an image can be "improved" by moving points around?
>>> In writing Postscript code for drawings of matroids, I have always done this by "hand". This usually amounts simply to
>>> minimising the number and degree of distortions of hopefully-straight lines, and to grouping coplanar points so they
>>> can be sensed as polygonal faces of 3-d structural forms.
>>>
>>> On the other hand, I did update to Python 3 my code for studying the Whitney algebra of a matroid,
>>> and in particular, for straightening in that algebra, i.e.: finding integer linear relations among monomials (tensor products
>>> of independent sets, as words, of given shape and content), in particular, those relating an arbitrary such monomial to
>>> a set of "standard" monomials, the earliest such adequate set of monomials, in lexicographic order. Rudi tells me this
>>> must have something to do with Mr Groebner. I would be delighted to include this in the Sage package.
>>>
>>> best wishes,
>>> Henry
>>>
>>> On 02 May 2013, at 20:40, Stefan van Zwam <stefan...@gmail.com> wrote:
>>>
>>>> Dear Sage developers,
>>>>
>>>> Over the past two years I've been working with several people on bringing Matroid Theory to Sage. We wanted this to be research-level code that will remain relevant for a long time, so we decided to have the design mature for a while before integrating it with Sage. By now we have test-driven the code (it produces output consistent with the theory and with computations carried out by other software for matroid theory), and it is already in use by people in the matroid theory community who install it separately on top of Sage.
>>>>
>>>> The code has now been submitted, see
>>>>
>>>> http://trac.sagemath.org/sage_trac/ticket/7477
>>>>
>>>> There are about 21,000 lines of code, and 500 functions with docstrings. While it is doable to check that it plays nice with the rest of Sage and follows all coding conventions (I'm sure it does), a full code review sounds like a hard task. So I write you to solicit opinions on how to proceed. Four suggestions have been made on the ticket:
>>>>
>>>> 1) Treat it as if it were an spkg, and accept with only a cursory review
>>>> 2) Try to assemble a team of reviewers, each responsible for part of the code
>>>> 3) Chop it up into separate, smaller pieces and have those submitted as separate tickets
>>>> 4) Get the authors of the package to review each others' code
>>>>
>>>> Options (3) and (4) are not very feasible. The core part of the code has close links all over the place, and I think I can't get it much below 9,000 lines of code without a lot of extra work. It would also mean rewriting all docstrings since we can't use the catalog of matroids for our examples. As for (4), Rudi Pendavingh and I are responsible for the bulk of this code, and each of us has had a hand in pretty much every part of it.
>>>>
>>>> That leaves (1) and (2). I hope to get the other users/developers to review parts of it, but so far I have not heard of any commitments, and I fear it would still take a long time to get it accepted. I'd rather see that time spent building a user base and ironing out any bugs uncovered in actual use.
>>>>
>>>> What do you all think?
>>>>
>>>> Regards,
>>>>
>>>> Stefan.
>>>>
>>>> P.S. The impact on the rest of Sage is the following:
>>>>
>>>> * add a directory sage.matroids
>>>> * lazy_import two items, a function "Matroid" and a package "matroids", on startup
>>>> * add an entry "Matroid theory" to the reference manual.