atlas  0.6
Public Member Functions | Private Member Functions | Private Attributes | List of all members
atlas::weyl::WeylGroup Class Reference

Represents a Weyl group for the purpose of manipulating its elements. More...

#include <weyl.h>

Collaboration diagram for atlas::weyl::WeylGroup:
Collaboration graph
[legend]

Public Member Functions

 WeylGroup (const int_Matrix &cartan)
 Build the Weyl group corresponding to the Cartan matrix c, and incorporate the possibly given twist (take identity if |twist==NULL|). More...
 
WeylElt generator (Generator i) const
 
int mult (WeylElt &w, Generator s) const
 
void mult (WeylElt &w, const WeylElt &v) const
 Multiply w on the right by v, and put the product in w: w*=v. More...
 
void mult (WeylElt &, const WeylWord &) const
 Multiply w on the right by v, and put the product in w: w*=v. More...
 
int leftMult (WeylElt &w, Generator s) const
 
void leftMult (WeylElt &w, const WeylWord &ww) const
 
void leftMult (WeylElt &w, const WeylElt &x) const
 set |w=xw| More...
 
WeylElt prod (const WeylElt &w, Generator s) const
 
WeylElt prod (Generator s, const WeylElt &w) const
 
WeylElt prod (const WeylElt &w, const WeylElt &v) const
 
WeylElt prod (const WeylElt &w, const WeylWord &ww) const
 
WeylElt prod (const WeylWord &ww, const WeylElt &w) const
 
unsigned int length (const WeylElt &) const
 Returns the length of w. More...
 
int length_change (WeylElt w, Generator s) const
 
int length_change (Generator s, const WeylElt &w) const
 
Generator letter (const WeylElt &w, unsigned int i) const
 
void conjugacyClass (WeylEltList &, const WeylElt &) const
 Puts into |c| the conjugacy class of |w|. More...
 
void conjugate (WeylElt &w, Generator s) const
 Conjugates |w| by the generator |s|: |w=sws|. More...
 
WeylElt inverse (const WeylElt &w) const
 $w^(-1)$ More...
 
void invert (WeylElt &w) const
 set |w=w^(-1)| More...
 
Generator leftDescent (const WeylElt &w) const
 return a left descent for |w|, or |UndefGenerator| if |w==e| More...
 
bool commutes (Generator s, Generator t) const
 
const WeylEltlongest () const
 
Generator Chevalley_dual (Generator s) const
 
WeylElt opposite (const WeylElt &w) const
 
unsigned long maxlength () const
 
const size::Sizeorder () const
 the order of the Weyl group More...
 
size_t rank () const
 
WeylWord word (const WeylElt &w) const
 
WeylElt element (const WeylWord &ww) const
 
WeylEltList reflections () const
 Returns the list of all reflections (conjugates of generators). More...
 
unsigned long toUlong (const WeylElt &w) const
 
WeylElt toWeylElt (unsigned long) const
 Returns the WeylElt whose packed form is u. More...
 
bool hasDescent (Generator, const WeylElt &) const
 Tells whether sw < w. More...
 
bool hasDescent (const WeylElt &, Generator) const
 
WeylElt translation (const WeylElt &w, const WeylInterface &f) const
 Applies to |w| the generator permutation in |I|, which should be an automorphism of the Dynkin diagram, expressed in terms of outer numbering. More...
 
void translate (WeylElt &w, const WeylInterface &i) const
 
void act (const RootDatum &rd, const WeylElt &w, RootNbr &alpha) const
 
template<typename C >
void act (const RootDatum &rd, const WeylElt &w, matrix::Vector< C > &v) const
 
void act (const RootDatum &rd, const WeylElt &w, RatWeight &v) const
 
void act (const RootDatum &rd, const WeylElt &w, LatticeMatrix &M) const
 
template<typename C >
void act (const PreRootDatum &prd, const WeylElt &w, matrix::Vector< C > &v) const
 
void act (const PreRootDatum &prd, const WeylElt &w, RatWeight &v) const
 
