# johnkerl/sack

Switch branches/tags
Nothing to show
Fetching contributors…
Cannot retrieve contributors at this time
executable file 252 lines (211 sloc) 6.32 KB
 #!/usr/bin/python -Wall # ================================================================ # Please see LICENSE.txt in the same directory as this file. # John Kerl # kerl.john.r@gmail.com # 2007-05-31 # ================================================================ import sys import re import copy # ================================================================ # Type module for complex group algebras CG, with sparse storage. # # Initial attempt at complex group algebras CG for small finite groups G. This # could, conceivably, be generalized to FG (for arbitrary user-specified # fields) or RG (for arbitrary user-specified rings). # # There are two possible storage representations for an element of CG: # * Sparse: Keep a list of non-zero coefficients, with their # corresponding group elements. # * Dense: Keep a list of group elements in each algebra element, with # another list of coefficients. # # For now I will attempt the former. A "pair" is a two-element list of # coefficient and group element; an algebra element is a list of pairs. # # ================================================================ # John Kerl # 2007-05-08 # ================================================================ class cgpalg_t: def __init__(self, pairs_array): self.pairs = copy.deepcopy(pairs_array) def index_of(self, g): for k in range(0, len(self.pairs)): if (g == self.pairs[k][1]): return [1, k] return [0, 0] def zero_strip(self): untested = self.pairs self.pairs = [] while (untested): x = untested[0] untested = untested[1:] if (x[0] != 0): self.pairs += [x] # I am using sparse storage. However, this routine permits a dense # extraction of coefficients: Given an array of group elements, it # returns a list of coefficients (in the same order). # # This makes it possible to hand the results off to a linear-algebra # routine. def to_coef_array(self, group_elements): coefs = [] for g in group_elements: coef = 0 [found, k] = self.index_of(g) if (found): coef = self.pairs[k][0] coefs += [coef] return coefs def __add__(a,b): # Concatenate the two lists. Then merge the pairs with matching # group elements. c = cgpalg_t([]) unmerged_pairs = copy.deepcopy(a.pairs + b.pairs) while (unmerged_pairs): current_pair = unmerged_pairs[0] [found, k] = c.index_of(current_pair[1]) if (found): # Update c.pairs[k][0] += current_pair[0] else: # Insert c.pairs += [current_pair] unmerged_pairs = unmerged_pairs[1:] return c def __neg__(b): negb = cgpalg_t(b.pairs) for k in range(0, len(negb.pairs)): negb.pairs[k][0] = -negb.pairs[k][0] return negb def __sub__(a,b): return a + (-b) def __mul__(a,b): c = cgpalg_t([]) for ap in a.pairs: for bp in b.pairs: ccoef = ap[0] * bp[0] # Field multiplication cgpelt = ap[1] * bp[1] # Group multiplication [found, k] = c.index_of(cgpelt) if (found): # Update c.pairs[k][0] += ccoef else: # Insert c.pairs += [[ccoef, cgpelt]] c.zero_strip() return c # The group data type must support the inv() method. # This is a stub for correct implementation and doesn't work (except for singletons). def inv(self): bi = cgpalg_t([]) n = len(self.pairs) if (n == 0): print "cgpalg_t.inv: division by zero." sys.exit(1) recip_n = 1.0/n for pair in self.pairs: bi.pairs += [[recip_n/pair[0], pair[1].inv()]] return bi def __div__(a,b): return a * b.inv() # def __eq__(a,b): # if (len(a.pairs) != len(b.pairs)): # return 0 # n = len(a.coefs) # for i in range(0, n): # if (a.coefs[i] != b.coefs[i]): # return 0 # return 1 # def __ne__(a,b): # return not (a == b) # def scan(self, res_string, cgpalg_array): # res_strings = re.split(',', res_string) # #self.check_lengths(len(res_strings), len(cgpalg_array), res_strings, # str(cgpalg_strings)) # n = len(res_strings) # coef_array = range(0, n) # for i in range(0, n): # coef_array[i] = int(res_strings[i]) # self.__init__(coef_array, gp_elt_array) def __str__(self): string = "" if (len(self.pairs) == 0): string = "0" for i in range(0, len(self.pairs)): if (i > 0): string += " " string += "[" string += str(self.pairs[i][0]) string += "]*[" string += str(self.pairs[i][1]) string += "]" return string def __repr__(self): return self.__str__() # Construct an element of C S_n, given only a list of permutations: each # coefficient is 1. def from_pmtns(pmtn_array): pairs = [] for pmtn in pmtn_array: pairs += [[1, pmtn]] return cgpalg_t(pairs) # Construct an element of C S_n, given only a list of permutations: compute the # coefficient from the parity. The group class being used must support the # sgn() method. def from_pmtns_with_parity(pmtn_array): pairs = [] for pmtn in pmtn_array: pairs += [[pmtn.sgn(), pmtn]] return cgpalg_t(pairs) #def params_from_string(params_string): # if (len(params_string) == 0): # print "Modadd requires non-empty parameter string" # sys.exit(1) # cgpalg_strings = re.split(',', params_string) # n = len(cgpalg_strings) # cgpalg_array = range(0, n) # for i in range(0, n): # cgpalg_array[i] = int(cgpalg_strings[i]) # return cgpalg_array #def from_string(value_string, params_string): # cgpalg_array = params_from_string(params_string) # obj = cgpalg_t([1], [1]) # obj.scan(value_string, cgpalg_array) # return obj # ================================================================ import unittest if __name__ == '__main__': class test_cases(unittest.TestCase): def test___init__(self): pass # to be implemented def test_index_of(self): pass # to be implemented def test_zero_strip(self): pass # to be implemented def test_to_coef_array(self): pass # to be implemented def test___add__(self): pass # to be implemented def test___neg__(self): pass # to be implemented def test___sub__(self): pass # to be implemented def test___mul__(self): pass # to be implemented def test_inv(self): pass # to be implemented def test___div__(self): pass # to be implemented def test___str__(self): pass # to be implemented def test___repr__(self): pass # to be implemented def test_from_pmtns(self): pass # to be implemented def test_from_pmtns_with_parity(self): pass # to be implemented # ---------------------------------------------------------------- unittest.main()