#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|
3ea8ac5263fdc6d4a6fe9c5699fcfdf1942ade61
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by Rudi):
Correctness:
{{{
sage: N = Matroid(MatrixSpace(GF(2), 5,10).random_element())
sage: for X in subsets(N.groundset()):
for Y in subsets(N.groundset()-set(X)):
if not
BasisMatroid(N.minor(X,Y)).equals(BasisMatroid(N).minor(X,Y)):
print X,Y
....:
sage: N = Matroid(MatrixSpace(GF(3), 5,10).random_element())
sage: for X in subsets(N.groundset()):
for Y in subsets(N.groundset()-set(X)):
if not
BasisMatroid(N.minor(X,Y)).equals(BasisMatroid(N).minor(X,Y)):
print X,Y
....:
sage: N = Matroid(MatrixSpace(GF(4,x), 5,10).random_element())
sage: for X in subsets(N.groundset()):
for Y in subsets(N.groundset()-set(X)):
if not
BasisMatroid(N.minor(X,Y)).equals(BasisMatroid(N).minor(X,Y)):
print X,Y
}}}
Efficiency before patch:
{{{
sage: M = Matroid(MatrixSpace(GF(2), 200,400).random_element())
sage: B = M.basis()
sage: timeit("for e in B: M.delete(M._fundamental_cocircuit(B,e))")
5 loops, best of 3: 261 ms per loop
sage: M = Matroid(MatrixSpace(GF(3), 200,400).random_element())
sage: B = M.basis()
sage: timeit("for e in B: M.delete(M._fundamental_cocircuit(B,e))")
5 loops, best of 3: 7.13 s per loop
sage: M = Matroid(MatrixSpace(GF(4,x), 200,400).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.95 s per loop
}}}
Efficiency after patch:
{{{
sage: M = Matroid(MatrixSpace(GF(2), 200,400).random_element())
sage: B = M.basis()
sage: timeit("for e in B: M.delete(M._fundamental_cocircuit(B,e))")
5 loops, best of 3: 73.7 ms per loop
sage: M = Matroid(MatrixSpace(GF(3), 200,400).random_element())
sage: B = M.basis()
sage: timeit("for e in B: M.delete(M._fundamental_cocircuit(B,e))")
5 loops, best of 3: 86.7 ms per loop
sage: M = Matroid(MatrixSpace(GF(4,x), 200,400).random_element())
sage: B = M.basis()
sage: timeit("for e in B: M.delete(M._fundamental_cocircuit(B,e))")
5 loops, best of 3: 86.4 ms per loop
}}}
For TernaryMatrix and QuaternaryMatrix, there was no optimized submatrix-
code to begin with, hence the 40 - 80 times speedup.
I scaled down the size of the matrix a bit, the ternary benchmark simply
wouldn't finish for 500x1000.
I will remove some lingering cython profile directives, and then I'm done.
--
Ticket URL: <http://trac.sagemath.org/ticket/18660#comment:5>
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.