void act (const PreRootDatum &prd, const WeylElt &w, LatticeMatrix &M) const
 
Weight image_by (const RootDatum &rd, const WeylElt &w, Weight v) const
 Nondestructive version of |act| method. More...
 
void inverse_act (const RootDatum &rd, const WeylElt &w, Weight &v) const
 Same as |act(rd,inverse(w),v)|, but avoiding computation of |inverse(w)|. Here the leftmost factors act first. More...
 
Weight image_by_inverse (const RootDatum &rd, const WeylElt &w, Weight v) const
 Nondestructive version of |inverse_act| method. More...
 

Private Member Functions

 WeylGroup (const WeylGroup &)
 
int multIn (WeylElt &w, Generator s) const
 Multiply w on the right by internally numbered generator s: w *= s. More...
 
int multIn (WeylElt &w, const WeylWord &v) const
 Multiply w on the right by v (in internal numbering): w *= v. More...
 
int leftMultIn (WeylElt &w, Generator s) const
 Transforms w into s*w, with s in internal numbering; returns $l(sw)-l(w)\{+1,-1}$. More...
 
const WeylWordwordPiece (const WeylElt &w, Generator j) const
 
Generator min_neighbor (Generator s) const
 first generator $<s$ not commuting with |s|, or |s| if none exist More...
 
WeylElt genIn (Generator i) const
 

Private Attributes

size_t d_rank
 
size::Size d_order
 
unsigned long d_maxlength
 
WeylElt d_longest
 
int_Matrix d_coxeterMatrix
 
Twist Chevalley
 
std::vector< Transducerd_transducer
 
WeylInterface d_in
 
WeylInterface d_out
 
std::vector< Generatord_min_star
 

Detailed Description

Represents a Weyl group for the purpose of manipulating its elements.

The WeylGroup class is a variation on Fokko's own and favourite implementation in terms of transducers.

I have tried to make a careful choice of datatype for the group elements in order to strike the right balance between efficiency and generality. [Since this is Fokko's mathematics as well as his code, I have tried to keep his voice. Occasional amplifications are in brackets. DV 7/23/06.] This has led me to the choice of fixed size arrays of unsigned chars, representing the "parabolic subquotient" representation of a given element; in other words, in a group of rank n, the first n elements of the array are used (but since it is fixed size, we have to allocate it to some constant value, namely RANK_MAX.)

[Meaning of "parabolic subquotient representation: one orders the simple generators in an appropriate fashion s_1,...,s_n (henceforth called the "internal representation). Define W_i = <s_1,...,s_i>, so that W_0 = {1} subset W_1 subset W_2 subset ... subset W_n = W. Each W_i is a parabolic subgroup of W, so its length function is the restriction of that of W. Each right coset in W_{i-1}\W_i has a unique minimal length coset representative. Write N_i for the number of cosets (or representatives). Then the cardinality of W is N_1.N_2...N_n. More precisely, and element of W has a unique factorization as x_1.x_2...x_n, with x_i one of the N_i minimal length coset representatives of W_{i-1}\W_i.

The key to the implementation is to order the generators in such a way that every parabolic subquotient W_{i-1}\W_i has cardinality fitting into an unsigned char: that is, cardinality at most 256. (This is possible for any Weyl group of rank at most 128.) A WeylElt is an array of unsigned char of size RANK_MAX; the unsigned char in entry i is the number of the factor x_i.

There is a little more about how the group structure is computed in this representation in the description of the class Transducer. The mathematical reference is Fokko du Cloux, "A transducer approach to Coxeter groups," J. Symbolic Computation 27 (1999), 311-324.]

This is not so wasteful as it may sound : of course the representation as a single number is more compact, but will overflow even on 64-bit machines for some groups of rank <= 16, and much sooner of course on 32-bit machines; also it imposes some computational overhead for packing and unpacking.

