 |
atlas
0.6
|
Represents a Weyl group for the purpose of manipulating its elements. More...
#include <weyl.h>
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 WeylElt & | longest () const |
| Generator | Chevalley_dual (Generator s) const |
| WeylElt | opposite (const WeylElt &w) const |
| unsigned long | maxlength () const |
| const size::Size & | order () 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 WeylWord & | wordPiece (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< Transducer > | d_transducer |
| WeylInterface | d_in |
| WeylInterface | d_out |
| std::vector< Generator > | d_min_star |
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).
|
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
| 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, | ||
| LatticeMatrix & | M | ||
| ) | const |
| 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 |
| 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.
Conjugates |w| by the generator |s|: |w=sws|.
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.
|
inline |
Nondestructive version of |act| method.
|
inline |
Nondestructive version of |inverse_act| method.
$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.
|
inline |
set |w=w^(-1)|
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.
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|)
|
inline |
|
inline |
first generator $<s$ not commuting with |s|, or |s| if none exist
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.
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.
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.
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.
|
inline |
the order of the Weyl group
|
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
|
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.
|
inlineprivate |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
1.8.11
