#18485: Make function to generate *all* independent sets.
-------------------------------------+-------------------------------------
Reporter: Rudi | Owner: Rudi
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/Rudi/make_function_to_generate__all__independent_sets_|
6347279565446a7fbdbec8755447b777056e5240
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by Rudi):
* commit: => 6347279565446a7fbdbec8755447b777056e5240
Comment:
The new function seems to work just fine.
{{{
sage: M=matroids.named_matroids.Q10()
sage: len(M.independent_sets())==sum([len(M.independent_r_sets(r)) for r
in range(M.full_rank()+1)])
True
sage: timeit("M.independent_sets()")
625 loops, best of 3: 467 µs per loop
sage: timeit("[M.independent_r_sets(r) for r in range(M.full_rank()+1)]")
625 loops, best of 3: 674 µs per loop
}}}
Other matroids give the same picture. There is some speedup (30-40%), but
nothing exceptional.
Q10 is a BasisExchangeMatroid, so independent_sets() and
independent_r_sets() above use bitsets, and that is where some of the
speed comes from.
I tried out Nathann's idea to use the hereditary-set code:
{{{
sage:def independent_sets_iterator(M):
from sage.combinat.subsets_hereditary import
subsets_with_hereditary_property
for x in
subsets_with_hereditary_property(M.is_independent,M.groundset()):
yield x
sage: timeit("list(independent_sets_iterator(M))")
125 loops, best of 3: 5.17 ms per loop
}}}
For a fair comparison, I should force the use Matroid.independent_sets()
instead of BasisExchangeMatroid.independent_sets(), so that you're not
just looking at the advantage of using bitsets.
{{{
sage: from sage.matroids.matroid import Matroid
sage: timeit("Matroid.independent_sets(M)")
625 loops, best of 3: 1.17 ms per loop
}}}
I will go and modify the code for M.independence_matroid_polytope().The
code will perhaps be more straightforward, but it will not matter much for
the efficiency. With the same matroid Q10, you get:
{{{
sage: timeit("M.independence_matroid_polytope()")
5 loops, best of 3: 109 ms per loop
}}}
So the amount of time spent on generating independent sets is already less
than 1%.
A somewhat bigger matroid is the binary Golay code on 24 elements. The
timings for that matroid are as follows:
{{{
sage: M=matroids.named_matroids.ExtendedBinaryGolayCode()
sage: len(M.independent_sets())
7898547
sage: timeit("M.independent_sets()")
5 loops, best of 3: 2.29 s per loop
sage: timeit("[M.independent_r_sets(r) for r in range(M.full_rank()+1)]")
5 loops, best of 3: 3.95 s per loop
sage: timeit("list(independent_sets_iterator(M))")
5 loops, best of 3: 92.1 s per loop
timeit("Matroid.independent_sets(M)")
5 loops, best of 3: 40 s per loop
}}}
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=6347279565446a7fbdbec8755447b777056e5240
6347279]||{{{Initial inplementation of Matroid.independent_sets() and
BasisExchangeMatroid.independent_sets()}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/18485#comment:10>
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.
