Opened 5 years ago

Closed 5 years ago

#22600 closed enhancement (fixed)

Implement Weyl groups as permutation groups

Reported by: tscrim Owned by:
Priority: major Milestone: sage-8.0
Component: combinatorics Keywords: days85
Cc: sage-combinat, stumpc5, nthiery, darij Merged in:
Authors: Travis Scrimshaw Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: cbe9bf2 (Commits, GitHub, GitLab) Commit: cbe9bf269788ebda128a37a076a4a488cf03efd7
Dependencies: Stopgaps:

Status badges

Description

Right now, they can be constructed using the experimental GAP3 spkg using ReflectionGroup, but we can have a native version by using the root system code. The advantage to this implementation is that it is extremely fast to iterate over.

We also refactor the element classes and move some other code up to the appropriate categories. A small bug is also fixed for checking irreducibility for generic Dynkin diagrams.

Change History (21)

comment:1 Changed 5 years ago by tscrim

  • Branch set to public/combinat/Weyl_groups_as_permutation_groups-22600
  • Component changed from PLEASE CHANGE to combinatorics
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by git

  • Commit set to b0994fdc19264a9e11be6600a267fa5084925dac

Branch pushed to git repo; I updated commit sha1. New commits:

b0994fdNative implementation of Weyl groups as permutations and refactoring.

comment:3 Changed 5 years ago by tscrim

  • Status changed from needs_review to needs_work

It could be that more things need to be moved up to the category, that are essentially generic methods, and some more @abstract_methods defined. However, I think we can worry about that later as we come across them.

I noticed a few other things to do. I will finish them after lunch.

comment:4 Changed 5 years ago by git

  • Commit changed from b0994fdc19264a9e11be6600a267fa5084925dac to a81a43b12c885b43c6ac77d43a9060cff4903d02

Branch pushed to git repo; I updated commit sha1. New commits:

a81a43bMore standardization and removing CoxeterGroupAsPermutationGroup class.

comment:5 Changed 5 years ago by tscrim

  • Status changed from needs_work to needs_review

comment:6 Changed 5 years ago by git

  • Commit changed from a81a43b12c885b43c6ac77d43a9060cff4903d02 to 0ef73628c50f4c5ce45ac7cc2221fbbdcaf70dd9

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

91d86a4Native implementation of Weyl groups as permutations and refactoring.
0ef7362More standardization and removing CoxeterGroupAsPermutationGroup class.

comment:7 Changed 5 years ago by stumpc5

Hi Travis! What is the point of moving the element class into cython?

comment:8 Changed 5 years ago by tscrim

IIRC, it is faster to have a cdef class, even when the methods are predominantly Python. However, it does allow us to use cpdef and run things entirely with C-function calls. There are quite possibly a number of other improvements we could do now that it is a cdef class, but I didn't want to get into that too much now (lest I spend the entire Sage days doing that :P).

comment:9 Changed 5 years ago by stumpc5

okay, so nothing concrete yet. I have also reimplemented the gap3 iteration algorithm in Sage in #20445 in case you want to give it a try, or to check if you could use it as well for Weyl groups.

comment:10 Changed 5 years ago by tscrim

I remember the iteration algorithm. We probably should consider cleaning that up and including it as an alternative implementation. Also from talking with Jeroen, I've become more convinced that if we want more speed from the current iteration algorithm, we need to extract it out into a C++ class. This would be a separate ticket of course.

comment:11 Changed 5 years ago by jdemeyer

Don't do this Cython code: from six.moves import range.

comment:12 Changed 5 years ago by jdemeyer

Just for fun, let me post this:

