Some basics..

[Gordon]

In the course of writing my series (well, two so far) of blog posts, I am coming up against some issues and implementation details that I'd like to clarify before I mislead my readers (even though it's probably just Rob).

Here is something that I would like to work, but it doesn't...

sage: bk4 = BinaryMatroid(k4)
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-82-4599fb5975ca> in <module>()
----> 1 bk4 = BinaryMatroid(k4)

/Applications/sage/local/lib/python2.7/site-packages/sage/matroids/linear_matroid.so in sage.matroids.linear_matroid.BinaryMatroid.__init__ (sage/matroids/linear_matroid.c:28636)()

AttributeError: 'sage.matroids.linear_matroid.RegularMatroid' object has no attribute 'nrows'

I can do it like this, but it seems a bit clunky

sage: bk4 = BinaryMatroid(k4.representation())
sage: bk4
Binary matroid of rank 3 on 6 elements, type (2, 7)

[Gordon]

Oops...forgot this, which comes before

sage: k4 = Matroid(graphs.CompleteGraph(4))
sage: k4

[Stefan van Zwam]

Hi Gordon,

> Here is something that I would like to work, but it doesn't...
>
> sage: bk4 = BinaryMatroid(k4)

Yes... we simply haven't gotten around to implementing this, probably because it is quite specific to binary matroids (you can do it for ternary, and with a lot of effort for quaternary, but after that you're out of luck).

> I can do it like this, but it seems a bit clunky
>
> sage: bk4 = BinaryMatroid(k4.representation())
> sage: bk4
> Binary matroid of rank 3 on 6 elements, type (2, 7)

Still, that's the way to go for now... another option that might be expected to work, but doesn't, is this:

sage: bk4 = Matroid(field=GF(2), matroid=k4)

Incidentally, my favorite way would be to do

sage: bk4 = Matroid(field=GF(2), matrix=k4.representation())

because then you don't have to import the advanced stuff, which is really unnecessary for these basic examples.

> Some more questions based on the following data - basically, what is determining the time taken?
>
> Is there a reason why has_minor does not call has_field_minor if both matroids are BinaryMatroids?

The reason is that we haven't implemented it. More seriously, has_minor has almost no optimizations, and is still a far cry from Macek's implementation.

> sage: pet_regular = Matroid(graphs.PetersenGraph())
> sage: pet_basis = BasisMatroid(pet_regular)
> sage: pet_binary = BinaryMatroid(pet_regular.representation())
> sage: fano_binary = matroids.named_matroids.Fano()
> sage: fano_basis = BasisMatroid(fano_binary)
>
> sage: %time pet_regular.has_minor(fano_binary)
> CPU times: user 8.16 s, sys: 0.01 s, total: 8.16 s
> Wall time: 8.16 s
> False
> sage: %time pet_regular.has_minor(fano_basis)
> CPU times: user 8.12 s, sys: 0.00 s, total: 8.12 s
> Wall time: 8.12 s
> False
> sage: %time pet_binary.has_minor(fano_binary)
> CPU times: user 6.51 s, sys: 0.06 s, total: 6.57 s
> Wall time: 6.52 s
> False
> sage: %time pet_binary.has_minor(fano_basis)
> CPU times: user 6.66 s, sys: 0.00 s, total: 6.66 s
> Wall time: 6.66 s
> False
> sage: %time pet_basis.has_minor(fano_basis)
> CPU times: user 10.21 s, sys: 0.00 s, total: 10.22 s
> Wall time: 10.22 s
> False
> sage: %time pet_basis.has_minor(fano_binary)
> CPU times: user 14.74 s, sys: 0.01 s, total: 14.75 s
> Wall time: 14.75 s
> False
> sage: pet_binary.has_field_minor(fano_binary)
> False
> sage: %time pet_binary.has_field_minor(fano_binary)
> CPU times: user 3.16 s, sys: 0.04 s, total: 3.19 s
> Wall time: 3.16 s
> False

I'm a bit surprised that basis_matroid is so much slower, but my guess is that it's much more expensive to create a minor in that class.

--Stefan.