Add domains for permutation groups

[mwhansen]

Often, one wants to define a permutation group on a set other than {1,2,...,n} such as say {'a', 'b', 'c', 'd'}.

For example,

sage: G = PermutationGroup([ [('c','d')], [('a','c')] ])
sage: G.orbit('a')
['a', 'c', 'd']

Apply:

1. attachment: trac_10335-permgroup_domain-rebase.patch

Depends on #10334

CC: @sagetrac-sage-combinat @sagetrac-jasonbhill @rbeezer @jdemeyer

Component: group theory

Keywords: sd31

Author: Mike Hansen, Jason Hill, David Loeffler

Reviewer: Robert Miller, Rob Beezer, Nicolas Borie, Nicolas M. Thiéry

Merged: sage-4.7.2.alpha3

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

[mwhansen]

comment:1

This depends

[rlmill]

Reviewer: Robert Miller

[rlmill]

Work Issues: needs rebase

[rlmill]

comment:3

Applying to sage-4.6.2.alpha0 on top of #10334, I get:

applying trac_10335-permgroup_domain-mh.patch
patching file sage/groups/perm_gps/permgroup.py
Hunk #5 FAILED at 321
1 out of 59 hunks FAILED -- saving rejects to file sage/groups/perm_gps/permgroup.py.rej
patching file sage/groups/perm_gps/permgroup_named.py
Hunk #10 succeeded at 313 with fuzz 2 (offset 0 lines).
Hunk #11 succeeded at 315 with fuzz 1 (offset -49 lines).
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh trac_10335-permgroup_domain-mh.patch

The failure:

$ cat sage/groups/perm_gps/permgroup.py.rej
--- permgroup.py
+++ permgroup.py
@@ -320,7 +322,7 @@
         sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
         sage: TestSuite(G).run()
     """
-    def __init__(self, gens=None, gap_group=None, canonicalize=True, category = None):
+    def __init__(self, gens=None, gap_group=None, canonicalize=True, category=None, domain=None):
         r"""
         INPUT:

Looks trivial to fix, and I'm excited to see this feature in Sage. Thank you, Mike!

[nthiery]

comment:5

This was most likely a minor conflict with Rob's permgroup patches which were merged late in the 4.6.2 release cycle.

Only apply: trac_10335-permgroup_domain-mh.2.patch

[nthiery]

Changed work issues from needs rebase to none

[nthiery]

comment:6

Ah, the test fail, and that's because the patch still did not commute perfectly with trac_8359-coxeter-groups-permutation-nt.patch. we need to have this patch add the category argument to __init__ of permutation groups, and remove that part from 8359.

Mike: let me know if you can do it shortly, and then #8359 is fair game. Otherwise I'll handle it.

[mwhansen]

comment:8

I've fixed the issue along with updating the patch at #8359.

Only apply: trac_10335-permgroup_domain-mh.patch

[rbeezer]

comment:9

This looks real good, Mike. I spent some time with this today. I know its not done yet, but hopefully the following will be helpful.

I applied the patch from sage-combinat for #8359 to 4.7.alpha1, as best I could tell (used patch from http://combinat.sagemath.org/hgwebdir.cgi/patches/rev/508d4942a6d2). One hunk failure at sage/combinat/root_system/all.py. Then #10334 had a hunk failure in sage/groups/perm_gps/permgroup.py and #10335 had a had failure in sage/categories/pushout.py. All easy to fix by hand, and maybe a result of not getting the right thing from the sage-combinat server.

Passed all tests in sage/groups/perm_gps, except two, so not too far off. Both doctest failures look very minor, and a result of routines I wrote that have been added recently.

**********************************************************************
File "/sage/dev/devel/sage-main/sage/groups/perm_gps/permgroup.py", line 1920:
    sage: G.subgroups()
Expected:
    [Permutation Group with generators [()],
     Permutation Group with generators [(2,3)],
     Permutation Group with generators [(1,2)],
     Permutation Group with generators [(1,3)],
     Permutation Group with generators [(1,2,3)],
     Permutation Group with generators [(1,3,2), (1,2)]]
Got:
    [Permutation Group with generators [()],
     Permutation Group with generators [(2,3)],
     Permutation Group with generators [(1,2)],
     Permutation Group with generators [(1,3)],
     Permutation Group with generators [(1,2,3)],
     Permutation Group with generators [(1,2), (1,3,2)]]
**********************************************************************
File "/sage/dev/devel/sage-main/sage/groups/perm_gps/permgroup.py", line 2082:
    sage: A.cosets(S)
Expected:
    Traceback (most recent call last):
    ...
    ValueError: Subgroup of SymmetricGroup(3) generated by [(1,2)] is not a subgroup of AlternatingGroup(3)
