#18539: faster matroid 3 connectivity
-------------------------------------+-------------------------------------
Reporter: chaoxu | Owner: chaoxu
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.8
Component: matroid theory | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/chaoxu/faster_matroid_3_connectivity|
0033334e6a0795d4e6033ac4721f3a8f432e7b55
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by Rudi):
Replying to [comment:12 chaoxu]:
> One can use the following code to test the running time of the current
implementation and the original one.
> {{{
> sage: %time bench(False)
> CPU times: user 298 ms, sys: 10.5 ms, total: 309 ms
> Wall time: 301 ms
> sage: %time bench(True)
> CPU times: user 36.9 ms, sys: 1.83 ms, total: 38.8 ms
> Wall time: 37.5 ms
> }}}
>
> I also benchmarked on 3-connected binary matroids
[https://groups.google.com/d/msg/sage-matroid/invXwv8SYsE/8tXA2hYUluEJ
listed here]. The old algorithm takes 925 ms, the new one takes 51 ms.
>
That really is very nice work. Cheers!
What part of your code is currently using most of the time on these test
cases?
> For correctness, I will try to see if the original and the new
implementation agrees for all matroids with at most 9 elements. (data from
[http://www-imai.is.s.u-tokyo.ac.jp/~ymatsu/matroid/index.html Database of
Matroids]).
I have attached the set of matroids on at most 9 elements, perhaps that
will save you some time translating their data. If you want I can also
send the Sage code I used to generate these matroids, just let me know.
--
Ticket URL: <http://trac.sagemath.org/ticket/18539#comment:13>
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.
