#18660: Improve efficiency of minors() for BinaryMatroid, TernaryMatroid,
QuaternaryMatroid
-------------------------------------+-------------------------------------
Reporter: Rudi | Owner: Rudi
Type: task | 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/Rudi/improve_efficiency_of_minors___for_binarymatroid__ternarymatroid__quaternarymatroid|
7deb135d390d4a83ab1fff1742c0015b5b5194ef
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by Rudi):
* commit: => 7deb135d390d4a83ab1fff1742c0015b5b5194ef
Comment:
First worked on BinaryMatroid and BinaryMatrix. The new code seems to be
correct:
{{{
sage: N = Matroid(MatrixSpace(GF(2), 5,12).random_element())
sage: for X in subsets(N.groundset()):
if not BasisMatroid(N\X).equals(BasisMatroid(N)\X):
print X
}}}
It's more efficient too. Without the patch:
{{{
sage: M = Matroid(MatrixSpace(GF(2), 500,1000).random_element())
sage: B = M.basis()
sage: timeit("for e in B: M.delete(M._fundamental_cocircuit(B,e))")
5 loops, best of 3: 3.69 s per loop
}}}
With the patch:
{{{
sage: M = Matroid(MatrixSpace(GF(2), 500,1000).random_element())
sage: B = M.basis()
sage: timeit("for e in B: M.delete(M._fundamental_cocircuit(B,e))")
5 loops, best of 3: 692 ms per loop
}}}
So, about 5 times faster on this example. This is not all due to the trick
announced in the ticket. Replacing a list by a c-style array here and
there did some good too. And just replacing the line
{{{
C = [c for c in range(len(self._E)) if self._E[c] not in deletions |
contractions]
}}}
in `_minor` by something that does not compute the union `deletions |
contractions` ''for each c'' made the code 2 times faster right there.
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=7deb135d390d4a83ab1fff1742c0015b5b5194ef
7deb135]||{{{Added new method for taking submatrix of a BinaryMatrix, used
in BinaryMatroid._minor()}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/18660#comment:3>
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.
