#18784: Tutte connectors for matroids
-------------------------------------+-------------------------------------
Reporter: Rudi | Owner: Rudi
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.8
Component: matroid theory | Resolution:
Keywords: | Merged in:
Authors: Rudi Pendavingh | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/Rudi/tutte_connectors_for_matroids|
9df1cf15e77161940b29d3cbe75fb89f4f463223
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by Rudi):
* status: needs_work => needs_review
Comment:
Well, I can't seem to merge or rebase on develop without going to an
earlier version than beta6. Anyway, I realise now that rebasing won't
help, that the one patchbot was unhappy about something unrelated to this
ticket.
I did realise one more efficiency tweak which may actually help to speed
up the test for k-connectedness as well. So have a look.
When _is_3connected_CE was based on matroid intersection it was quite a
bit slower that _is_3connected_BC, now the picture is this:
{{{
sage: for i in range (10):
M = Matroid(MatrixSpace(GF(2), i*10, i*20).random_element())
print i, M
timeit("M._is_3connected_BC()")
timeit("M._is_3connected_CE()")
....:
0 Binary matroid of rank 0 on 0 elements, type (0, 0)
625 loops, best of 3: 129 ns per loop
625 loops, best of 3: 147 ns per loop
1 Binary matroid of rank 10 on 20 elements, type (1, None)
625 loops, best of 3: 1.09 ms per loop
625 loops, best of 3: 704 µs per loop
2 Binary matroid of rank 20 on 40 elements, type (1, 1)
625 loops, best of 3: 1.38 ms per loop
125 loops, best of 3: 2.82 ms per loop
3 Binary matroid of rank 30 on 60 elements, type (1, 5)
125 loops, best of 3: 1.95 ms per loop
125 loops, best of 3: 6.57 ms per loop
4 Binary matroid of rank 40 on 80 elements, type (1, None)
125 loops, best of 3: 3.28 ms per loop
25 loops, best of 3: 13.8 ms per loop
5 Binary matroid of rank 50 on 100 elements, type (1, 3)
125 loops, best of 3: 5.09 ms per loop
25 loops, best of 3: 23.8 ms per loop
6 Binary matroid of rank 60 on 120 elements, type (0, 0)
125 loops, best of 3: 7.31 ms per loop
25 loops, best of 3: 39.3 ms per loop
7 Binary matroid of rank 70 on 140 elements, type (2, None)
25 loops, best of 3: 9.87 ms per loop
5 loops, best of 3: 61.5 ms per loop
8 Binary matroid of rank 80 on 160 elements, type (0, 6)
25 loops, best of 3: 12.7 ms per loop
5 loops, best of 3: 90.7 ms per loop
9 Binary matroid of rank 90 on 180 elements, type (0, 0)
25 loops, best of 3: 16.4 ms per loop
5 loops, best of 3: 122 ms per loop
}}}
So on a matroid on n elements, CE is about n/10 times slower than BC.
--
Ticket URL: <http://trac.sagemath.org/ticket/18784#comment:21>
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.