[Meaning of "representation as a single number:" if the cardinality of W fits in an unsigned long, then an element of W may be represented as the unsigned long

x_1 + x_2(N_1) + x_3(N_1N_2) + ... +x_n(N_1...N_n).

In this formula I have changed the meaning of x_i: now it means the integer between 0 and N_i enumerating the coset representative previously called x_i. This representation is called the "packed form" in the software. On a 32 bit machine, this representation works for W(E8), but not for W(A12) (which has order 13!, which is about 1.5 x 2^{32}).]

Any variable-size structure like the STL vector uses already three unsigned longs for its control structure (the address of the data, the size and the capacity), and then it still has to allocate. This could perhaps be simplified to just a pointer (after all the size of the allocation is known to the group) but you still have the big overhead of allocating and deallocating memory from the heap, and remembering to delete the pointers when they go out of scope, or else use autopointers ...

And if worst comes to worst and one really is worried about a factor 2 waste for type E8 (which might be significant if one deals with huge containers of group elements), then one can still recompile with RANK_MAX=8, which will then give a datatype that in 64 bits is the same size as an unsigned long.

Notice that the unsigned char type miraculously suffices for all subquotients of all groups up to rank 128 (indeed, the biggest subquotient for B128 is of order 256), provided the generators are enumerated in an appropriate order. This forces us to do quite a bit of type recognition, which is relegated to the dynkin namespace. Because of this reordering, the group carries a little interface that will translate back and forth from the external ordering and the internal one. To speed up some computations we precompute in |d_min_star| for each generator the smallest other generator with which it does not commute (or the generator itself if there are none).

Constructor & Destructor Documentation

atlas::weyl::WeylGroup::WeylGroup ( const WeylGroup )
private
atlas::weyl::WeylGroup::WeylGroup ( const int_Matrix c)

Build the Weyl group corresponding to the Cartan matrix c, and incorporate the possibly given twist (take identity if |twist==NULL|).

NOTE : |c| and |twist| use some (consistent) labelling of simple roots, but we will determine an internal renumbering making the subquotients small

Member Function Documentation

void atlas::weyl::WeylGroup::act ( const RootDatum &  rd,
const WeylElt w,
RootNbr alpha 
) const
template<typename C >
void atlas::weyl::WeylGroup::act ( const RootDatum &  rd,
const WeylElt w,
matrix::Vector< C > &  v 
) const
void atlas::weyl::WeylGroup::act ( const RootDatum &  rd,
const WeylElt w,
RatWeight v 
) const
void atlas::weyl::WeylGroup::act ( const RootDatum &  rd,
const WeylElt w,
LatticeMatrix M 
) const
template<typename C >
void atlas::weyl::WeylGroup::act ( const PreRootDatum &  prd,
const WeylElt w,
matrix::Vector< C > &  v 
) const
void atlas::weyl::WeylGroup::act ( const PreRootDatum &  prd,
const WeylElt w,
RatWeight v 
) const
void atlas::weyl::WeylGroup::act ( const PreRootDatum &  prd,
const WeylElt w,
LatticeMatrix M 
) const
Generator atlas::weyl::WeylGroup::Chevalley_dual ( Generator  s) const
inline
bool atlas::weyl::WeylGroup::commutes ( Generator  s,
Generator  t 
) const
inline
void atlas::weyl::WeylGroup::conjugacyClass ( WeylEltList c,
const WeylElt w 
) const

Puts into |c| the conjugacy class of |w|.

Algorithm: straightforward enumeration of the connected component of |w| in the graph defined by the operation conjugatee, using a |std::set| structure to record previously encountered elements and a |stdstack| to store elements whose neighbors have not yet been generated.

void atlas::weyl::WeylGroup::conjugate ( WeylElt w,
Generator  s 
) const
inline

Conjugates |w| by the generator |s|: |w=sws|.

WeylElt atlas::weyl::WeylGroup::element ( const WeylWord ww) const
inline
WeylElt atlas::weyl::WeylGroup::generator ( Generator  i) const
inline
WeylElt atlas::weyl::WeylGroup::genIn ( Generator  i) const
private
bool atlas::weyl::WeylGroup::hasDescent ( Generator  s,
const WeylElt w 
) const

Tells whether sw < w.

