Opened 8 years ago
Closed 8 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 )
This patch adds support for cyclotomics and matrices to LibGAP. And rewrites the matrix groups on top of that.
- Apply trac_14014_libgap_cyclotomic_matrix.patch
- Apply trac_14014_deletions.patch
- Apply trac_14014_parents_for_matrix_groups.patch
- Apply trac_14014_parents_group_dependents.patch
- Apply trac_14014_iterator.patch
- Apply trac_14014_misc.patch
- Apply trac_14014-review-ts.patch
Follow-up: #14039.
Attachments (7)
Change History (60)
comment:1 Changed 8 years ago by
- Dependencies set to #14015
comment:2 Changed 8 years ago by
- Dependencies #14015 deleted
comment:3 Changed 8 years ago by
- Description modified (diff)
comment:4 Changed 8 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:5 Changed 8 years ago by
- Cc roed added
comment:6 Changed 8 years ago by
- Dependencies set to #14187
Changed 8 years ago by
comment:8 Changed 8 years ago by
- Description modified (diff)
- Reviewers set to David Roe
comment:10 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
- Description modified (diff)
comment:13 Changed 8 years ago by
- Dependencies changed from #14187 to #14187, #14323
- Description modified (diff)
Moving the spkg-update to #14323.
comment:14 Changed 8 years ago by
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()
?
comment:15 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
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).
comment:18 follow-up: ↓ 19 Changed 8 years ago by
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.
comment:19 in reply to: ↑ 18 Changed 8 years ago by
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 runsage -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.
comment:20 Changed 8 years ago by
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).
comment:21 follow-up: ↓ 22 Changed 8 years ago by
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 8 years ago by
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.
comment:23 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
- 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 8 years ago by
- 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()
.
comment:27 Changed 8 years ago by
Rebased for the updated patch in #14187
comment:28 Changed 8 years ago by
Patches rebased for sage-5.10.beta1
comment:29 Changed 8 years ago by
- Status changed from needs_review to needs_work
trac_14014_iterator.patch doesn't apply correctly in sage-5.10.beta2
comment:30 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
I fixed the quantumin one. I don't get any doctest failures in quadratic forms.
comment:33 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
- Status changed from needs_work to needs_review
comment:36 Changed 8 years ago by
- 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 8 years ago by
- 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.
comment:38 Changed 8 years ago by
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 8 years ago by
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
comment:40 Changed 8 years ago by
- Description modified (diff)
comment:41 Changed 8 years ago by
Libgap is not imported upon startup (it would raise an error if you tried).
comment:42 Changed 8 years ago by
- 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 8 years ago by
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 8 years ago by
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 8 years ago by
- 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 8 years ago by
- Milestone changed from sage-5.10 to sage-5.11
comment:47 Changed 8 years ago by
- 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 8 years ago by
comment:48 Changed 8 years ago by
- 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 8 years ago by
Also, the slightly slower startup time will be addressed in #14652
comment:50 in reply to: ↑ 34 Changed 8 years ago by
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 8 years ago by
Thanks for checking this Sebastien.
comment:52 Changed 8 years ago by
sage: T.number_of_solutions() # very long time
comment:53 Changed 8 years ago by
- Merged in set to sage-5.11.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
Initial patch