#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):
Replying to [comment:16 chaoxu]:
> > What part of your code is currently using most of the time on these
test cases?
> For the named cases, _corank and minor operation taking the most of the
time.
> For the small 3 connected binary matroids, most time was spent on
is_circuit, is_cosimple, is_simple.
> For matroids with large rank (I generated a random rank 500 binary
matroid), components take the most time.
> Here is an time breakdown for a rank 500 binary matroid.
>
Thanks for sending that data. The many calls to circuits() are probably
happening in the Matroids.components() routine. I think I may have written
that routine, and looks as if I did not really optimize it for speed.
- the method calls .circuit() in it's innermost loop, and then the use of
_circuit() is preferred. The underscored versions of Matroid methods do
the same as the original, but without the sanity checking of the input (in
this case, testing if the input is a set of elements from the ground set).
- `circuit()` is used to get a fundamental circuit, and I think we later
created that optimized method for that: `fundamental_circuit`
So the following slight tweak to `components()` may make a difference.
{{{
B = self.basis()
components = [frozenset([e]) for e in self.groundset()]
for e in self.groundset() - B:
C = self._fundamental_circuit(B,e)
components2 = []
for comp in components:
if (C & comp):
C = C | comp
else:
components2.append(comp)
components2.append(C)
components = components2
return components
}}}
The change is in line 4507, `C = self._fundamental_circuit(B,e)`. You
could also consider rewriting a bit more, use the above when `r(M) >
r^*(M)` and the dual version (cocircuits) in the other case. That way the
inner loop always has the least number of iterations. And if this routine
really stays a bottleneck, a bitpacked version is always an option.
Since your routine is_3connected_beta also computes fundamental
cocircuits, you would also gain a bit by using the unguarded
_fundamental_cocircuit. It is perhaps wasteful to compute those
fundamental cocircuits again in `components` and indirectly, in
`is_connected`. You could consider rewriting these routines so that they
take a set of fundamental circuits and/or a set of fundamental cociruits
as input.
There is no way that a single call to `is_cosimple` takes that much time.
That just cannot be right. It sometimes helps to also turn on the cython
profiler in other files.
I suspect the minor-taking is very expensive in your method, perhaps even
more so that the profiler reports. The routine
`sanitize_deletions_contractions` the guarded version uses is not that
fast, so it may help to avoid it here and there if you are sure about what
you're contracting is independent and what you're deleting is
coindependent.
Improving the inefficiency of `minor` itself is probably more involved,
and this would really deserve it's own ticket.
--
Ticket URL: <http://trac.sagemath.org/ticket/18539#comment:17>
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.
