"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
```