The Word Generator

Detailed Description

Given a finitely generated matrix algebra A, the word generator produces a sequence of "random" elements of A, i.e., words in the generators. Words are numbered starting with 1. Here is an example demonstrating the usage of the word generator:

MatRep_t *rep;
...
WgData_t *wg = WgAlloc(rep);
Matrix_t *word = WgMakeWord(wg,1833);
long nul = MatNullity__(word);
printf("Word 1833 has nullity %ld\n",nul);
WgFree(wg);

The generator produces words in blocks of 238, i.e., words 1 to 238 belong to block 1, words 239 to 476 to block 2 and so on. For each block, 8 monomials a,b,...,h in the generators are chosen by calculating "random" products of the generators. Then, all possible sums of 2 up to 6 of the monomials are calculated, yielding 238 words. The order in which these sums are taken is fixed: a+b+c, a+b+c+f, a+d+e+g+h, a+b+d+e+g+h, ..., c+d+e+f+g+h. See the BitTab[] array in wgen.c for the complete list.

Remark: since the generators are often invertible and the word generator is typically used to find words with a small but nontrival kernel, it is a good idea to take at least two summands. There seems to be no reason, however, why sums of 7 or 8 monomials are not used.

The calculation of a...h involves a simple pseudorandom number generator which is seeded with the block number, and some magic including the use of fixed recipes for the first two blocks (words 1 to 476). The number of factors in any monomial is limited to 5 for the first 200 blocks, to 6 for blocks 200 to 1999, and to 7 for blocks 2000 to 19999. For example, assuming two generators x and y, the summand xyxyxyx has 7 factors and thus cannot appear before block 2000, which means not before word 476000.

Data Structures
class	WgData_t
	Word Generator Data. More...

Functions
const char *	WgSymbolicName (WgData_t *b, long n)
	Symbolic name of a word. More...
int *	WgDescribeWord (WgData_t *b, long n)
	Creates a symbolic description of a word. More...
Matrix_t *	WgMakeWord (WgData_t *b, long n)
	Calculates a Word. More...
WgData_t *	WgAlloc (const MatRep_t *rep)
	Initialize the word generator. More...
int	WgFree (WgData_t *b)
	Terminate the word generator. More...
void	WgMakeFingerPrint (WgData_t *b, int fp[6])
	Calculate finger print. More...

Function Documentation

WgAlloc()

WgData_t* WgAlloc

(

const MatRep_t *

rep

)

Initialize the word generator.

This function initializes the word generator for a given matrix representation rep. There must be at least one generator. On success, WgAlloc() returns a pointer to an internal data structure which can be used in subsequent calls to WgMakeWord() and WgFree(). If an error occurs, the return value is 0.

Note that the word generator does not create internal copies of the generators. The caller must assure that the generators are not deleted or modified as long as the word generator is in use.

Parameters

rep	Pointer to the matrix representation.

Returns

Pointer to a new word generator data structure or 0 on error.

WgDescribeWord()

int* WgDescribeWord	(	WgData_t *	b,
		long	n
	)

Creates a symbolic description of a word.

Stores the description of the given word in «b->Description». The description is a sequence of monomials terminated by -1. Each monomial itself is a sequence of integers, again terminated by -1, specifying the generators that must be multiplied to obtain the monomial. The word is the sum of the monomials.

For example a+b+baa would be represented as 0,-1,1,-1,1,0,0,-1,-1.

«b->Description» is overwritten each time this function is called and should treated as read-only. In particular, do not attempt to free or reallocate the buffer!

Parameters

b	Word generator.
n	Wird number.

WgFree()

int WgFree

(

WgData_t *

b

)

Terminate the word generator.

Parameters

b	Pointer to word generator data.

Returns

0 on success, -1 on error. This function terminates the word generator and cleans up internal data structures. Note that the generators that were passed to WgAlloc() are not freed.

WgMakeFingerPrint()

void WgMakeFingerPrint	(	WgData_t *	b,
		int	fp[6]
	)

Calculate finger print.

This function calculates the "finger print" of a module, i.e. the nullities of the first 6 words.

Parameters

b	Word generator data.
fp	Buffer for the finger print (6 numbers).

WgMakeWord()

Matrix_t* WgMakeWord	(	WgData_t *	b,
		long	n
	)

Calculates a Word.

This function calculates an element in a matrix algebra, given its number. Generators for the algebra are specified when the WgData_t structure is allocated with WgAlloc().

Parameters

b	Pointer to word generator data.
n	Word number.

Returns

Matrix representation of the word or 0 on error.

WgSymbolicName()

const char* WgSymbolicName	(	WgData_t *	b,
		long	n
	)

Symbolic name of a word.

This function returns a symbolic representation of the word n as a polynomial in the generators. The generators are named a, b, c... The return value is a pointer to a static buffer which is overwritten on each call.

Parameters

b	Pointer to word generator data.
n	Word number.

Returns

Symbolic name of the word.