Got:
    Traceback (most recent call last):
      File "/sage/dev/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/sage/dev/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/sage/dev/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_61[29]>", line 1, in <module>
        A.cosets(S)###line 2082:
    sage: A.cosets(S)
      File "/sage/dev/local/lib/python/site-packages/sage/groups/perm_gps/permgroup.py", line 2099, in cosets
        raise ValueError("%s is not a subgroup of %s" % (S, self))
    ValueError: Subgroup of (Symmetric group of order 3! as a permutation group) generated by [(1,2)] is not a subgroup of Alternating group of order 3!/2 as a permutation group
**********************************************************************

I think the stabilizer() routine needs some work.

try:
    postition = self._domain_to_gap[point]
except KeyError:
    return self.subgroup(gens=self.gens())
return self.subgroup(gap_group=gap.Stabilizer(self, point))

"position" is mis-spelled as first defined, and in the return, I think "point" should be replaced with "position". With these changes, this seems to work properly with a non-trivial domain in play.

Not a comprehensive look, but hopefully of use. Let me know what I can do to help (including assisting with documentation). It'd be nice if there was a patch, or something, at #8359 explaining how best to apply that work.

Rob

[nthiery]

comment:10

Hi Mike,

For the record: I rebased trac_10335-permgroup_domain-mh.patch on the sage-combinat server on top of #9949

[nthiery]

comment:11

Hi Mike!

Replying to @nthiery:

For the record: I rebased trac_10335-permgroup_domain-mh.patch on the sage-combinat server on top of #9949

With Rob we are both at Sage days 30, and would love to push permutation groups in. Rob is going to rebase #10334, and I'll finalize the review. #10335 itself needs rebase on 3.4.7, and has quite a few failing doctests, though most look harmless (it's just that the output of permutation groups have changed). Would there be any chance for you to work on this early this week?

Thanks!

Cheers,
Nicolas

[mwhansen]

comment:12

Sure -- I'll try to get this taken care of tonight.

[mwhansen]

comment:13

I've fixed the doctest failures and updated the patch.

[rbeezer]

comment:14

I ran make ptestlong and got quite a few failures. I even tried it twice - not sure what is up.

• Many were in sage/doc
• Many were simply the new version of _repr_ for the symmetric group, and its subgroups
• The latex() method is putting a comma between the cycles within each generator. Is this desired?

return ",".join(["(" + ",".join([latex(x) for x in cycle])+")" for cycle in self.cycle_tuples()])

At a minimum it is causing doctest failures.

• 73 failures in sage/rings/number_field/galois_group.py, likely all the same root cause

Saw these in the patch itself:

• a stray "deprecated_function_alias" in a docstring
• ``selfs`` in a docstring

[sagetrac-nborie]

Dependencies: #10334

[rbeezer]

comment:64

Replying to @rbeezer:

Probably about 8-10 hours from now.

My build was interrupted (long story) and now two files are giving segfaults when I doctest, with or without the patch. Don't panic - likely entirely all my fault. So anyway, I'm starting over and building overnight. Stay tuned.

Rob

[rbeezer]

comment:65

alpha3-prerelease segfaults during testing, without patch. Errors, followed by system info. I can follow up with more testing, if requested.

The following tests failed:

        sage -t  -long -force_lib devel/sage/sage/modular/modsym/ambient.py # 0 doctests failed
        sage -t  -long -force_lib devel/sage/sage/modular/hecke/ambient_module.py # 0 doctests failed
        sage -t  -long -force_lib devel/sage/sage/modular/hecke/hecke_operator.py # 0 doctests failed
----------------------------------------------------------------------
Total time for all tests: 2701.6 seconds
make: *** [ptestlong] Error 128

rob@lava:/sage/sage-4.7.2.alpha3-prerelease$ ./sage -t  -long -force_lib devel/sage/sage/modular/modsym/ambient.py
sage -t -long -force_lib "devel/sage/sage/modular/modsym/ambient.py"
/sage/sage-4.7.2.alpha3-prerelease/local/lib/libcsage.so(print_backtrace+0x31)[0x7fd8e335834f]
/sage/sage-4.7.2.alpha3-prerelease/local/lib/libcsage.so(sigdie+0x14)[0x7fd8e3358381]
/sage/sage-4.7.2.alpha3-prerelease/local/lib/libcsage.so(sage_signal_handler+0x20e)[0x7fd8e3357fb4]
/lib/x86_64-linux-gnu/libpthread.so.0(+0xfc60)[0x7fd8e484fc60]
/sage/sage-4.7.2.alpha3-prerelease/local/lib/libatlas.so(ATL_dJIK44x44x44TN44x44x0_a1_b0+0x9d)[0x7fd8da12c3ed]

------------------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component of Sage has a bug
in it and is not properly wrapped with sig_on(), sig_off(). You might
want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate.
------------------------------------------------------------------------
Segmentation fault

         [5.9 s]
 
