#11324: Bug in gale_ryser_theorem
-----------------------------+----------------------------------------------
Reporter: ncohen | Owner: wdj
Type: defect | Status: needs_work
Priority: major | Milestone: sage-4.7.1
Component: combinatorics | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
-----------------------------+----------------------------------------------
Changes (by wdj):
* status: needs_review => needs_work
Comment:
Replying to [comment:8 ncohen]:
> Hello !
>
> David and I talked about it over emails, but even though the patch fixes
the bug there is now a large difference in speed between the two
algorithms.
>
> Using the test function defined in the docstring, it gives :
>
> {{{
> sage: %timeit test_algorithm("ryser", 10, 20)
> 5 loops, best of 3: 2.25 s per loop
> sage: %timeit test_algorithm("gale", 10, 20)
> 5 loops, best of 3: 29.2 ms per loop
> }}}
>
> It is probable that this implementation could be greatly improved, at
least by rewriting it in Cython, but as it could take some time and as
this already comes from a nasty bug that has been noticed in the Graph
library, perhaps the best is to have a quick fix for now.
>
> With this patch, the default algorithm is moved to "gale", and I also
edited a part of the docstring which did not make sense anymore, now that
GLPK is by default included in Sage.
>
> If you can review my patch, or if you found a wonderful way to get its
former speed's back in between... `:-)`
In principle, your patch is good. It reads fine. However, when you change
the default,
the output can change, at least in cases when there is some symmetry in
one or both of the partitions. In this case, I am getting some new
docstring failures. Can you please check those and fix them too?
>
> Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11324#comment:9>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