Method: we multiply from $s$ to $sw$, at least by the word pieces of |w| at the relevant pieces: those from |min_neighbor(s)| to |s| inclusive. If any descent occurs we return |true|, otherwise |false|. Despite the double loop below, this question is resolved in relatively few operations on the average.

bool atlas::weyl::WeylGroup::hasDescent ( const WeylElt w,
Generator  s 
) const
Weight atlas::weyl::WeylGroup::image_by ( const RootDatum &  rd,
const WeylElt w,
Weight  v 
) const
inline

Nondestructive version of |act| method.

Weight atlas::weyl::WeylGroup::image_by_inverse ( const RootDatum &  rd,
const WeylElt w,
Weight  v 
) const
inline

Nondestructive version of |inverse_act| method.

WeylElt atlas::weyl::WeylGroup::inverse ( const WeylElt w) const

$w^(-1)$

return inverse of |w|

Algorithm: read backwards the reduced expression gotten from the pieces of w.

void atlas::weyl::WeylGroup::inverse_act ( const RootDatum &  rd,
const WeylElt w,
Weight v 
) const

Same as |act(rd,inverse(w),v)|, but avoiding computation of |inverse(w)|. Here the leftmost factors act first.

void atlas::weyl::WeylGroup::invert ( WeylElt w) const
inline

set |w=w^(-1)|

Generator atlas::weyl::WeylGroup::leftDescent ( const WeylElt w) const

return a left descent for |w|, or |UndefGenerator| if |w==e|

Returns a left descent generator for |w|, or |UndefGenerator| if there is no such (i.e., if $w = e$). In fact this is the index |i| of the first piece of |w| that is not 0 (identity), converted to external numbering, since the canonical (minimal for ShortLex) expression for |w| starts with this letter. Returning the first generator in external numbering would take a bit more time, as we would have to repeatedly use |hasDescent|.

In fact the descent whose internal number is lowest is returned, but converted to external numbering.

int atlas::weyl::WeylGroup::leftMult ( WeylElt w,
Generator  s 
) const
inline
void atlas::weyl::WeylGroup::leftMult ( WeylElt w,
const WeylWord ww 
) const
inline
void atlas::weyl::WeylGroup::leftMult ( WeylElt w,
const WeylElt x 
) const

set |w=xw|

int atlas::weyl::WeylGroup::leftMultIn ( WeylElt w,
Generator  s 
) const
private

Transforms w into s*w, with s in internal numbering; returns $l(sw)-l(w)\{+1,-1}$.

Algorithm: note that our transducers are geared towards right multiplication by a generator. But we note that passing from $w$ to $sw$ only affects the pieces $x_j$ in $w$ for $t <= j <= s$, where |t=min_neighbor(s)| is the first generator that does not commute with |s| (remarkably, if $v$ is the product of those pieces, $sv$ does have non-zero components only for that set of indices; hard to believe at first but easy to prove).

unsigned int atlas::weyl::WeylGroup::length ( const WeylElt w) const

Returns the length of w.

This is relatively efficient (compared to |involutionLength|)

int atlas::weyl::WeylGroup::length_change ( WeylElt  w,
Generator  s 
) const
inline
int atlas::weyl::WeylGroup::length_change ( Generator  s,
const WeylElt w 
) const
inline
Generator atlas::weyl::WeylGroup::letter ( const WeylElt w,
unsigned int  i 
) const
const WeylElt& atlas::weyl::WeylGroup::longest ( ) const
inline
unsigned long atlas::weyl::WeylGroup::maxlength ( ) const
inline
Generator atlas::weyl::WeylGroup::min_neighbor ( Generator  s) const
inlineprivate

first generator $<s$ not commuting with |s|, or |s| if none exist

int atlas::weyl::WeylGroup::mult ( WeylElt w,
Generator  s 
) const
inline
void atlas::weyl::WeylGroup::mult ( WeylElt w,
const WeylElt v 
) const

Multiply w on the right by v, and put the product in w: w*=v.

Algorithm: increment w by the various pieces of v, whose reduced expressions are available from the transducer.