----------------------------------------------------------------------
The following tests failed:


        sage -t -long -force_lib "devel/sage/sage/modular/modsym/ambient.py"
Total time for all tests: 5.9 seconds

rob@lava:/sage/sage-4.7.2.alpha3-prerelease$ uname -a
Linux lava 2.6.38-10-generic #46-Ubuntu SMP Tue Jun 28 15:07:17 UTC 2011 x86_64 x86_64 x86_64 GNU/Linux

rob@lava:/sage/sage-4.7.2.alpha3-prerelease$ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/x86_64-linux-gnu/gcc/x86_64-linux-gnu/4.5.2/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.5.2-8ubuntu4' --with-bugurl=file:///usr/share/doc/gcc-4.5/README.Bugs --enable-languages=c,c++,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.5 --enable-shared --enable-multiarch --with-multiarch-defaults=x86_64-linux-gnu --enable-linker-build-id --with-system-zlib --libexecdir=/usr/lib/x86_64-linux-gnu --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.5 --libdir=/usr/lib/x86_64-linux-gnu --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-plugin --enable-gold --enable-ld=default --with-plugin-ld=ld.gold --enable-objc-gc --disable-werror --with-arch-32=i686 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.5.2 (Ubuntu/Linaro 4.5.2-8ubuntu4) 

rob@lava:/sage/sage-4.7.2.alpha3-prerelease$ cat /proc/cpuinfo
processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 42
model name      : Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz
stepping        : 7
cpu MHz         : 1600.000
cache size      : 8192 KB
physical id     : 0
siblings        : 8
core id         : 0
cpu cores       : 4
apicid          : 0
initial apicid  : 0
fpu             : yes
fpu_exception   : yes
cpuid level     : 13
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm sse4_1 sse4_2 x2apic popcnt aes xsave avx lahf_lm ida arat epb xsaveopt pln pts dts tpr_shadow vnmi flexpriority ept vpid
bogomips        : 6822.05
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:

[nexttime]

comment:66

Replying to @rbeezer:

alpha3-prerelease segfaults during testing, without patch. Errors, followed by system info. I can follow up with more testing, if requested.

That's either due to Linaro, or, more likely, an ATLAS problem, since our version afaik doesn't yet support Sandy Bridge (second generation "Core i").

You could try using your system's ATLAS (may have to install it with your package manager first), by doing:

$ export SAGE_ATLAS_LIB=/usr/lib64/atlas # the directory; usual place on 64-bit Linux
$ rm $SAGE_ROOT/spkg/installed/atlas-*
$ cd $SAGE_ROOT
$ env SAGE_UPGRADING=yes make # or "... make build"

The SAGE_UPGRADING=yes is important to (really) rebuild all dependent packages as well.

[nexttime]

comment:67

Replying to @nexttime:

$ export SAGE_ATLAS_LIB=/usr/lib64/atlas # the directory; usual place on 64-bit Linux
...

Might be /usr/lib/x86_64-linux-gnu/atlas/ on your system; you should check this before attempting to build... ;-)

[rbeezer]

comment:68

Thanks, Leif. Ubuntu installs ATLAS into /usr/lib64/atlas-base. Then setting up everything as you describe, suitably adjusted yields:

Unable to find one of liblapack, libcblas, libatlas or libf77blas
in the directory /usr/lib64/atlas-base
Set SAGE_ATLAS_LIB to the directory containing liblapack, libcblas,
libatlas and libf77blas (either .a or .so extensions) if you wish to
use existing ATLAS libraries. For more details, see

I've installed the packages liblapack3gf, libblas3gf but cannot see anything to provide libf77blas and do not know if I am getting libcblas. Furthermore, these all go to different directories.

Any advice? My Sandy Bridge motherboard is about 8 months old. Will anybody with a newer chip have to go through a drill like this? Would Volker's ATLAS ticket be a better/workable approach?

[nexttime]

comment:69

Replying to @rbeezer:

I've installed the packages liblapack3gf, libblas3gf but cannot see anything to provide libf77blas and do not know if I am getting libcblas. Furthermore, these all go to different directories.

I've asked Volker on the IRC for help. (Perhaps drop in if you can.)

If some libraries are simply in different directories, you could just create symbolic links to them in the .../atlas-base/ directory. (Although there IMHO should^TM be a directory containing all; are there some more self-contained ATLAS packages you could install?)

My Sandy Bridge motherboard is about 8 months old.

That shouldn't matter; Intel's bug just causes a SATA part of the chipset to die earlier.

Whether AVX is available depends on your board (and chipset); if you have on-board graphics, AVX isn't usable.

Will anybody with a newer chip have to go through a drill like this?

