"Fossies" - the Fresh Open Source Software Archive

Member "NZMATH-1.2.0/nzmath/group.py" (19 Nov 2012, 13682 Bytes) of package /linux/misc/old/NZMATH-1.2.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Python source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file. For more information about "group.py" see the Fossies "Dox" file reference documentation.

    1 """
    2 Group Theorical module
    3 """
    4 import math
    5 import nzmath.rational as rational
    6 import nzmath.factor.misc as factor_misc
    7 import nzmath.vector as vector
    8 import nzmath.matrix as matrix
    9 import nzmath.compatibility
   10 
   11 
   12 class Group:
   13     """
   14     This is a class for finite group.
   15     """
   16 
   17     def __init__(self, value, operation=-1):
   18         if isinstance(value, Group):
   19             self.entity = value.entity
   20             if operation == -1:
   21                 self.operation = value.operation
   22             else:
   23                 self.setOperation(operation)
   24         else:
   25             self.entity = value
   26             if operation == -1:
   27                 self.setOperation(0)
   28             else:
   29                 self.setOperation(operation)
   30 
   31     def __repr__(self):
   32         if hasattr(self.entity, "__repr__"):
   33             return self.entity.__repr__()
   34         else:
   35             return repr(self.entity.__class__.__name__)
   36 
   37     def __str__(self):
   38         if hasattr(self.entity, "__str__"):
   39             return self.entity.__str__()
   40         else:
   41             return str(self.entity.__class__.__name__)
   42 
   43     def __eq__(self, other):
   44         if self.entity == other.entity and self.operation == other.operation:
   45             return True
   46         else:
   47             return False
   48 
   49     def __ne__(self, other):
   50         return not (self == other)
   51 
   52     def setOperation(self, value):
   53         """
   54         Change group type for additive(0) or multiplicative(1).
   55         """
   56         if isinstance(value, int) :
   57             self.operation = (value & 1)
   58         else:
   59             raise TypeError("invalid input")
   60 
   61     def createElement(self, *value):
   62         """
   63         Create group element with value.
   64         Return GroupElement instance.
   65         """
   66         return GroupElement(self.entity.createElement(*value), self.operation)
   67 
   68     def identity(self):
   69         """
   70         Return identity element(unit).
   71         Return addtive 0 or multiplicative 1.
   72         """
   73         if hasattr(self.entity, "identity"):
   74             return GroupElement(self.entity.identity(), self.operation)
   75         else:
   76             if self.operation:
   77                 return GroupElement(self.entity.one, 1)
   78             else:
   79                 return GroupElement(self.entity.zero, 0)
   80 
   81     def grouporder(self):
   82         """
   83         Return group order(Cardinality).
   84         """
   85         order = 0
   86         if hasattr(self.entity, "grouporder"):
   87             order = self.entity.grouporder()
   88         elif hasattr(self.entity, "card"):
   89             order = card(self.entity)
   90         else:
   91             order = self.entity.m
   92         if self.operation and hasattr(self.entity, "zero"): # *-group
   93             order -= 1
   94         return order
   95 
   96 
   97 class GroupElement:
   98     """
   99     This is a class for finite group element.
  100     """
  101 
  102     def __init__(self, value, operation=-1):
  103         self.operation = operation
  104         if isinstance(value, GroupElement):
  105             self.entity = value.entity
  106             self.set = value.set
  107             self._set_name = value._set_name
  108             if operation == -1:
  109                 self.operation = value.operation
  110             else:
  111                 self.setOperation(operation)
  112         else:
  113             self.entity = value
  114             if operation == -1:
  115                 if self._type_check(1):
  116                     self.operation = 1
  117                 if self._type_check(0):
  118                     self.operation = 0
  119                 if self.operation == -1:
  120                     raise TypeError("This element isn't Group")
  121             self.set = self.getGroup()
  122             self.setOperation(self.operation) # mainly operation
  123             self._set_name = self.set.entity.__class__.__name__
  124 
  125     def __repr__(self):
  126         return self._set_name + ',' + repr(self.entity)
  127 
  128     def __str__(self):
  129         return self._set_name + ',' + str(self.entity)
  130 
  131     def __eq__(self, other):
  132         if self.entity == other.entity and self.operation == other.operation:
  133             return True
  134         else:
  135             return False
  136 
  137     def __ne__(self, other):
  138         return not (self == other)
  139 
  140     def _type_check(self, value):
  141         """
  142         Check group type is value or not.
  143         """
  144         a = self.entity
  145         if not (value & 1):
  146             if hasattr(a, "__add__") and hasattr(a, "__mul__"):
  147                 return True
  148             else:
  149                 return False
  150         else:
  151             if hasattr(a, "__mul__") and hasattr(a, "__pow__"):
  152                 return True
  153             else:
  154                 return False
  155 
  156     def setOperation(self, value):
  157         """
  158         Change group type for additive(0) or multiplicative(1).
  159         """
  160         if isinstance(value, int) and self._type_check(value):
  161             self.operation = (value & 1)
  162         else:
  163             raise TypeError("invalid input")
  164         self.set.setOperation(self.operation)
  165 
  166     def ope(self, other):
  167         """
  168         Group basic operation.
  169         """
  170         if  not self.operation:
  171             return GroupElement(self.entity + other.entity, self.operation)
  172         else:
  173             return GroupElement(self.entity * other.entity, self.operation)
  174 
  175     def ope2(self, other):
  176         """
  177         Group extended operation
  178         """
  179         if rational.isIntegerObject(other):
  180             if not self.operation:
  181                 return GroupElement(self.entity * other, self.operation)
  182             else:
  183                 return GroupElement(self.entity ** other, self.operation)
  184         else:
  185             raise TypeError("input integer")
  186 
  187     def inverse(self):
  188         """
  189         Return inverse element.
  190         """
  191         ele = self.entity
  192         cla = self.set
  193         operation = self.operation
  194         if hasattr(cla.entity, "zero") and (ele == cla.entity.zero):
  195             return self
  196         else:
  197             if not operation:
  198                 return GroupElement(-ele, operation)
  199             elif hasattr(ele, "inverse"):
  200                 return GroupElement(ele.inverse(), operation)
  201             else:
  202                 return GroupElement(self.ope2(cla.order() - 1), operation)
  203 
  204     def order(self):
  205         """
  206         Compute order using grouporder factorization.
  207         """
  208         clas = self.set.entity
  209         if hasattr(clas, "zero") and self.entity == clas.zero:
  210             return 1
  211         ordfact = factor_misc.FactoredInteger(self.set.grouporder())
  212         identity = self.set.identity()
  213         k = 1
  214         for p, e in ordfact:
  215             b = self.ope2(int(ordfact) // (p ** e))
  216             while b != identity:
  217                 k = k * p
  218                 b = b.ope2(p)
  219         return k
  220 
  221     def t_order(self, v=2):
  222         """
  223         Compute order using Terr's Baby-step Giant-step algorithm.
  224         """
  225         if (v < 1) or not(rational.isIntegerObject(v)):
  226             raise TypeError("input integer v >= 1")
  227         e = self.set.identity()
  228         a = self.set.identity()
  229         R = [(e, 0)]
  230         for i in range(1, v + 1):
  231             a = self.ope(a)
  232             if a == e:
  233                 return i
  234             else:
  235                 R.append((a, i))
  236         j = 0
  237         b = a.ope2(2)
  238         t = 2 * v
  239         while True:
  240             for (c, k) in R:
  241                 if b == c:
  242                     return (t - k)
  243             a = self.ope(a)
  244             j += 1
  245             R.append((a, j + v))
  246             b = a.ope(b)
  247             t += j + v
  248 
  249     def getGroup(self):
  250         """
  251         Return the group which element belongs.
  252         """
  253         if self._type_check(0) and self._type_check(1):
  254             if hasattr(self.entity, "getRing"):
  255                 return Group(self.entity.getRing(), self.operation)
  256             else:
  257                 return Group(self.entity, self.operation)
  258         else:
  259             if hasattr(self.entity, "getGroup"):
  260                 return Group(self.entity.getGroup(), self.operation)
  261             else:
  262                 return Group(self.entity, self.operation)
  263 
  264 
  265 class GenerateGroup(Group):
  266     """
  267     This is a class for finite group with generator.
  268     """
  269 
  270     def __init__(self, value, operation=-1, entity=None):
  271         if isinstance(value, list):
  272             temp = value
  273         else:
  274             TypeError("invalid input")
  275         if entity:
  276             self.entity = entity
  277         else:
  278             self.entity = GroupElement(value[0]).set.entity
  279         self.generator = []
  280         for a in temp:
  281             self.generator.append(GroupElement(a))
  282         if operation == -1:
  283             self.operation = self.generator[0].operation
  284         else:
  285             self.setOperation(operation)
  286 
  287     def isGroupElement(self, other):
  288         """
  289         Check whether other is self group element or not.
  290         """
  291         pass
  292 
  293     def setOperation(self, value):
  294         """
  295         Change group type for additive(0) or multiplicative(1).
  296         """
  297         if isinstance(value, int) :
  298             self.operation = (value & 1)
  299         else:
  300             raise TypeError("invalid input")
  301         for a in self.generator:
  302             a.setOperation(value)
  303 
  304 
  305 class AbelianGenerate(GenerateGroup):
  306     """
  307     This is a class for finite abelian group with genarator.
  308     """
  309 
  310     def relationLattice(self):
  311         """
  312         Return relation lattice basis as column vector matrix for generator.
  313         If B[j]=transpose(b[1,j],b[2,j],..,b[l,j]),
  314         it satisfies that product(generator[i]**b[i,j])=1 for each j.
  315         """
  316         if not hasattr(self, "relation"):
  317             l = len(self.generator)
  318             b = matrix.RingSquareMatrix(l)
  319             H1 = [(self.identity(), vector.Vector([0] * l))]
  320             H2 = list(H1)
  321             m = 1
  322             a_baby_s, giant_s = list(H1), list(H2)
  323             pro_I1, pro_I2, pro_diag = 1, 1, 1
  324             e_vec = []
  325             g_gen = []
  326             for i in range(1, l + 1):
  327                 e_i = vector.Vector([0] * l)
  328                 e_i[i] = 1
  329                 e_vec.append(e_i)
  330                 g_gen.append(self.generator[i - 1])
  331             for j in range(1, l + 1):
  332                 e = 1
  333                 baby_s = list(a_baby_s)
  334                 baby_e = GroupElement(g_gen[j - 1])
  335                 giant_e = GroupElement(g_gen[j - 1])
  336                 flag = False
  337                 while not flag:
  338                     for (g_g, v) in giant_s:
  339                         for (g_b, w) in baby_s:
  340                             if g_g.ope(giant_e) == g_b:
  341                                 b[j] = v + w + (e * (e + 1) >> 1) * e_vec[j - 1]
  342                                 flag = True
  343                                 break
  344                         if flag:
  345                             break
  346                     if flag:
  347                         break
  348                     for (g_a, v_a) in a_baby_s:
  349                         baby_s.append((g_a.ope(baby_e), v_a - e * e_vec[j - 1]))
  350                     e += 1
  351                     baby_e = baby_e.ope(g_gen[j - 1])
  352                     giant_e = giant_e.ope(baby_e)
  353                 if (j < l) and (b[j, j] > 1):
  354                     pro_diag *= b[j, j]
  355                     pro_diag_root = math.sqrt(pro_diag)
  356                     if (b[j, j] * pro_I1) <= pro_diag_root or j == 1:
  357                         temp = list(H1)
  358                         for (g, v) in temp:
  359                             g_j_inv = g_gen[j - 1].inverse()
  360                             H1_1 = GroupElement(g)
  361                             for x in range(1, b[j, j]):
  362                                 H1_1 = H1_1.ope(g_j_inv)
  363                                 H1.append((H1_1, v + x * e_vec[j - 1]))
  364                         pro_I1 *= b[j, j]
  365                     else:
  366                         if m > 1:
  367                             temp = list(H2)
  368                             for (g, v) in temp:
  369                                 H2_1 = GroupElement(g)
  370                                 for x in range(1, b[m, m]):
  371                                     H2_1 = H2_1.ope(g_gen[m - 1])
  372                                     H2.append((H2_1, v + x * e_vec[m - 1]))
  373                             pro_I2 *= b[m, m]
  374                         m = j
  375                     s = int(math.ceil(pro_diag_root / pro_I1))
  376                     if len(H2) > 1:
  377                         t = int(math.ceil(pro_diag_root / pro_I2))
  378                     else:
  379                         t = 1
  380                     a_baby_s, giant_s = list(H1), list(H2)
  381                     g_m_inv = g_gen[m - 1].inverse()
  382                     for (h1, v) in H1:
  383                         H1_1 = GroupElement(h1)
  384                         for r in range(1, s):
  385                             H1_1 = H1_1.ope(g_m_inv)
  386                             a_baby_s.append((H1_1, v + r * e_vec[m - 1]))
  387                     g_m_s = g_gen[m - 1].ope2(s)
  388                     for (h2, v) in H2:
  389                         H2_1 = GroupElement(h2)
  390                         for q in range(1, t):
  391                             H2_1 = H2_1.ope(g_m_s)
  392                             giant_s.append((H2_1, v + (q * s) * e_vec[m - 1]))
  393             self.relation = b
  394         return self.relation
  395 
  396     def computeStructure(self):
  397         """
  398         Compute Finite Abelian Group Structure.
  399         """
  400         B = self.relationLattice()
  401         U_d, V, M = B.extsmithNormalForm()
  402         det = M.determinant()
  403         U_d.toFieldMatrix()
  404         U = U_d.inverse()
  405         for i in range(U_d.row):
  406             U_d[i] = (U_d[i] % det)
  407         structure = []
  408         l = M.row
  409         for j in range(1, l):
  410             if M[j, j] != 1 or j == 1:
  411                 g = self.identity()
  412                 for i in range(1, l+1):
  413                     g = g.ope(self.generator[i-1].ope2(int(U[i, j])))
  414                 structure.append((g, M[j, j]))
  415             else:
  416                 break
  417         return structure, det