Opened 7 years ago

Closed 6 years ago

#14014 closed enhancement (fixed)

Update matrix groups to new Parents, libGAP.

Reported by: vbraun Owned by: joyner
Priority: major Milestone: sage-5.11
Component: group theory Keywords:
Cc: roed, dimpase, slabbe Merged in: sage-5.11.beta0
Authors: Volker Braun Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14187, #14323, #14284, #14640 Stopgaps:

Description (last modified by tscrim)

This patch adds support for cyclotomics and matrices to LibGAP. And rewrites the matrix groups on top of that.

Follow-up: #14039.

Attachments (7)

trac_14014_deletions.patch (32.5 KB) - added by vbraun 7 years ago.
Initial patch
trac_14014_parents_group_dependents.patch (42.8 KB) - added by vbraun 6 years ago.
Updated patch
trac_14014_parents_for_matrix_groups.patch (227.0 KB) - added by vbraun 6 years ago.
Updated patch
trac_14014_libgap_cyclotomic_matrix.patch (65.5 KB) - added by vbraun 6 years ago.
Updated patch
trac_14014_iterator.patch (26.2 KB) - added by vbraun 6 years ago.
Updated patch
trac_14014_misc.patch (2.3 KB) - added by vbraun 6 years ago.
Initial patch
trac_14014-review-ts.patch (17.2 KB) - added by tscrim 6 years ago.

Download all attachments as: .zip

Change History (60)

comment:1 Changed 7 years ago by vbraun

  • Dependencies set to #14015

comment:2 Changed 7 years ago by vbraun

  • Dependencies #14015 deleted

comment:3 Changed 7 years ago by vbraun

  • Description modified (diff)

comment:4 Changed 7 years ago by vbraun

  • Authors set to Volker Braun
  • Description modified (diff)
  • Status changed from new to needs_review

comment:5 Changed 7 years ago by vbraun

  • Cc roed added

comment:6 Changed 7 years ago by vbraun

  • Dependencies set to #14187

Changed 7 years ago by vbraun

Initial patch

comment:7 Changed 7 years ago by vbraun

  • Description modified (diff)

Split into bit-sized pieces ;-)

comment:8 Changed 7 years ago by vbraun

  • Description modified (diff)
  • Reviewers set to David Roe

comment:9 Changed 7 years ago by dimpase

  • Cc dimpase added

is there a trac ticket for libgap-4.5.7.p2.spkg ?

comment:10 Changed 7 years ago by dimpase

Does it handle GAP's BlockMatrix? ? This would allow a seamless interface between Sage's sparse matrices and GAP, as BlockMatrix? can be used as a sparse matrix:

gap> n:=10^16;
10000000000000000
gap> a:=BlockMatrix([[1,2,[[5]]]],n,n);
<block matrix of dimensions (10000000000000000*1)x(10000000000000000*1)>
gap> 

comment:11 Changed 7 years ago by vbraun

This is the track ticket for libgap-4.5.7.p2.spkg. It does not handle GAP's blockmatrix special, that is, they currently become dense matrices in Sage. Please open another ticket for feature requests.

comment:12 Changed 7 years ago by jdemeyer

  • Description modified (diff)

comment:13 Changed 7 years ago by jdemeyer

  • Dependencies changed from #14187 to #14187, #14323
  • Description modified (diff)

Moving the spkg-update to #14323.

comment:14 Changed 7 years ago by dimpase

I started to look at sage/groups/libgap_wrapper.pyx, and wonder what the following two lines would do:

sage: G.<a,b> =FreeGroup()
sage: G
Free Group on generators {a, b}

there was a doctest like this, marked "# indirect doctest", but it's removed by this patch. Shouldn't one just remove the "# indirect doctest"? Or does G stand from something weird now?

Can we have a bit longer explanation of what happens on this ticket. Do matrix groups get libGAP as the default backend, while the old one remains available as G.gap() ?

Last edited 7 years ago by dimpase (previous) (diff)

comment:15 Changed 7 years ago by dimpase

Is it assumed in libGAP that GAP long integers are GMP/MPIR integers? For there is the following comment in the patch, in sage/libs/gap/element.pyx, lines 1150-2:

 An immediate integer is one that is stored as a C integer, and 
 is subject to the usual size limits. Larger integers are 
 stored in GAP as GMP integers.