Simon King did successfully build the prerelease on a (Sandy Bridge) Core i3 with Debian x86_64; there only five doctests (in three files) failed due to numerical noise (the same doctests that failed on some other "rare" and older platforms).

[vbraun]

comment:70

The following bug in Ubuntu launchpad says that the symlinks for the standard libraries are not created: https://bugs.launchpad.net/ubuntu/+source/atlas/+bug/769180 So you either create them manually (in a directory of your choice), or you compile ATLAS again. For the latter, you should probably try to set

export SAGE_ATLAS_ARCH=Corei7,SSE3,SSE2,SSE1

This works only with the new atlas spkg (4.7.2.alpha3+)

[vbraun]

comment:71

AVX is just the CPU instruction set extension du jour. The version of ATLAS that we are shipping knows nothing about AVX. All 2011 sandy bridge cpus have it, irrespective of on-board graphics.

[nexttime]

comment:72

Replying to @vbraun:

AVX is just the CPU instruction set extension du jour. The version of ATLAS that we are shipping knows nothing about AVX.

Aha. Wasn't sure about that. But does 3.8.4 "know" Sandy Brigde already?

All 2011 sandy bridge cpus have it, irrespective of on-board graphics.

They have it, but you can only use it when the CPU doesn't also act as a GPU. And afaik that's hard-wired, i.e., you even cannot use it if your motherboard has on-board graphics you don't actually use.

[nexttime]

comment:73

Replying to @vbraun:

This works only with the new atlas spkg (4.7.2.alpha3+)

I guess you meant alpha2+.

Apparently alpha2 in contrast did not segfault for Rob (on that machine), despite having the same ATLAS spkg. At least that's my understanding.

[vbraun]

comment:74

Oh yes, it was merged in alpha2.

This is now completely OT, but my (Sandy Bridge) Thinkpad W520 uses the on-board GPU and has AVX:

[vbraun@volker-laptop-two ~]$ cat /proc/cpuinfo | head -24
processor	: 0
vendor_id	: GenuineIntel
cpu family	: 6
model		: 42
model name	: Intel(R) Core(TM) i7-2720QM CPU @ 2.20GHz
stepping	: 7
cpu MHz		: 2201.000
cache size	: 6144 KB
physical id	: 0
siblings	: 8
core id		: 0
cpu cores	: 4
apicid		: 0
initial apicid	: 0
fpu		: yes
fpu_exception	: yes
cpuid level	: 13
wp		: yes
flags		: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx rdtscp lm constant_tsc arch_perfmon pebs bts nopl xtopology nonstop_tsc aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm sse4_1 sse4_2 x2apic popcnt aes xsave avx lahf_lm ida arat epb xsaveopt pln pts dts tpr_shadow vnmi flexpriority ept vpid
bogomips	: 4385.92
clflush size	: 64
cache_alignment	: 64
address sizes	: 36 bits physical, 48 bits virtual
power management:

[rbeezer]

comment:75

Leif and Volker,

Thanks for the quick help, and I apologize to the group theorists for diverting this ticket. I've got to attend to some other things the rest of today, but I'll see if I can get the symlinks in place with guidance from that bug report.

I have Sandy Bridge with no on-board graphics. I have built and tested alpha2 - this is my first problem like this.

Rob

[nexttime]

comment:76

Replying to @rbeezer:

Leif and Volker,

Thanks for the quick help, and I apologize to the group theorists for diverting this ticket.

Yep, we can continue the discussion on e.g. this sage-release thread, or -- preferably -- a new one there.

[rbeezer]

comment:77

alpha3 prerelease build is fixed and passes long tests, with and without this rebased patch. To quote William "merge that sucker"! In other words, positive review.

Second line of patch summary message credits Jason Hill - I'll add him to the authors, and Mike's name is still on the main patch.

David - feel free to cc me on any of the follow-on tickets that might need review, especially if they are cosmetic changes. I have not yet looked at them at all.

Leif - thanks for your attention to this one and help with my build challenges.

Everybody else - my apologies again for getting this ticket off the tracks. I need to post a summary on sage-release.

Rob

[rbeezer]

Changed author from Mike Hansen, David Loeffler to Mike Hansen, Jason Hill, David Loeffler

[loefflerd]

comment:78

Hi Rob,

Thanks for the review! I have tested the two tickets that follow on directly from this (#11422 and #11598) and they apply fine and pass doctests, so no futher reviewing is needed; I'm going to move them back to the 4.7.2 milestone (from "sage-pending").

Regards, David

[nexttime]

Merged: sage-4.7.2.alpha3

[sagetrac-nborie]

comment:80

Hello and sorry to add a comment on a closed ticket. I have a patch which depend on it and the patchbot try to apply 2 patches instead one here.

apply trac_10335-permgroup_domain-rebase.patch