The Hall Basis class. More...

#include <lie_basis.h>

Inheritance diagram for hall_basis:

Public Types
typedef DEG	KEY
	A default key has value 0, which is an invalid value.
typedef std::pair< KEY, KEY >	PARENT
	The parents of a key is a pair of keys. Invalid keys for letters.
Public Member Functions
	hall_basis (DEG n_letters)
	Constructs the basis with a given number of letters.
void	growup (DEG desired_degree)
	Constructs the basis up to a desired degree.
DEG	degree (const KEY &k) const
	Returns the degree (ie. weight) of a Lie key.
KEY	keyofletter (LET letter) const
	Returns the key corresponding to a letter.
KEY	lparent (const KEY &k) const
	Returns the left parent of a key.
KEY	rparent (const KEY &k) const
	Returns the right parent of a key.
bool	letter (const KEY &k) const
	Tells if a key corresponds to a letter.
LET	getletter (const KEY &k) const
	Returns the letter of a key corresponding to a letter.
KEY	begin (void) const
	Returns the value of the smallest key in the basis.
KEY	end (void) const
	Returns the key next the biggest key of the basis.
KEY	nextkey (const KEY &k) const
	Returns the key next a given key in the basis. No implicit growup made.
DEG	keypos (const KEY &k) const
	Returns the position of a key in the basis total order.
DEG	size (void) const
	Returns the size of the basis.
const std::string &	key2string (const KEY &k) const
	Converts a key to an std::string of letters.
Protected Attributes
std::vector< PARENT >	hall_set
	Parents, indexed by keys.
std::map< PARENT, KEY >	reverse_map
	Reverse map from parents to keys.
std::vector< DEG >	degrees
	Degrees, indexed by keys.
std::string	letters
	Letters, indexed by their keys.
std::map< LET, KEY >	ltk
	Maps letters to keys.
DEG	curr_degree
	Current degree, always > 0 for any valid class instance.
Friends
std::ostream &	operator<< (std::ostream &os, hall_basis &b)
	Outputs the Hall basis to an std::ostream.

Detailed Description

The Hall Basis class.

A basis is a finite total ordered set of keys, its cardinal is size() and its minimal element is begin(). The successor key of a given key is given by nextkey(). The successor of the maximal key is end() and does not belong to the basis. The position of a given key in the total order of the basis is given by keypos(), and equals 1 for begin(). To each letter corresponds a key.

This class is an ancestor of the lie_basis class, used to implement the lie class (Free Lie Algebra) as a particular instance of an algebra class (Associative Algebras).

This class stores a Philip Hall basis associated to a finite number of letters. A key is the implementation of a Lie element of this basis. A letter is a particular Lie element (or basis element, or key). Each key k which does not correspond to a letter has two parents lp and rp and we have k = [lp,rp] where [.,.] is the Lie product. A letter, viewed as a key, has no parents. More precisely, its parents are invalid keys.

The basis elements are recursively computed and are enumerated with keys. The set of valid keys is essentially an interval of natural integers.

One can find below a brief Mathematical description of Philip Hall bases for the free Lie Algebra. Cf. Reutenauer's book for example, ISBN 0 19 853679 8.

Let K be a field with characteristic non equals to 2. In newgenesis-libalgebra, this field K corresponds to the type SCA defined in libalgebra.h.

Let M be a finite alphabet {a_1,...,a_n}. We denote by M* the monoid which consists in words of letters in M. The product in M* is the concatenation and the neutral element is the empty word.

We consider the free albegra A over (K,M). An element of A is a linear combination of elements of M*, with coefficients in K. An element of A is an instance of class free_tensor<>, which affects to each element of M* a coefficient in K. The element of M* are indexed by tensor_key<>, which essentially stores the corresponding word as a std::string.

We consider also the associated free Lie albegra L, the smallest subalgebra of A which contains M and is stable by the Lie product [X,Y] = XY-YX. An element of L is an instance of class lie<>. The key used are of type lie_key<>, which are actually indexes in a basis of type lie_basis<>.

The degree of a word w in M is its length. The degree of an element of the algebra A is the maximum degree of words with non zero coefficients. The degree of [X,Y] is the sum of the degrees of X and Y if X and Y are different, and 0 if X = Y.

Actually, the free Lie algebra L is a graded algebra, with respect to the degree (or weight) of Lie products. Philip Hall invented an algorithm for computing a basis of the free Lie albegra L. A Hall basis H is a union of subsets H_1,...H_i,... of L. By definition, H_1 = M = {a_1,...,a_n} and the elements of H_i are of degree i. The set H is totally ordered and more over, H_1 < H_2 < ... The Hall basis H can be constructed recursively from H_1. This can be done by constructing an array HALLARRAY of elements of the form {left, degree , right}. The left and right corresponds to indexes in the array for constructing the element by the Lie product, and degree corresponds to the degree of this element, which is then the sum of the degrees of the two elements pointed by left and right. The order of the elements of the array is in one to one correspondance with the order of H. The subset H_i is exactly the elements of the form {left, degree , right} with degree = i.

Starting from H1 = {{0, 1, 1},...,{0, 1, n}} which corresponds to the n letters, Hi+1 is constructed from H_1, ..., H_i by examining all elements of the form {l, i + 1, r} where l < r and l and r are in the union of H_1,...,H_i. Such an element is added to the set Hi+1 if and only if the right parent of r is <= l.

Member Function Documentation

void hall_basis::growup ( DEG desired_degree ) [inline]

Constructs the basis up to a desired degree.

For performance reasons, max_degree is not checked. So be careful.

The documentation for this class was generated from the following file:

libalgebra-demo/libalgebra/lie_basis.h

hall_basis Class Reference

Public Types

Public Member Functions

Protected Attributes

Friends

Detailed Description

Member Function Documentation