Or it actually just calls the appropriate GAP long integer functions? Note that GAP itself allows for different long integer backends, e.g. it has its own implementation of them, used exclusively before version 4.5, although Sage does not use this.

Whatever it is, it should be possible to discover without reading the full source.

comment:16 Changed 7 years ago by dimpase

for some reason I get

sage -t --long sage/groups/matrix_gps/morphism.py
**********************************************************************
File "sage/groups/matrix_gps/morphism.py", line 319, in sage.groups.matrix_gps.morphism.MatrixGroupMorphism_im_gens._call_
Failed example:
    f(O)  # long time
Expected:
    Matrix group over Rational Field with 6 generators: 
     [[[1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 1]], [[1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 1]], [[1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 1, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 1]], [[0, 0, 0, 0, -1, 0], [0, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [-1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1]], [[0, 0, 0, 0, 0, 1], [0, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 1, 0], [1, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, -1], [0, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 1, 0], [-1, 0, 0, 0, 0, 0]]]
Got:
    Matrix group over Rational Field with 6 generators
**********************************************************************
1 item had failures:
   1 of  19 in sage.groups.matrix_gps.morphism.MatrixGroupMorphism_im_gens._call_
    [67 tests, 1 failure, 53.2 s]

Is it just me, a side effect of some crap in patch queue?

comment:17 Changed 7 years ago by dimpase

Something I don't get happens in sage/groups/matrix_gps/orthogonal.py. You changed docstring to say

The general orthogonal group `GO(n,R)` consists of all orthogonal 
 `n\times n` matrices over the ring `R`.

but it doesn't always work, as for finite fileds it's still the same GAP backend:

sage: GO(6,GF(3))
...
ValueError: must have e=-1 or e=1 for even degree

IMHO, speaking about the orthogonal group over a ring is not right. Generally speaking one would have lots of inequivalent bilinear scalar products to choose from, leading to different groups. Even in physics, where the Lorenz group is an example of this...

In fact, the behaviour of even dimension orthogonal groups over a field is not so special in the finite field case. This is just a manifestation of the fact that there are two Dynkin diagrams (or Lie algebras) giving such groups, namely B_n (you get e=-1) and D_n (you get e=1).

Last edited 7 years ago by dimpase (previous) (diff)

comment:18 follow-up: Changed 7 years ago by vbraun

comment:14

This is the _repr_ doctests, which previously was incorrectly labelled as indirect doctest. In fact, it just showed the output that was generated in a derived class. I replaced it with an explict doctest that actually tests ParentLibGAP._repr_.

My goal is to replace the GAP interface with LibGAP everywhere. During the transition the gap() method will return the wrapped object, which may be in the GAP interface or in LibGAP.

comment:15

I just want to allow the GMP backend for long integers, I don't think we gain anything from trying to support the old home-grown one. Though at this point you can still use both, the conversion from long integers to Sage is done via strings. But I'd like to change that in the future and directly access the GMP limbs.

The libgap before this ticket doesn't handle long its correctly because I didn't understand what GAP docs mean by "immediate integers". This is why I wrote the explanatory comment.

comment:16

That file has been renamed to just morphism.py, if you have all patches you might have to run sage -sync-build

comment:17

I agree that there is no unique bilinear scalar form, though I would call the orthogonal group (in absence of any further qualifiers) over a ring the one with the standard (identity matrix) bilinear form. In particular since the orthogonal groups for other bilinear forms have sometimes other names, as you said. The next paragraph explains how the notation for finite fields differ, so I think thats clear enough:

The general orthogonal group `GO(n,R)` consists of all orthogonal 
`n\times n` matrices over the ring `R`.  

In the case of a finite field and if the degree `n` is even, then 
there are two inequivalent quadratic forms and a third parameter 
``e`` must be specified to disambiguate these two possibilities. 

My aim was to start the docstring with a friendly paragraph that says what GO/SO is before hitting the user with the finite field technicalities.

Last edited 7 years ago by vbraun (previous) (diff)

comment:19 in reply to: ↑ 18 Changed 7 years ago by dimpase

Replying to vbraun:

comment:15

I just want to allow the GMP backend for long integers, I don't think we gain anything from trying to support the old home-grown one.

I agree, I'm just asking for a bit more explanation there.

Though at this point you can still use both, the conversion from long integers to Sage is done via strings. But I'd like to change that in the future and directly access the GMP limbs.

The libgap before this ticket doesn't handle long its correctly because I didn't understand what GAP docs mean by "immediate integers". This is why I wrote the explanatory comment.

comment:16

That file has been renamed to just morphism.py, if you have all patches you might have to run sage -sync-build

Hmm, I tried, and it didn't help. I'll build a pristine installation of Sage and test this there.

No, no luck on this one. I just built 5.9.beta1, installed the libgap spkg from #14323, and applied the patches from #14187 and from this ticket, and still have the same failure

comment:17

I agree that there is no unique bilinear scalar form, though I would call the orthogonal group (in absence of any further qualifiers) over a ring the one with the standard (identity matrix) bilinear form.

Actually, it's not even correct to talk about bilinear forms; one should talk about quadratic forms, in case you do not want to exclude the case of fields of characteristic 2 (it's more or less a coincidence that in other characteristics the automorphisms of the associate bilinear form coincide with the (linear) automorphisms of the quadratic form.

As well, in characteristic 2 orthogonal matrices have little to do with orthogonal groups; indeed they fix the quadratic form f(X)=<X,X>, but this form is (sesqu)linear, i.e. f(aX+bY)=<aX+bY,aX+bY>=a^2 <X,X>+b^2<Y,Y>+2<aX,bY>= a^2<X,X>+b^2<Y,Y>, and this is not a one one cares much about. The ones which are interesting cannot even be diagonalized.

And what happens for rings in general is much more mysterious, even for ZZ. I don't know much about this topic, but number theorists might start pulling their hairs out upon reading this part; already binary quadratic forms over ZZ are a big topic.

In particular since the orthogonal groups for other bilinear forms have sometimes other names, as you said. The next paragraph explains how the notation for finite fields differ, so I think thats clear enough:

The general orthogonal group `GO(n,R)` consists of all orthogonal 
`n\times n` matrices over the ring `R`.  

In the case of a finite field and if the degree `n` is even, then 
there are two inequivalent quadratic forms and a third parameter 
``e`` must be specified to disambiguate these two possibilities. 

My aim was to start the docstring with a friendly paragraph that says what GO/SO is before hitting the user with the finite field technicalities.

One has to start with a correct paragraph (see above). It's also strange to see that 'in case of finite fields' clarification. Orthogonal groups over fields are a family of classical groups, which are the same as the D_n and B_n groups "of Lie type". And for the latter there will be two different groups for n even, something like this. Another way to talk about them is to talk about automorphism groups of nondegenerate quadratic forms, and for each class of equivalent forms one will have its "own" orthogonal group.

Last edited 7 years ago by dimpase (previous) (diff)

comment:20 Changed 7 years ago by dimpase

No luck on the comment 16 problem. I just built 5.9.beta1, installed the libgap spkg from #14323, and applied the patches from #14187 and from this ticket, did sage -synch-build and sage -b and still have the same failure on sage/groups/matrix_gps/morphism.py. I have

dima@arando:~/sage/sage-5.9.beta1/devel/sage$ hg qapp
trac_14187_lazy_import_test.patch
trac_14187_lazy_everywhere.patch
trac_14014_libgap_cyclotomic_matrix.patch
trac_14014_deletions.patch
trac_14014_parents_for_matrix_groups.patch
trac_14014_parents_group_dependents.patch

and libgap-4.5.7.p2 from #14323. (It's on arando from the buildbot, by the way).

Last edited 7 years ago by dimpase (previous) (diff)

comment:21 follow-up: Changed 7 years ago by vbraun

Updated patch fixes the problem from comment:16, which hides behind a # long time.

I also updated the orthogonal matrix docstrings, hopefully it is now correct even in characteristic two.

comment:22 in reply to: ↑ 21 Changed 7 years ago by dimpase

Replying to vbraun:

Updated patch fixes the problem from comment:16, which hides behind a # long time.

line 329 of morphism.py should be

            <BLANKLINE>

not the empty line. now this doctest is still broken.

Last edited 7 years ago by dimpase (previous) (diff)

comment:23 Changed 7 years ago by dimpase

There are also doctest failures in sage/categories/groups.py, sage/combinat/backtrack.py, sage/combinat/partition.py. Did you look at these?

In sage/combinat/root_system/weyl_group.py. In the latter the fix is trivial: replace [] by ():

sage -t --long devel/sage/sage/combinat/root_system/weyl_group.py
**********************************************************************
File "devel/sage/sage/combinat/root_system/weyl_group.py", line 311, in sage.combinat.root_system.weyl_group.WeylGroup.gens
Failed example:
    G.gens()
Expected:
    [
    [0 1 0 0]  [1 0 0 0]  [1 0 0 0]
    [1 0 0 0]  [0 0 1 0]  [0 1 0 0]
    [0 0 1 0]  [0 1 0 0]  [0 0 0 1]
    [0 0 0 1], [0 0 0 1], [0 0 1 0]
    ]
Got:
    (
    [0 1 0 0]  [1 0 0 0]  [1 0 0 0]
    [1 0 0 0]  [0 0 1 0]  [0 1 0 0]
    [0 0 1 0]  [0 1 0 0]  [0 0 0 1]
    [0 0 0 1], [0 0 0 1], [0 0 1 0]
    )

Also devel/sage/sage/libs/gap/libgap.pyx (forgot to lazify):

sage -t --long devel/sage/sage/libs/gap/libgap.pyx
**********************************************************************
File "devel/sage/sage/libs/gap/libgap.pyx", line 460, in sage.libs.gap.libgap.Gap.__init__
Failed example:
    type(libgap)
Expected:
    <class 'sage.libs.gap.libgap.Gap'>
Got:
    <type 'sage.misc.lazy_import.LazyImport'>

And a number of similar failures in devel/sage/sage/misc/lazy_import.pyx.

I also get timeouts in sage/sage/combinat/backtrack.py and sage/modular/arithgroup/arithgroup_perm.py.

comment:24 Changed 7 years ago by vbraun

The new doctesting framework doesn't seem to work with some of the lazy_import improvements in #14187. So let's just forget about trac_14187_lazy_everywhere.patch for now. I also updated the other patch on #14187, as explained there.

With that and the updated patches all doctests pass (normal&long) again on sage-5.9.beta1

comment:25 Changed 7 years ago by vbraun

  • Dependencies changed from #14187, #14323 to #14187, #14323, #14284

Needs to be rebased for the upcoming sage-5.9.beta2 due to #14284

comment:26 Changed 7 years ago by vbraun

  • Description modified (diff)

The last patch improves the iterator for matrix groups, see also http://tracker.gap-system.org/issues/369.

Now all tests pass again on sage-5.9.beta2, including the new category code that checks consistency between __iter__() and list().

Changed 6 years ago by vbraun

Updated patch

comment:27 Changed 6 years ago by vbraun

Rebased for the updated patch in #14187

Changed 6 years ago by vbraun

Updated patch

Changed 6 years ago by vbraun

Updated patch

comment:28 Changed 6 years ago by vbraun

Patches rebased for sage-5.10.beta1

comment:29 Changed 6 years ago by Snark

  • Status changed from needs_review to needs_work

trac_14014_iterator.patch doesn't apply correctly in sage-5.10.beta2

comment:30 Changed 6 years ago by vbraun

Works for me. Are you sure? The patchbot gets the order wrong as usual...

Patchbot: Apply trac_14014_libgap_cyclotomic_matrix.patch, trac_14014_deletions.patch, trac_14014_parents_for_matrix_groups.patch, trac_14014_parents_group_dependents.patch, trac_14014_iterator.patch

comment:31 Changed 6 years ago by Snark

Ah, I got the order wrong ; they apply with only small fuzz now.

Notice that I'm trying this with the packages and the patch from #14039 (with big fuzz) ; the compilation goes well, but I have failures in sage.games.quantumino:

Running doctests with ID 2013-05-14-13-08-28-8b625de0.
Doctesting 1 file.
sage -t --long devel/sage/sage/games/quantumino.py
**********************************************************************
File "devel/sage/sage/games/quantumino.py", line 82, in sage.games.quantumino
Failed example:
    for p in s: p                                   # long time (<1s)
Expected:
    Polyomino: [(0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (1, 2, 0)], Color: d
eeppink
    Polyomino: [(0, 0, 1), (0, 1, 0), (0, 1, 1), (0, 2, 1), (1, 2, 1)], Color: d
eeppink
    Polyomino: [(0, 2, 0), (0, 3, 0), (0, 4, 0), (1, 4, 0), (1, 4, 1)], Color: g
reen
    Polyomino: [(0, 3, 1), (1, 3, 1), (2, 2, 0), (2, 2, 1), (2, 3, 1)], Color: g
reen
    Polyomino: [(1, 3, 0), (2, 3, 0), (2, 4, 0), (2, 4, 1), (3, 4, 0)], Color: r
ed
    Polyomino: [(1, 0, 1), (2, 0, 1), (2, 1, 0), (2, 1, 1), (3, 1, 1)], Color: r
ed
    Polyomino: [(2, 0, 0), (3, 0, 0), (3, 0, 1), (3, 1, 0), (4, 0, 0)], Color: g
ray
    Polyomino: [(3, 2, 0), (4, 0, 1), (4, 1, 0), (4, 1, 1), (4, 2, 0)], Color: p
urple
    Polyomino: [(3, 2, 1), (3, 3, 0), (3, 3, 1), (4, 2, 1), (4, 3, 1)], Color: y
ellow
    Polyomino: [(3, 4, 1), (3, 5, 1), (4, 3, 0), (4, 4, 0), (4, 4, 1)], Color: b
lue
    Polyomino: [(0, 4, 1), (0, 5, 0), (0, 5, 1), (0, 6, 1), (1, 5, 0)], Color: m
idnightblue
    Polyomino: [(0, 6, 0), (0, 7, 0), (0, 7, 1), (1, 7, 0), (2, 7, 0)], Color: d
arkblue
    Polyomino: [(1, 7, 1), (2, 6, 0), (2, 6, 1), (2, 7, 1), (3, 6, 0)], Color: b
lue
    Polyomino: [(1, 5, 1), (1, 6, 0), (1, 6, 1), (2, 5, 0), (2, 5, 1)], Color: y
ellow
    Polyomino: [(3, 6, 1), (3, 7, 0), (3, 7, 1), (4, 5, 1), (4, 6, 1)], Color: p
urple
    Polyomino: [(3, 5, 0), (4, 5, 0), (4, 6, 0), (4, 7, 0), (4, 7, 1)], Color: o
range
Got:
    Polyomino: [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 2, 0), (1, 1, 0)], Color: d
eeppink
    Polyomino: [(0, 1, 1), (1, 0, 1), (1, 1, 1), (1, 2, 0), (1, 2, 1)], Color: d
eeppink
    Polyomino: [(0, 2, 1), (0, 3, 1), (0, 4, 0), (0, 4, 1), (1, 4, 0)], Color: g
reen
    Polyomino: [(0, 3, 0), (1, 3, 0), (2, 2, 1), (2, 3, 0), (2, 3, 1)], Color: g
reen
    Polyomino: [(1, 3, 1), (1, 4, 1), (2, 4, 0), (2, 4, 1), (2, 5, 1)], Color: r
ed
    Polyomino: [(1, 0, 0), (2, 0, 0), (2, 0, 1), (2, 1, 1), (3, 0, 1)], Color: r
ed
    Polyomino: [(2, 1, 0), (2, 2, 0), (3, 2, 0), (3, 2, 1), (3, 3, 1)], Color: b
lue
    Polyomino: [(3, 0, 0), (3, 1, 0), (4, 0, 0), (4, 0, 1), (4, 1, 0)], Color: y
ellow    Polyomino: [(3, 1, 1), (4, 1, 1), (4, 2, 0), (4, 2, 1), (4, 3, 0)], Color: p
urple
    Polyomino: [(3, 3, 0), (3, 4, 0), (3, 4, 1), (4, 3, 1), (4, 4, 1)], Color: yellow
    Polyomino: [(3, 5, 1), (4, 4, 0), (4, 5, 0), (4, 5, 1), (4, 6, 0)], Color: midnightblue
    Polyomino: [(2, 6, 1), (2, 7, 1), (3, 7, 0), (3, 7, 1), (4, 7, 0)], Color: purple
    Polyomino: [(3, 5, 0), (3, 6, 0), (3, 6, 1), (4, 6, 1), (4, 7, 1)], Color: blue
    Polyomino: [(0, 5, 0), (0, 5, 1), (0, 6, 0), (1, 5, 0), (2, 5, 0)], Color: darkblue
    Polyomino: [(0, 7, 0), (0, 7, 1), (1, 7, 0), (2, 6, 0), (2, 7, 0)], Color: orange
    Polyomino: [(0, 6, 1), (1, 5, 1), (1, 6, 0), (1, 6, 1), (1, 7, 1)], Color: gray
**********************************************************************
**********************************************************************
File "devel/sage/sage/games/quantumino.py", line 485, in sage.games.quantumino.Q
uantuminoSolver.solve
Failed example:
    for p in s: p                                  # long time (fast)
Expected:
    Polyomino: [(0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (1, 2, 0)], Color: deeppink
    Polyomino: [(0, 0, 1), (0, 1, 0), (0, 1, 1), (0, 2, 1), (1, 2, 1)], Color: deeppink
    Polyomino: [(0, 2, 0), (0, 3, 0), (0, 4, 0), (1, 4, 0), (1, 4, 1)], Color: green
    Polyomino: [(0, 3, 1), (1, 3, 1), (2, 2, 0), (2, 2, 1), (2, 3, 1)], Color: green
    Polyomino: [(1, 3, 0), (2, 3, 0), (2, 4, 0), (2, 4, 1), (3, 4, 0)], Color: red
    Polyomino: [(1, 0, 1), (2, 0, 0), (2, 0, 1), (2, 1, 0), (3, 0, 1)], Color: midnightblue
    Polyomino: [(0, 4, 1), (0, 5, 0), (0, 5, 1), (0, 6, 0), (1, 5, 0)], Color: red
    Polyomino: [(2, 1, 1), (3, 0, 0), (3, 1, 0), (3, 1, 1), (4, 0, 0)], Color: blue
    Polyomino: [(3, 2, 0), (4, 0, 1), (4, 1, 0), (4, 1, 1), (4, 2, 0)], Color: purple
    Polyomino: [(3, 2, 1), (3, 3, 0), (4, 2, 1), (4, 3, 0), (4, 3, 1)], Color: yellow
    Polyomino: [(3, 3, 1), (3, 4, 1), (4, 4, 0), (4, 4, 1), (4, 5, 0)], Color: blue
    Polyomino: [(0, 6, 1), (0, 7, 0), (0, 7, 1), (1, 5, 1), (1, 6, 1)], Color: purple
    Polyomino: [(1, 6, 0), (1, 7, 0), (1, 7, 1), (2, 7, 0), (3, 7, 0)], Color: darkblue
    Polyomino: [(2, 5, 0), (2, 6, 0), (3, 6, 0), (4, 6, 0), (4, 6, 1)], Color: orange
    Polyomino: [(2, 5, 1), (3, 5, 0), (3, 5, 1), (3, 6, 1), (4, 5, 1)], Color: gray
    Polyomino: [(2, 6, 1), (2, 7, 1), (3, 7, 1), (4, 7, 0), (4, 7, 1)], Color: orange
Got:
    Polyomino: [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 2, 0), (1, 1, 0)], Color: deeppink
    Polyomino: [(0, 1, 1), (1, 0, 1), (1, 1, 1), (1, 2, 0), (1, 2, 1)], Color: deeppink
    Polyomino: [(0, 2, 1), (0, 3, 1), (0, 4, 0), (0, 4, 1), (1, 4, 0)], Color: green
    Polyomino: [(0, 3, 0), (1, 3, 0), (2, 2, 1), (2, 3, 0), (2, 3, 1)], Color: green
    Polyomino: [(1, 3, 1), (1, 4, 1), (2, 4, 0), (2, 4, 1), (2, 5, 1)], Color: red
    Polyomino: [(1, 0, 0), (2, 0, 0), (2, 0, 1), (2, 1, 1), (3, 0, 1)], Color: red
    Polyomino: [(3, 0, 0), (4, 0, 0), (4, 0, 1), (4, 1, 0), (4, 2, 0)], Color: darkblue
    Polyomino: [(2, 1, 0), (2, 2, 0), (3, 1, 0), (3, 1, 1), (4, 1, 1)], Color: purple
    Polyomino: [(3, 2, 0), (3, 3, 0), (3, 3, 1), (3, 4, 0), (4, 3, 0)], Color: gray
    Polyomino: [(3, 2, 1), (4, 2, 1), (4, 3, 1), (4, 4, 0), (4, 4, 1)], Color: orange
    Polyomino: [(3, 4, 1), (3, 5, 1), (4, 5, 0), (4, 5, 1), (4, 6, 0)], Color: blue
    Polyomino: [(3, 6, 0), (3, 7, 0), (4, 6, 1), (4, 7, 0), (4, 7, 1)], Color: yellow
    Polyomino: [(1, 5, 0), (2, 5, 0), (2, 6, 0), (2, 6, 1), (3, 5, 0)], Color: midnightblue
    Polyomino: [(1, 7, 0), (2, 7, 0), (2, 7, 1), (3, 6, 1), (3, 7, 1)], Color: purple
    Polyomino: [(0, 5, 1), (0, 6, 1), (0, 7, 0), (0, 7, 1), (1, 5, 1)], Color: orange
    Polyomino: [(0, 5, 0), (0, 6, 0), (1, 6, 0), (1, 6, 1), (1, 7, 1)], Color: blue
**********************************************************************
2 items had failures:
   1 of  19 in sage.games.quantumino
   1 of  13 in sage.games.quantumino.QuantuminoSolver.solve
    [74 tests, 2 failures, 63.04 s]
----------------------------------------------------------------------
sage -t --long devel/sage/sage/games/quantumino.py  # 2 doctests failed
----------------------------------------------------------------------
Total time for all tests: 63.1 seconds
    cpu time: 62.9 seconds
    cumulative wall time: 63.0 seconds

(the other failures are in the quadratic forms and appear also with the base sage since 5.9)

comment:32 Changed 6 years ago by vbraun

I fixed the quantumin one. I don't get any doctest failures in quadratic forms.

comment:33 Changed 6 years ago by Snark

Ok, now it compiles and passes all tests except the quadratic forms ones (and those fail on this box anyway).

I'm not sure I can give a positive review though: the patches change the result of many tests, and I have no idea if they really replace a correct value by another correct value...

comment:34 follow-up: Changed 6 years ago by vbraun

Most of the doctests are unchanged, they just moved around when reorganizing the code. The ones that do change are generally trivial, like the order of group elements returned. Only very few are non-trivial (like the quantumino one), and there the corresponding Sage module already does checks. Has anybody ever verified by hand that the quantumino puzzle has 5484 distinct solutions?

comment:35 Changed 6 years ago by vbraun

  • Status changed from needs_work to needs_review

comment:36 Changed 6 years ago by tscrim

  • Cc slabbe added

Hey Volker,

With some of the patches merged in 5.10.beta4 (I'm pretty sure it's #4327), the patchbot is saying there is a (trivial) doctest failure in root_lattice_realization.py. It should be because the order of the group elements changed.

Also in groups/matrix_gps/catalog.py, could you give the file a proper title line (the first docstring line) in case at some point we include the file in the documentation?

Volker, do you remember what other tests were non-trivial changes? I'm cc-ing Sebastien Labbe since the quantumino code was originally written by him.

Thanks,
Travis

comment:37 Changed 6 years ago by vbraun

  • Dependencies changed from #14187, #14323, #14284 to #14187, #14323, #14284, #14640

I've fixed the text output to doctest graphics in #14640. In particular this takes care of the doctest failure in root_lattice_realization by printing sorted plot objects.

Rediffed last patch for fuzz.

Changed 6 years ago by vbraun

Updated patch

comment:38 Changed 6 years ago by vbraun

I don't think there are any non-trival doctest changes. In particular I don't do any non-trivial group theory, everything is punted to GAP and the GAP output is then used. The enumeration of group elements changed as required by the new category consistency check between __iter__ and list() so there is no mystery that individual group elements arrive in different order now. The total number is still the same so unless there is some HUGE bug in GAP this is an equally correct answer.

comment:39 Changed 6 years ago by tscrim

So then the change the quantumino output should be correct. The change just seems non-trivial to me. Sebastien, could you take a look at it just as a double-check?

Volker, a few more things on the patch.

  • matrix_gps/pickling_overrides.py is missing a doctest for the last __setstate__().
  • Would it be possible to not import libs.gap* at startup?
  • (more trivial), could you change the line continuation on line 260 of matrix_gps/finitely_generated.py to the new ....:?

Thanks,
Travis

Changed 6 years ago by vbraun

Initial patch

comment:40 Changed 6 years ago by vbraun

  • Description modified (diff)

comment:41 Changed 6 years ago by vbraun

Libgap is not imported upon startup (it would raise an error if you tried).

comment:42 Changed 6 years ago by tscrim

  • Description modified (diff)

Hey Volker,

I was talking about the modules libs.gap.*, in particular the one which triggers the rest is libs.gap.element. However by lazily importing this, I ended up getting errors, so I don't think we can get around this (plus it's not really a big import or a significant slowdown to startup time). I'd guess this is related to #14357, but it's definitely not worth holding this ticket up.

Anyways, I've uploaded a small reviewer patch which does some minor to trivial docstring changes to methods that are being moved around by this patch. If you're happy with my tweaks, I think we can set this to positive review.

Best,
Travis

comment:43 Changed 6 years ago by vbraun

Let me clarify: Importing libgap is rather slow right now since it does not use the cached GAP workspace. But the matrix groups that use libgap are already lazily imported, so libgap is not loaded on startup even if some files have a non-lazy libgap import. #14187 ensures that an error will be printed if you were to actually import libgap during startup.

comment:44 Changed 6 years ago by vbraun

I agree that there are some unnecessary modules imported (though not libgap as a whole), I created #14652 to deal with them.

comment:45 Changed 6 years ago by vbraun

  • Reviewers changed from David Roe to Travis Scrimshaw
  • Status changed from needs_review to positive_review

reviewer patch looks good to me

comment:46 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.10 to sage-5.11

comment:47 Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work

Documentation trouble:

dochtml.log:[groups   ] /mazur/release/merger/sage-5.11.beta0/devel/sage/doc/en/reference/groups/sage/groups/matrix_gps/matrix_group_morphism.rst:11: WARNING: autodoc can't import/find module 'sage.groups.matrix_gps.matrix_group_morphism', it reported error: "No module named matrix_group_morphism", please check your spelling and sys.path

Note also the patchbot saying (but I don't know how reliable this is):

With 99.9% confidence, startup time increased by at least 0.1%

Changed 6 years ago by tscrim

comment:48 Changed 6 years ago by tscrim

  • Status changed from needs_work to positive_review

New version of the review patch which fixes the doc issue. The file was renamed but not changed in the rst file.

comment:49 Changed 6 years ago by vbraun

Also, the slightly slower startup time will be addressed in #14652

comment:50 in reply to: ↑ 34 Changed 6 years ago by slabbe

Replying to vbraun:

Only very few are non-trivial (like the quantumino one)

I checked the patch fixing non-trivial doctest for the quantumino code, and it is ok. The ordering of the matrices changed the ordering of rotated copies of polyominos, which changed the ordering of the rows passed to the dlx solver, which explains the doctest update for the list of rows indices (a solution is given as a subset of rows).

, and there the corresponding Sage module already does checks. Has anybody ever verified by hand that the quantumino puzzle has 5484 distinct solutions?

The related doctest is the following one :

    sage: q = QuantuminoSolver(0)
    sage: T = q.tiling_solver()
    sage: rows = T.rows()                            # not tested (10 s)
    sage: len(rows)                                  # not tested (but fast)
    5484

This is not the number of solutions. 5484 is the number of rows (of a matrix) given to the dlx solver. The number of solutions of the Quantumino game when one block is chosen aside is counted in the order of 10^9. On my machine I estimated the following line to take one month :

    sage: T.number_of_solutions()

I never run it enough time to get the result...

comment:51 Changed 6 years ago by tscrim

Thanks for checking this Sebastien.

comment:52 Changed 6 years ago by vbraun

sage: T.number_of_solutions()   # very long time

comment:53 Changed 6 years ago by jdemeyer

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