This is the C code generated for for i in range(len(M_gals[0])) with six.moves.range:

  __pyx_t_2 = __Pyx_GetModuleGlobalName(__pyx_n_s_range); if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 640, __pyx_L1_error)
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_t_7 = __Pyx_GetItemInt_List(__pyx_v_M_gals, 0, long, 1, __Pyx_PyInt_From_long, 1, 0, 1); if (unlikely(!__pyx_t_7)) __PYX_ERR(0, 640, __pyx_L1_error)
  __Pyx_GOTREF(__pyx_t_7);
  __pyx_t_5 = PyObject_Length(__pyx_t_7); if (unlikely(__pyx_t_5 == -1)) __PYX_ERR(0, 640, __pyx_L1_error)
  __Pyx_DECREF(__pyx_t_7); __pyx_t_7 = 0;
  __pyx_t_7 = PyInt_FromSsize_t(__pyx_t_5); if (unlikely(!__pyx_t_7)) __PYX_ERR(0, 640, __pyx_L1_error)
  __Pyx_GOTREF(__pyx_t_7);
  __pyx_t_3 = NULL;
  if (CYTHON_UNPACK_METHODS && unlikely(PyMethod_Check(__pyx_t_2))) {
    __pyx_t_3 = PyMethod_GET_SELF(__pyx_t_2);
    if (likely(__pyx_t_3)) {
      PyObject* function = PyMethod_GET_FUNCTION(__pyx_t_2);
      __Pyx_INCREF(__pyx_t_3);
      __Pyx_INCREF(function);
      __Pyx_DECREF_SET(__pyx_t_2, function);
    }
  }
  if (!__pyx_t_3) {
    __pyx_t_1 = __Pyx_PyObject_CallOneArg(__pyx_t_2, __pyx_t_7); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 640, __pyx_L1_error)
    __Pyx_DECREF(__pyx_t_7); __pyx_t_7 = 0;
    __Pyx_GOTREF(__pyx_t_1);
  } else {
    #if CYTHON_FAST_PYCALL
    if (PyFunction_Check(__pyx_t_2)) {
      PyObject *__pyx_temp[2] = {__pyx_t_3, __pyx_t_7};
      __pyx_t_1 = __Pyx_PyFunction_FastCall(__pyx_t_2, __pyx_temp+1-1, 1+1); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 640, __pyx_L1_error)
      __Pyx_XDECREF(__pyx_t_3); __pyx_t_3 = 0;
      __Pyx_GOTREF(__pyx_t_1);
      __Pyx_DECREF(__pyx_t_7); __pyx_t_7 = 0;
    } else
    #endif
    #if CYTHON_FAST_PYCCALL
    if (__Pyx_PyFastCFunction_Check(__pyx_t_2)) {
      PyObject *__pyx_temp[2] = {__pyx_t_3, __pyx_t_7};
      __pyx_t_1 = __Pyx_PyCFunction_FastCall(__pyx_t_2, __pyx_temp+1-1, 1+1); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 640, __pyx_L1_error)
      __Pyx_XDECREF(__pyx_t_3); __pyx_t_3 = 0;
      __Pyx_GOTREF(__pyx_t_1);
      __Pyx_DECREF(__pyx_t_7); __pyx_t_7 = 0;
    } else
    #endif
    {
      __pyx_t_4 = PyTuple_New(1+1); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 640, __pyx_L1_error)
      __Pyx_GOTREF(__pyx_t_4);
      __Pyx_GIVEREF(__pyx_t_3); PyTuple_SET_ITEM(__pyx_t_4, 0, __pyx_t_3); __pyx_t_3 = NULL;
      __Pyx_GIVEREF(__pyx_t_7);
      PyTuple_SET_ITEM(__pyx_t_4, 0+1, __pyx_t_7);
      __pyx_t_7 = 0;
      __pyx_t_1 = __Pyx_PyObject_Call(__pyx_t_2, __pyx_t_4, NULL); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 640, __pyx_L1_error)
      __Pyx_GOTREF(__pyx_t_1);
      __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
    }
  }
  __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
  if (likely(PyList_CheckExact(__pyx_t_1)) || PyTuple_CheckExact(__pyx_t_1)) {
    __pyx_t_2 = __pyx_t_1; __Pyx_INCREF(__pyx_t_2); __pyx_t_5 = 0;
    __pyx_t_6 = NULL;
  } else {
    __pyx_t_5 = -1; __pyx_t_2 = PyObject_GetIter(__pyx_t_1); if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 640, __pyx_L1_error)
    __Pyx_GOTREF(__pyx_t_2);
    __pyx_t_6 = Py_TYPE(__pyx_t_2)->tp_iternext; if (unlikely(!__pyx_t_6)) __PYX_ERR(0, 640, __pyx_L1_error)
  }
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
  for (;;) {
    if (likely(!__pyx_t_6)) {
      if (likely(PyList_CheckExact(__pyx_t_2))) {
        if (__pyx_t_5 >= PyList_GET_SIZE(__pyx_t_2)) break;
        #if CYTHON_ASSUME_SAFE_MACROS && !CYTHON_AVOID_BORROWED_REFS
        __pyx_t_1 = PyList_GET_ITEM(__pyx_t_2, __pyx_t_5); __Pyx_INCREF(__pyx_t_1); __pyx_t_5++; if (unlikely(0 < 0)) __PYX_ERR(0, 640, __pyx_L1_error)
        #else
        __pyx_t_1 = PySequence_ITEM(__pyx_t_2, __pyx_t_5); __pyx_t_5++; if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 640, __pyx_L1_error)
        __Pyx_GOTREF(__pyx_t_1);
        #endif
      } else {
        if (__pyx_t_5 >= PyTuple_GET_SIZE(__pyx_t_2)) break;
        #if CYTHON_ASSUME_SAFE_MACROS && !CYTHON_AVOID_BORROWED_REFS
        __pyx_t_1 = PyTuple_GET_ITEM(__pyx_t_2, __pyx_t_5); __Pyx_INCREF(__pyx_t_1); __pyx_t_5++; if (unlikely(0 < 0)) __PYX_ERR(0, 640, __pyx_L1_error)
        #else
        __pyx_t_1 = PySequence_ITEM(__pyx_t_2, __pyx_t_5); __pyx_t_5++; if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 640, __pyx_L1_error)
        __Pyx_GOTREF(__pyx_t_1);
        #endif
      }
    } else {
      __pyx_t_1 = __pyx_t_6(__pyx_t_2);
      if (unlikely(!__pyx_t_1)) {
        PyObject* exc_type = PyErr_Occurred();
        if (exc_type) {
          if (likely(exc_type == PyExc_StopIteration || PyErr_GivenExceptionMatches(exc_type, PyExc_StopIteration))) PyErr_Clear();
          else __PYX_ERR(0, 640, __pyx_L1_error)
        }
        break;
      }
      __Pyx_GOTREF(__pyx_t_1);
    }
    __Pyx_XDECREF_SET(__pyx_v_i, __pyx_t_1);
    __pyx_t_1 = 0;