void atlas::weyl::WeylGroup::mult ( WeylElt w,
const WeylWord v 
) const

Multiply w on the right by v, and put the product in w: w*=v.

Algorithm: do the elementary multiplication by the generators, running through v left-to-right.

int atlas::weyl::WeylGroup::multIn ( WeylElt w,
Generator  s 
) const
private

Multiply w on the right by internally numbered generator s: w *= s.

Returns +1 if the length moves up, -1 if the length goes down.

This just means exercising the transducer tables as they were designed to.

int atlas::weyl::WeylGroup::multIn ( WeylElt w,
const WeylWord v 
) const
private

Multiply w on the right by v (in internal numbering): w *= v.

Returns nonpositive even value $l(wv)-l(w)-l(v)$

Precondition: v is written in the internal generators.

Algorithm: do the elementary multiplication by the generators, running through v left-to-right.

WeylElt atlas::weyl::WeylGroup::opposite ( const WeylElt w) const
inline
const size::Size& atlas::weyl::WeylGroup::order ( ) const
inline

the order of the Weyl group

WeylElt atlas::weyl::WeylGroup::prod ( const WeylElt w,
Generator  s 
) const
inline
WeylElt atlas::weyl::WeylGroup::prod ( Generator  s,
const WeylElt w 
) const
inline
WeylElt atlas::weyl::WeylGroup::prod ( const WeylElt w,
const WeylElt v 
) const
inline
WeylElt atlas::weyl::WeylGroup::prod ( const WeylElt w,
const WeylWord ww 
) const
inline
WeylElt atlas::weyl::WeylGroup::prod ( const WeylWord ww,
const WeylElt w 
) const
inline
size_t atlas::weyl::WeylGroup::rank ( ) const
inline
WeylEltList atlas::weyl::WeylGroup::reflections ( ) const

Returns the list of all reflections (conjugates of generators).

NOTE: the ordering of the reflections is the ordering induced by our operator<, which is not very significative mathematically, but has the advantage that the STL search tools may be used.

unsigned long atlas::weyl::WeylGroup::toUlong ( const WeylElt w) const

$ is the value of piece |i|, the value is $a_0+N_0*(a_1+N_1*(a_2+... N_{n-2}*(a_{n-1})...))$

WeylElt atlas::weyl::WeylGroup::toWeylElt ( unsigned long  u) const

Returns the WeylElt whose packed form is u.

Its pieces for the mixed-radix representation of |u|, which as usual can be found starting at the least significant end by repeated Euclidean divisions

void atlas::weyl::WeylGroup::translate ( WeylElt w,
const WeylInterface i 
) const
inline
WeylElt atlas::weyl::WeylGroup::translation ( const WeylElt w,
const WeylInterface f 
) const

Applies to |w| the generator permutation in |I|, which should be an automorphism of the Dynkin diagram, expressed in terms of outer numbering.

Algorithm: we use the standard reduced decomposition of |w|, and rebuild the return value by repeated right-multiplication. We can do the multiplication in the same Weyl group as the decomposition because |I| is supposed to be an automorphism; if it weren't we would need a reference to a second Weyl group.

WeylWord atlas::weyl::WeylGroup::word ( const WeylElt w) const
const WeylWord& atlas::weyl::WeylGroup::wordPiece ( const WeylElt w,
Generator  j 
) const
inlineprivate

Member Data Documentation

Twist atlas::weyl::WeylGroup::Chevalley
private
int_Matrix atlas::weyl::WeylGroup::d_coxeterMatrix
private
WeylInterface atlas::weyl::WeylGroup::d_in
private
WeylElt atlas::weyl::WeylGroup::d_longest
private
unsigned long atlas::weyl::WeylGroup::d_maxlength
private
std::vector<Generator> atlas::weyl::WeylGroup::d_min_star
private
size::Size atlas::weyl::WeylGroup::d_order
private
WeylInterface atlas::weyl::WeylGroup::d_out
private
size_t atlas::weyl::WeylGroup::d_rank
private
std::vector<Transducer> atlas::weyl::WeylGroup::d_transducer
private

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