Bug in gale_ryser_theorem

[nathanncohen]

See the discussion at :

https://groups.google.com/d/topic/sage-devel/IyrgvrLch4M/discussion

Apply :

• trac_11324.3.patch
• trac_11324-reviewer.patch

Nathann

CC: @wdjoyner

Component: combinatorics

Author: David Joyner

Reviewer: Nathann Cohen

Merged: sage-4.7.2.alpha4

Issue created by migration from https://trac.sagemath.org/ticket/11324

[nathanncohen]

Attachment: trac_11324.patch.gz

[wdjoyner]

comment:1

What bug? The above thread seems to simply state that the DegreeSequenceBipartite method was implemented wrong.

[wdjoyner]

comment:2

Nathann explained the bug and I think I found the fix. I'm testing and hope to post a patch soon.

[wdjoyner]

standalone patch, applies to 4.7.rc1

[wdjoyner]

comment:3

Attachment: trac_11324.2.patch.gz

[wdjoyner]

comment:4

I added a patch which rewrites _slider01 and seems to fix the bug. It has commented out print statements, which need to be removed. I left them in though, since they are easy to remove. My patch passes docstring tests. I also aded the tests that check that the original bug report found.

I also looked at and tested the docstring patch of Nathann.It looks good to me and passes tests.

[nathanncohen]

comment:7

Hellooooo !!!

I've been trying to apply your patch with all the possible orderings, but I can't get it to pass ^^;

Among other things there is a "fixedcol" variable in your .3 patch that I don'tsee appearing in the original file, nor in my patch nor in your .2 ^^;

Nathann

[wdjoyner]

Attachment: trac_11324.3.patch.gz

apply only this patch

[nathanncohen]

comment:8

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

[wdjoyner]

comment:9

Replying to @nathanncohen:

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

[nathanncohen]

comment:10

Oopssssss.... Fixed !

I instead set the algorithm in these doctests to "ryser", as it is much less sensible to numerical noise than Gale's, which uses GLPK (or CPLEX when installed).

Nathann

[wdjoyner]

comment:11

Replying to @nathanncohen:

Oopssssss.... Fixed !

I instead set the algorithm in these doctests to "ryser", as it is much less sensible to numerical noise than Gale's, which uses GLPK (or CPLEX when installed).

Nathann

That works now. I give the reviewer patch a positive review.

Nathann, I'll leave the final decision to you. Thanks for the help!

[nathanncohen]

comment:12

Oh ! Then all's good to go :-)

And by the way, you did all the hard stuff on this ticket, so thanks to you !! ^^;

Nathann

[jdemeyer]

Author: David Joyner

[jdemeyer]

Reviewer: Nathann Cohen

[jdemeyer]

Merged: sage-4.7.1.alpha3

[jdemeyer]

comment:15

The description says "Here is a patch implementing a new doctest checking for correction, but so far the ryser method still needs to be fixed !". Is this up-to-date? If yes, why adding a doctest for a broken method?

In any case, this needs work. On a Mac OS X 10.4 PPC system, I can easily reproduce the following:

sage -t -long -force_lib "devel/sage/sage/combinat/integer_vector.py"
**********************************************************************
File "/Users/jdemeyer/sage-4.7.1.alpha3/devel/sage/sage/combinat/integer_vector.py", line 340:
    sage: for algorithm in ["gale", "ryser"]:                            # long time
         for i in range(Integer(50)):                                         # long time
            if not test_algorithm(algorithm, Integer(3), Integer(10)):                 # long time
                print "Something wrong with algorithm ", algorithm   # long time
                break                                                # long time
Exception raised:
    Traceback (most recent call last):
      File "/Users/jdemeyer/sage-4.7.1.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/jdemeyer/sage-4.7.1.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/jdemeyer/sage-4.7.1.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_3[28]>", line 3, in <module>
        if not test_algorithm(algorithm, Integer(3), Integer(10)):                 # long time
      File "<doctest __main__.example_3[27]>", line 7, in test_algorithm
        ss1 = sorted(map(lambda x : sum(x) , m.rows()), reverse = True)
    AttributeError: 'bool' object has no attribute 'rows'
**********************************************************************

The error does not show up every time, but let's say 1 time of out 5 tests.

[jdemeyer]

Changed merged from sage-4.7.1.alpha3 to none

[nathanncohen]

comment:18

Gloops... :-/

This was an old bug, without any link to what we were adressing now. The problem appeared when the function was given as an entry containing only vectors [0]*n. I fixed that in my updated patch, and ran the test..... MANY times :-)

David ? Are you still around ? :-)

Nathann

[nathanncohen]

Attachment: trac_11324-reviewer.patch.gz

[nathanncohen]

comment:19

Ping ?

[wdjoyner]

comment:20

Replying to @nathanncohen:

Gloops... :-/

...

David ? Are you still around ? :-)

Sorry for the delay.

The reviewer's patch applies (on top of the previous patch) fine on 4.7.1.rc1.
It passes all tests. I read through the patch itself which is mostly docstring fixes but also implements the trivial case of the 0 matrix (which a corresponding added doctest).

Thanks Nathann!

Nathann

[nathanncohen]

comment:21

Thaaaaaaaanks :-)

[jdemeyer]

Merged: sage-4.7.2.alpha4