Opened 6 years ago

Closed 5 years ago

#12489 closed defect (fixed)

Fix equality of combinatorial free module on non totally ordered basis

Reported by: hivert Owned by: sage-combinat
Priority: critical Milestone: sage-5.0
Component: combinatorics Keywords: CombinatorialFreeModule, equality, Cernay2012
Cc: sage-combinat Merged in: sage-5.0.beta5
Authors: Nicolas M. Thiéry Reviewers: Florent Hivert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12490 Stopgaps:

Description (last modified by hivert)

The following is obviously wrong:

sage: F = CombinatorialFreeModule(QQ, Subsets([1,2,3]))
sage: x = F.an_element()
sage: x+0 == x
False
sage: x+F.zero() == x
False

The reason is

sage: (x+F.zero()).terms()  # random
[2*B[{1}], 3*B[{2}], B[{}]]
sage: x.terms()             # random
[2*B[{1}], B[{}], 3*B[{2}]]

Fixing equality testing also revealed a bug in sage.combinat.sf.dual: the conversion back from the dual basis did not strip cancelled terms from the dictionary. This conversion now uses dict_linear_combination which fixes the bug, factors out code and should be faster.

See also the possible optimization in #12508

Attachments (1)

trac_12489-freemod_eq-nt.patch (6.6 KB) - added by nthiery 6 years ago.

Download all attachments as: .zip

Change History (14)

comment:1 Changed 6 years ago by hivert

  • Dependencies set to #12490
  • Keywords Cernay2012 added

comment:2 Changed 6 years ago by hivert

  • Status changed from new to needs_review

comment:3 Changed 6 years ago by hivert

  • Status changed from needs_review to positive_review

I uploaded the patch on behalf of Nicolas and put a positive review since I'm Ok with it (the test suite is currently running).

Nicolas: I just put the correct trac ticket number and added one more test compared to your patch. I don't think this needs a new review.

comment:4 Changed 6 years ago by nthiery

  • Authors changed from Nicolas Thiery to Nicolas M. Thiéry

+1! Thanks for the review!

comment:5 follow-ups: Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work
sage -t --long "devel/sage-main/sage/combinat/sf/dual.py"
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/devel/sage-main/sage/combinat/sf/dual.py", line 33:
    sage: TestSuite(f).run()  # long time (11s on sage.math, 2011)
Expected nothing
Got:
    Failure in _test_one:
    Traceback (most recent call last):
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/local/lib/python/site-packages/sage/misc/sage_unittest.py", line 275, in run
        test_method(tester = tester)
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/local/lib/python/site-packages/sage/categories/monoids.py", line 126, in _tes
t_one
        tester.assert_(x * one == x)
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/local/lib/python2.7/unittest/case.py", line 420, in assertTrue
        raise self.failureException(msg)
    AssertionError: False is not true
[...]

comment:6 in reply to: ↑ 5 Changed 6 years ago by nthiery

Replying to jdemeyer:

sage -t --long "devel/sage-main/sage/combinat/sf/dual.py"
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/devel/sage-main/sage/combinat/sf/dual.py", line 33:
    sage: TestSuite(f).run()  # long time (11s on sage.math, 2011)
Expected nothing
Got:
    Failure in _test_one:
    Traceback (most recent call last):
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/local/lib/python/site-packages/sage/misc/sage_unittest.py", line 275, in run
        test_method(tester = tester)
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/local/lib/python/site-packages/sage/categories/monoids.py", line 126, in _tes
t_one
        tester.assert_(x * one == x)
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/local/lib/python2.7/unittest/case.py", line 420, in assertTrue
        raise self.failureException(msg)
    AssertionError: False is not true
[...]

Thanks for catching that. I am working on it. First thing, I am extracting the call to _test_associativity to only set # long on it, and not on the full testsuite (otherwise I would have caught the error myself). The other thing is that the new equality test highlighted a preexisting bug: x*f.one() contains zero coefficients in its dictionary.

comment:7 Changed 6 years ago by nthiery

  • Status changed from needs_work to needs_review

Changed 6 years ago by nthiery

comment:8 Changed 6 years ago by nthiery

  • Description modified (diff)

comment:9 in reply to: ↑ 5 Changed 6 years ago by hivert

Replying to jdemeyer:

sage -t --long "devel/sage-main/sage/combinat/sf/dual.py" [...]

AssertionError?: False is not true

}}}

Sorry for not catching this ealier ! I didn't launch the -long tests during my review.

comment:10 follow-up: Changed 6 years ago by hivert

Nicolas: using dict_linear_combination is clearly the good solution here. I'm testing all these and will get back to positive review if the tests pass. Do you have auto tests on sageange working the way we had on massena ?

Florent

comment:11 in reply to: ↑ 10 Changed 6 years ago by nthiery

Replying to hivert:

Nicolas: using dict_linear_combination is clearly the good solution here. I'm testing all these and will get back to positive review if the tests pass. Do you have auto tests on sageange working the way we had on massena ?

Yes, that's where I ran the test mentionned above. I'll put sage-combinat-commits in CC next time.

comment:12 Changed 6 years ago by hivert

  • Description modified (diff)
  • Status changed from needs_review to positive_review

I put back to positive review while waiting for the result of the tests.

comment:13 Changed 5 years ago by jdemeyer

  • Merged in set to sage-5.0.beta5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.