and this is without six.moves.range:

  __pyx_t_1 = __Pyx_GetItemInt_List(__pyx_v_M_gals, 0, long, 1, __Pyx_PyInt_From_long, 1, 0, 1); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 638, __pyx_L1_error)
  __Pyx_GOTREF(__pyx_t_1);
  __pyx_t_5 = PyObject_Length(__pyx_t_1); if (unlikely(__pyx_t_5 == -1)) __PYX_ERR(0, 638, __pyx_L1_error)
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
  for (__pyx_t_12 = 0; __pyx_t_12 < __pyx_t_5; __pyx_t_12+=1) {
    __pyx_v_i = __pyx_t_12;

comment:13 Changed 5 years ago by git

  • Commit changed from 0ef73628c50f4c5ce45ac7cc2221fbbdcaf70dd9 to eda7dbdc749adfcbb80f8e4ee26868ec122814fc

Branch pushed to git repo; I updated commit sha1. New commits:

eda7dbdUsing xrange in the new Cython file.

comment:14 Changed 5 years ago by git

  • Commit changed from eda7dbdc749adfcbb80f8e4ee26868ec122814fc to 221cea55785980280cd1fe6d487d52139b221e8b

Branch pushed to git repo; I updated commit sha1. New commits:

98fc2b0Getting some more speedup by taking advantage of Cython.
d2b38faFixing action of ComplexReflectionGroupElement.
221cea5Making length() return a Sage integer.

comment:15 Changed 5 years ago by git

  • Commit changed from 221cea55785980280cd1fe6d487d52139b221e8b to cbe9bf269788ebda128a37a076a4a488cf03efd7

Branch pushed to git repo; I updated commit sha1. New commits:

cbe9bf2Last little bit of Cython optimization.

comment:16 Changed 5 years ago by tscrim

  • Cc darij added
  • Milestone changed from sage-7.6 to sage-8.0

This should be relatively easy to review since it is mainly refactoring code with some mild conversion to Cython (which one can just check that the [gap3] doctests pass). I'd appreciate if one of you could do so.

comment:17 Changed 5 years ago by darij

Is there a good way to know what parts are just moved and what are actually changed? I probably can't help much with the mathematical content (e.g., the noncrossing elements)...

comment:18 Changed 5 years ago by tscrim

Essentially no functionality has changed other than the addition of a native version of real reflection groups. In other words, there are no mathematical changes. There are a number of code changes for speed improvements by using Cython (with thanks to Jeroen for answering my Cython questions). Although for getting a good diff, perhaps the best is just to compare (by hand) function by function.

comment:19 Changed 5 years ago by chapoton

  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok, let it be. Doctests pass with or without gap3.

comment:20 Changed 5 years ago by tscrim

Thank you.

comment:21 Changed 5 years ago by vbraun

  • Branch changed from public/combinat/Weyl_groups_as_permutation_groups-22600 to cbe9bf269788ebda128a37a076a4a488cf03efd7
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.