#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|
84a81fdefe60c488faf9e4610c170c985e0c5f2f
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by Rudi):
Hi Chao,
somehow the inefficiency of components() became a major earworm for me
today, so I coded a more efficient version for BasisExchangeMatroid
(ticket #18591) to get it out of my system. The real inefficiency turned
out to be in the set union operations, and calculating with bitsets rather
than python sets works miracles for that.
I also felt a bit bad for luring you into my bad habits of premature code
optimization, but by just using my patch you can stay focussed on testing
correctness and enhancing functionality, which is probably better.
I realized why is_cosimple() is that much slower than is_simple() for
BinaryMatroids (and Ternary and Quaternary). There is a specialized ultra
fast method to get a fundamental cocircuit for such matroids, essentially
copying the row of a bitpacked matrix (which is a bitset) into another
bitset, which is the internal representation of the cocircuit. For
circuits you are back to touching each of the groundset elements one by
one, which is way slower. This asymmetry makes closure() faster that
coclosure, and in turn is_simple faster than is_cosimple. I still need to
see what is a clean way to solve that.
Rudi
--
Ticket URL: <http://trac.sagemath.org/ticket/18539#comment:18>
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.
