Opened 10 years ago

Closed 10 years ago

# Update matrix groups to new Parents, libGAP.

Reported by: Owned by: Volker Braun joyner major sage-5.11 group theory David Roe, Dima Pasechnik, Sébastien Labbé sage-5.11.beta0 Volker Braun Travis Scrimshaw N/A #14187, #14323, #14284, #14640

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

Follow-up: #14039.

### comment:1 Changed 10 years ago by Volker Braun

Dependencies: → #14015

### comment:2 Changed 10 years ago by Volker Braun

Dependencies: #14015

### comment:3 Changed 10 years ago by Volker Braun

Description: modified (diff)

### comment:4 Changed 10 years ago by Volker Braun

Authors: → Volker Braun modified (diff) new → needs_review

### comment:6 Changed 10 years ago by Volker Braun

Dependencies: → #14187

Initial patch

### comment:7 Changed 10 years ago by Volker Braun

Description: modified (diff)

Split into bit-sized pieces ;-)

### comment:8 Changed 10 years ago by Volker Braun

Description: modified (diff) → David Roe

### comment:9 Changed 10 years ago by Dima Pasechnik

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

### comment:10 Changed 10 years ago by Dima Pasechnik

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 10 years ago by Volker Braun

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 10 years ago by Jeroen Demeyer

Description: modified (diff)

### comment:13 Changed 10 years ago by Jeroen Demeyer

Dependencies: #14187 → #14187, #14323 modified (diff)

Moving the spkg-update to #14323.

### comment:14 Changed 10 years ago by Dima Pasechnik

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 10 years ago by Dima Pasechnik (previous) (diff)

### comment:15 Changed 10 years ago by Dima Pasechnik

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 10 years ago by Dima Pasechnik

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 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 10 years ago by Dima Pasechnik

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 10 years ago by Dima Pasechnik (previous) (diff)

### 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 10 years ago by Volker Braun (previous) (diff)

### 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 10 years ago by Dima Pasechnik (previous) (diff)

### comment:20 Changed 10 years ago by Dima Pasechnik

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 10 years ago by Dima Pasechnik (previous) (diff)

### comment:21 follow-up:  22 Changed 10 years ago by Volker Braun

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 10 years ago by Dima Pasechnik

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 10 years ago by Dima Pasechnik (previous) (diff)

### comment:23 Changed 10 years ago by Dima Pasechnik

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 10 years ago by Volker Braun

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 10 years ago by Volker Braun

Dependencies: #14187, #14323 → #14187, #14323, #14284

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

### comment:26 Changed 10 years ago by Volker Braun

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().

Updated patch

### comment:27 Changed 10 years ago by Volker Braun

Rebased for the updated patch in #14187

Updated patch

Updated patch

### comment:28 Changed 10 years ago by Volker Braun

Patches rebased for sage-5.10.beta1

### comment:29 Changed 10 years ago by Julien Puydt

Status: needs_review → needs_work

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

### comment:30 Changed 10 years ago by Volker Braun

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 10 years ago by Julien Puydt

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
**********************************************************************
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 10 years ago by Volker Braun

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

### comment:33 Changed 10 years ago by Julien Puydt

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:  50 Changed 10 years ago by Volker Braun

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 10 years ago by Volker Braun

Status: needs_work → needs_review

### comment:36 Changed 10 years ago by Travis Scrimshaw

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 10 years ago by Volker Braun

Dependencies: #14187, #14323, #14284 → #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.

Updated patch

### comment:38 Changed 10 years ago by Volker Braun

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 10 years ago by Travis Scrimshaw

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

Initial patch

### comment:40 Changed 10 years ago by Volker Braun

Description: modified (diff)

### comment:41 Changed 10 years ago by Volker Braun

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

### comment:42 Changed 10 years ago by Travis Scrimshaw

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 10 years ago by Volker Braun

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 10 years ago by Volker Braun

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 10 years ago by Volker Braun

Reviewers: David Roe → Travis Scrimshaw needs_review → positive_review

reviewer patch looks good to me

### comment:46 Changed 10 years ago by Jeroen Demeyer

Milestone: sage-5.10 → sage-5.11

### comment:47 Changed 10 years ago by Jeroen Demeyer

Status: positive_review → 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%


### comment:48 Changed 10 years ago by Travis Scrimshaw

Status: needs_work → 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 10 years ago by Volker Braun

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

### comment:50 in reply to:  34 Changed 10 years ago by Sébastien Labbé

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 10 years ago by Travis Scrimshaw

Thanks for checking this Sebastien.

### comment:52 Changed 10 years ago by Volker Braun

sage: T.number_of_solutions()   # very long time


### comment:53 Changed 10 years ago by Jeroen Demeyer

Merged in: → sage-5.11.beta0 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.