#11324: Bug in gale_ryser_theorem
-----------------------------+----------------------------------------------
Reporter: ncohen | Owner: wdj
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.7.1
Component: combinatorics | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
-----------------------------+----------------------------------------------
Old description:
> See the discussion at :
>
> https://groups.google.com/d/topic/sage-devel/IyrgvrLch4M/discussion
>
> Here is a patch implementing a new doctest checking for correction, but
> so far the ryser method still needs to be fixed !
>
> Nathann
New description:
See the discussion at :
https://groups.google.com/d/topic/sage-devel/IyrgvrLch4M/discussion
Here is a patch implementing a new doctest checking for correction, but so
far the ryser method still needs to be fixed !
Apply :
* trac_11324.3.patch
* trac_11324-reviewer.patch
Nathann
--
Comment(by 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... `:-)`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11324#comment:8>
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.
