README

@
@ --------------------------------------------------------------------------
@
@ FILE: base.h
@
@ some algorithms connected with the schreier-sims algorithm are collected.
@
@ --------------------------------------------------------------------------
@
@
@ --------------------------------------------------------------------------
@
@ void init_bahn(bahn *a)
@ initialises the struct bahn, i.e. get's memory for the pointers, and
@ sets all other values to zero.
@
@ --------------------------------------------------------------------------
@
@
@ --------------------------------------------------------------------------
@
@ extern void extend_bahn(bahn **a)
@
@  bahn **a
@
@  reallocated the pointers a[0]->orbit, a[0]->generators and
@  a[0]->representatives by the amount MIN_SPEICHER, and increases
@  a[0]->speicher by this ammount.
@
@ --------------------------------------------------------------------------
@
@
@ --------------------------------------------------------------------------
@
@ void free_bahn(bahn *a)
@
@ --------------------------------------------------------------------------
@
@
@ --------------------------------------------------------------------------
@
@  int einordnen(bahn** erg,matrix_TYP *h, matrix_TYP *new_vec,int l,
@                       int flag)
@
@  bahn **erg          :  the set of base/strong generators for a finite
@                         group G. it's the ONLY variable to be changed.
@  matrix_TYP *h       :
@  matrix_TYP *new_vec :  this value is not asked for in the case
@                         described here, so any variable with the right
@                         type will do.
@  int l               :  -1          ALLWAYS
@  int flag            :  TRUE        ALLWAYS!!!!!
@
@ Inserts a new generator h into the list of strong generators for
@ any FINITE group G.
@ Therefore erg has to be the result of a call of strong_generators(..)
@ for some bravais_TYP *G.
@ The function calls itself recursively, and therefore the convention to
@ use it is somewhat cryptical. In all cases for the 'end user' l has to
@ be -1, and flag has to be TRUE (no garanties otherwise).
@ THE FUNCTION DOES NOT COPY THE VARIABLE h INTO erg[0]->generators,
@ (IT JUST STORES THE POINTER THERE), THEREFORE THE USER IS ASKED TO
@ ASSURE THAT h STAY'S IN THE SAME PLACE WHILE USING erg !!!!!!!!!!
@ The function does not check whether the new generator h is really needed,
@ so better check is out before calling this function by a call of is_element!
@ --------------------------------------------------------------------------
@
@
@-----------------------------------------------------------------------
@
@ bahn **strong_generators(matrix_TYP **base,bravais_TYP *U)
@
@  matrix_TYP **base:
@  bravais_TYP *U   :
@
@  Calculates a strong generating set according to the sims algorithm
@  for the FINITE group U and the given base.
@  This function initialises the result according to the conventions
@  made in this file. It doesn't change neither **base nor *U.
@  for U only the entries U->dim, U->gen and U->gen_no are used.
@-----------------------------------------------------------------------
@
@
@ --------------------------------------------------------------------------
@
@ int is_element(matrix_TYP *x,bravais_TYP *G,bahn **strong)
@
@      matrix_TYP *x:  the matrix in question
@      bravais_TYP *G: actually the only thing asked for is G->dim!
@      bahn **strong:  the result of a call of strong_generators(..)
@                      for the group G.
@
@  Decides whether the matrix represented by *x is contained in the
@  group described by **strong and *G respectively.
@  strong has to be the result of a call of strong_generators(..)
@  for the group G.
@  The function returns TRUE if x in G, and FALSE otherwise.
@  None of the given variables is changed.
@
@ --------------------------------------------------------------------------
@
@
@ --------------------------------------------------------------------------
@
@  int size(bahn **a)
@
@  bahn **a:   the result of a call strong_generators(...) for some
@              bravais_TYP *G.
@
@ Under this condition, the function will return the order of the group G.
@ Actually calculated is the product of a[i]->length in some ranges.
@
@ --------------------------------------------------------------------------
@
@
@ --------------------------------------------------------------------------
@
@  matrix_TYP **normalizer_in_N(bravais_TYP *U,bravais_TYP *N,int *anz,
@                                    int finite)
@
@  calculates a generating set for the normalizer of the FINITE group
@  U in the group N, and N is interpreted as generated by N->gen, N->cen and
@  N->normal. The assumption is, that U^N is FINITE.
@     bravais_TYP *U
@     bravais_TYP *N
@     int *anz
@     int finite
@  It returns the elements of the normalizer via return, and the
@  number of these via anz[0].
@  no global variables nor U or N are changed.
@  If finite == true the program assumes that the calculated normalizer
@  is finite, and tries to get hold of a set of base/strong generators
@  for it. THIS WILL WORK IFF THE CALCULATED NORMALIZER IS INDEED FINITE.
@  The program will get the record U->order and U->divisors!
@
@ --------------------------------------------------------------------------
@
@
@--------------------------------------------------------------------------
@
@ int red_gen(bravais_TYP *G,matrix_TYP **base,bahn ***strong,int i)
@
@ Tries to reduce the number of generators for the group G, and returns
@ |G|.
@
@   bravais_TYP *G:     the group in question
@   matrix_TYP **base:  a basis for the vectorspace on which G is acting
@   bahn ***strong:     after the call of this function strong[0] will
@                       contain a set of base/strong generating set for
@                       the group G.
@                       There are two cases for the call of this function
@                       1st: strong[0] == NULL
@                            the pfunction reduces the number of generators
@                            for G.
@                       2nd: strong[0] != NULL
@                            the function assummes strong[0] to contain a set
@                            of base/strong generators for the group generated
@                            by the first i generators of G, and kills
@                            those of the other generators which does not
@                            give a bigger group.
@   int i:              see above
@
@   SIDEEFFECTS:        the entries of G->gen may be changed, and they
@                       may be shuffled. G->gen_no may be changed to
@                       the number of relevant matrices.
@                       strong[0] returns a set of base/strong generators
@                       for G, NO OTHER GLOBAL VARIABLE IS CHANGED.
@
@--------------------------------------------------------------------------
@
@
@ --------------------------------------------------------------------------
@
@ FILE: base2.c
@
@ some algorithms connected with the schreier-sims algorithm are collected.
@ in contrast to the functions in base.c these functions operate mod 2,
@ so these functions are able to calculate the kernel of the minkowski
@ homomorphism as well.
@
@ --------------------------------------------------------------------------
@
@
@ --------------------------------------------------------------------------
@
@  int einordnen_2(bahn** erg,matrix_TYP *h, matrix_TYP *new_vec,int l,
@                       int flag, matrix_TYP ***K,int *anz)
@
@  bahn **erg          :  the set of base/strong generators (mod 2) for a
@                         (possibly infinite) group G. this variable will
@                         be changed!
@  matrix_TYP *h       :
@  matrix_TYP *new_vec :  this value is not asked for in the case
@                         described here, so any variable with the right
@                         type will do.
@  int l               :  -1          ALLWAYS
@  int flag            :  TRUE        ALLWAYS!!!!!
@  matrix_TYP ***K     :  this list of matrices might already contain
@                         generators for the kernel of the minkowski
@                         homomorphism. All newly found generators
@                         will be stucked in K[0][anz[0]],K[0][anz[0]+1]..
@                         and anz[0] will be changed accordingly.
@  int *anz[0]         :  see above
@
@ Inserts a new generator h into the list of strong generators (mod 2) for
@ any (possible infinite) group G.
@ The function calls itself recursively, and therefore the convention to
@ use it is somewhat cryptical. In all cases for the 'end user' l has to
@ be -1, and flag has to be TRUE (no garanties otherwise).
@ THE FUNCTION DOES NOT COPY THE VARIABLE h INTO erg[0]->generators,
@ (IT JUST STORES THE POINTER THERE), THEREFORE THE USER IS ASKED TO
@ ASSURE THAT h STAY'S IN THE SAME PLACE WHILE USING erg !!!!!!!!!!
@ The function does not check whether the new generator h is really needed,
@ so better check is out before calling this function by a call of is_element!
@ --------------------------------------------------------------------------
@
@
@-----------------------------------------------------------------------
@
@ int strong_generators_2(matrix_TYP **base,bravais_TYP *U,
@                            matrix_TYP ***K,int *anz,MP_INT *mp)
@
@  This function decides whether or not the integral group generated
@  by the matrices in U->gen[i], 0<= i< U->gen_no, is finite.
@  If so, it will return TRUE and the order of the group via the multiple
@  precision integer mp. Otherwise the function will return FALSE immediately
@  if infiniteness can be proven.
@  In the case the given group is finite it will return a generating set
@  for the kernel of the Minkowski homomorphim (g -> g mod 2) via K,
@  and the number of matrices via anz[0].
@  In case the function proves the group to be infinite, it will return
@  at least one element in K, which proves the group to ge infinite.
@
@  matrix_TYP **base: a set of U->dim integral column vectors. there are
@                     two conditions to these vectors, which are not checked:
@                     1. the vectors entries 0,1 only,
@                     2. the vectors form a basis of Z^U->dim/(2Z)^U->dim.
@  bravais_TYP *U   : the group in question. It is in no way changed.
@  matrix_TYP ***K  : the function returns elements of the minkowski kernel
@                     via this pointer.
@  int *anz         : anz[0] is the number of returned elements in K
@  MP_INT *mp       : a multiple precesion integer. Call the function with
@                     strong_generators_2(....,&x) for an MP_INT x, which
@                     has been initialized via mpz_init(&x) before.
@
@ SIDEEFECT: none are known.
@-----------------------------------------------------------------------
@
@
@ -------------------------------------------------------------------------
@ FILE: conjugate.c
@ -------------------------------------------------------------------------
@
@
@ -------------------------------------------------------------------------
@
@ matrix_TYP *conjugated(bravais_TYP *G,bravais_TYP *H,
@                        matrix_TYP **N,int Nanz,bahn **strong)
@ Suppose the matrices in G->gen, H->gen generate finite matrix groups, and N
@ generates a matrix group with the condition that the orbit of N
@ on the conjugated of G under N is finite. Then the algorithm decides
@ whether G is conjugated to a supergroup of H, and if so gives an element
@ conjugating G over H, i.e H<= X * G * X^-1 for the result of this function.
@ Declaration of variables:
@      G:       matrices generating G,
@      H:
@      N:
@      strong:   a set of base/strong generators for G returned by
@                strong_generators
@
@ Sideefects: None of the variables given nor global variables should
@             be affected.
@
@ -------------------------------------------------------------------------
@