# Matroids in Wellington

I’m at a small workshop/conference on “matroid computation” in Wellington this week – the idea being to get together the handful of people in the world who are interested not only in matroids, but particularly in *computing* with matroids to have a few talks and lots of discussion.

The problem we face is that everyone has written their own software for their own problems in their own language and with varying degrees of reusability, flexibility and extensibility. Basically there is simply no matroid equivalent of GAP or Magma that will permit the exploration of individual matroids, routine case checking of small cases, identification of known small matroids and so on, while also facilitating reasonably hard-core research programming.

Anyway the week has been fun and I’ve learned a lot about other people’s approaches – my own particular approach is in using *databases* that permit rapid answering of a variety of different problems (after a considerable “set-up” time). Here are the slides from my talk (VUW2010) describing the basic set up and one problem that I used it for, though there are many others on the list.

I also happen to particularly like Wellington as a city – on a sunny day it is stunningly beautiful and it has a really lively “vibe” – it is still cheap enough for arty, hippie, countercultural types to live, shop and play downtown and they seem to coexist happily with the politicians and bankers. So there’s a real eclectic mix of shops like Minnie Cooper where you can buy $400 handbags, alongside body piercing joints. But one thing’s for sure – banker or hippy, politician or artist – they all drink a heck of a lot here! It’s also a nice change from Perth (with its “Swiss prices” as recent visitor Harald Helfgott described them) to be able to easily afford daily things and to be able to walk into a restaurant with only a cursory glance at the menu prices!

Wellington is incredibly hilly and they basically just perch houses on every little spot they can.

Anyway, back to the Maths…

It seems that we have reached a bit of an impasse – a GAP or Sage package is favoured by some, but because the data required to store a general matroid can get awfully large awfully quickly, it is far from clear that the general purpose data structures offered by GAP/Sage can effectively replace the highly-tuned tightly packed data structures in the existing code that are manipulated with C’s bitwise operators.

So where to go from here? Maybe we’ll just end up back with everyone using their own code for their own particular purposes? Maybe that’s just the best we can do with such loosely structured objects as matroids?

It may be that sage+cython would be a lot more useful than sage itself.

What we’d really like is to not reinvent the wheel in terms of implementing things like finite fields, rings, polynomials, arbitrary precision arithmetic etc but still be able to use specific C++ data structures and existing chunks of optimized code etc as transparently as possible.

I haven’t had time yet to really investigate exactly how external code interacts with Sage data structures / objects (or vice versa).

In GAP it is quite clunky to use completely external C/C++ code, in that the GAP code basically has to write a text file for input to the external program, spawn a process to run the external program, and then parse the output. Fine for really big discrete jobs (like running nauty from within GRAPE) but not really suitable for tight integration of GAP facilities with C code.

My experience with Sage is (mostly) very positive. Begin by just writing everything in Sage (i.e. Python with all the useful extensions and built-in extra types); then you can speedup the bottlenecks by rewriting them in Cython (or in C/C++, if really needed).

You get an extra benefit of being able to communicate with GAP in a natural way (now via files/raw pipes, that is). Which is a great deal if you want to look into the underlying groups…

Sage is very flexible (much better than GAP, say) in sense that it’s easy to get your own code into its “main library”, if needed – or convince someone to fix something for you…

Or if you are scared of Sage, use Python/Cython (+C/C++, if really needed), with admittedly less powerful toolboxes like Sympy/Scipy/Numpy, which give you a bit of calculus, arbitrary precision rationals, and algebra, still.

Interfacing C with Python is quite easy using Cython: I cannot resist giving you

a link.

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

I’m at a two-day short course on matroids at the US math meetings in New Orleans. I have been coding up some of the basic matroid types and constructions just as a way to learn more, and also looking at David Joyner’s code on the Sage ticket referenced above.

I’ll just echo Dima’s comments: you can prototype rapidly in Python with Sage and then easily speed it up once working. With linear algebra, finite fields, graph theory (isomorphism testing, matchings, connected components, cycle basis), and group theory all in Sage and fairly mature, you can build up working code quickly. You can interface with C libraries, translate Python to C with Cython, and talk to GAP. Cython lets you easily speed up critical sections of code. Seems like a natural place to locate a common home for bits and pieces of specialized packages and unify them with a common interface. And then you get maintenance and distribution for free.