#18946: unweighted matroid intersection using blocking flow approach
-------------------------------------+-------------------------------------
Reporter: chaoxu | Owner:
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-6.8
Component: matroid theory | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: u/chaoxu/faster- | Commit:
abstract-matroid-intersection | c9fb292e9d2155ddc647e83970204a256ae53b3f
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by chaoxu):
* status: new => needs_review
Comment:
Here is a run time comparison if the maximum common independent set is
large.
{{{
sage: M = Matroid(MatrixSpace(GF(2), 1000,1000).random_element())
sage: N = Matroid(MatrixSpace(GF(2), 1000,1000).random_element())
sage: %time len(M.intersection(N))
CPU times: user 446 ms, sys: 2.05 ms, total: 448 ms
Wall time: 450 ms
998
sage: %time len(M._intersection_unweighted(N))
CPU times: user 316 ms, sys: 569 us, total: 317 ms
Wall time: 317 ms
998
}}}
I have done tests on random matroids and `intersection(N)` seems to
`_intersection_unweighted(N)`. so far so good.
--
Ticket URL: <http://trac.sagemath.org/ticket/18946#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.
