{'fraction_non_alphanumeric': 0.04926474795445442, 'fraction_numerical': 0.012673799851233049, 'mean_word_length': 3.696358995028886, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Computing in unipotent and reductive algebraic groups

The unipotent groups are an important class of algebraic groups. We show that techniques used to compute with finitely generated nilpotent groups carry over to unipotent groups. We concentrate particularly on the maximal unipotent subgroup of a split reductive group and show how this improves computation in the reductive group itself.


Introduction
A linear algebraic group is unipotent if its elements are unipotent (ie, the elements only have eigenvalue one in every representation). Unipotent groups play a prominent role in the theory of algebraic groups. In this paper, we present algorithms for efficient element operations in unipotent groups. Since unipotent groups are nilpotent, we adapt methods used for computing in finitely generated nilpotent groups. A PC group provides a unique computer representation for the elements of nilpotent groups (see, for example, [HEO05]). Collection gives efficient algorithms for multiplication and inversion of group elements. We modify these concepts to work with a large class of unipotent groups defined over a field. This class contains all unipotent groups if the field has characteristic zero. It also contains the full unipotent subgroup of every split reductive group.
Algorithms for element operations in split reductive algebraic groups are given in [CMT04]. Computations in the unipotent subgroup make the largest single contribution to the time taken by these algorithms. This was the main impetus for the current paper, in which we prove: Theorem 1.1. Let F be a field with effective algorithms for the basic element operations. Let G be a split reductive algebraic group over F with rank n. Then there is a normal form for elements of G(F). The word problem for elements in normal form requires O(n 2 ) field operations, and multiplying or inverting them requires O(n 3 ) field operations.
This theorem is a great improvement over the analysis of [CMT04], where we proved that the operations are polynomial time, but did not compute the exponent. This result is optimal in the sense that the timings are asymptotically the same as the straightforward methods for matrices.
In Section 2, we construct FC group schemes, which give normal forms for elements of unipotent groups. We adapt two basic collection strategies in Section 3. We have developed two new algorithms for the full unipotent subgroup of a split reductive algebraic group: The first is a new collection strategy called collection from the outside (Section 4). The second is a direct method for computing products and inverses in classical groups using standard representations (Section 5). Section 6 gives the asymptotic analysis and the proof of Theorem 1.1. Section 7 compares practical timings for the various methods considered and describes the default method used in Magma [BCP97] from version 2.13.

Unipotent groups and presentations
Throughout this paper, F is a field and E is a commutative unital algebra over F. We assume that we have effective algorithms for the basic element operations in F and E. We find it convenient to use the scheme-theoretic definition of algebraic groups. So an algebraic group defined over F is a functor from the category of all commutative unital algebras over F to the category of groups, satisfying the appropriate additional conditions [DG70,Wat79]. If G is an algebraic group, then G(E) is an abstract group, called the rational point group of G over E. For example, the additive group G a has rational point group G a (E) = E + .
We define an F-unipotent group to be an algebraic group defined over F with a normal series in which every quotient is isomorphic to G a . This is analogous to the definition of an F-soluble algebraic group in [DG70].
Proposition 2.1. Over a perfect field F, every connected unipotent group is Funipotent. Over a field F of characteristic zero, every unipotent group is F-unipotent.
Proof. The first statement follows from [Ros57, Proposition 5, Corollary 2]. The second follows from the first using the standard fact that all unipotent groups are connected in characteristic zero.
The group α p , defined in [Wat79] over fields of characteristic p > 0, is unipotent but not F-unipotent.
Let U be an F-unipotent group. Fix a central series U = U 1 > U 2 > · · · > U N +1 = 1, such that each U r /U r+1 is F-isomorphic to G a . The projection U r → U r /U r+1 ∼ = G a splits as an F-morphism of schemes by [Spr98, Theorem 16.2.6]. Fix splitting maps x r : G a → U r . Clearly U is parametrised by N -dimensional affine space: Multiplication and inversion in U (E) are given by polynomials. To be precise where all products are written in ascending order, each F r is a polynomial in 2N indeterminates, and each G r is a polynomial in N indeterminates. The F r and G r are called Hall polynomials [Hal69]. These polynomials have coefficients in F, but tend to be very large and unwieldy. In order to do practical computations in U , we need a more concise description.
We now construct a presentation for the rational point group U (E). Since the series for a, b ∈ E and 1 ≤ r < s ≤ N . Hence we have relations x t (g rt (a)), (4) where f rt , g rt , and h rst are polynomials defined over F. We note that many of these relations are redundant (including (4) for all r), but the extra relations are useful for computation.
Theorem 2.2. Let U be an F-unipotent group and let E be a commutative Falgebra. LetŨ (E) be the group with generators x r (a), for a ∈ E, r = 1, . . . , N , and relations (3), (4), and (5), for a, b ∈ E, 1 ≤ r < s ≤ N . Then the natural map U (E) → U (E) is an isomorphism of abstract groups.
Proof. Since the given relations hold in U (E), the map is well defined. The map is onto because U (E) is generated by the images of the generators ofŨ (E). Every element ofŨ (E) is a word with terms of the form x r (a) or x r (a) −1 . This word can be collected into a product N r=1 x r (a r ). This is achieved by first eliminating all inverses using (4), then putting the terms in order by the subscripts using (5) and removing multiple terms with the same subscript using (3). If the words N r=1 x r (a r ) and N r=1 x r (b r ) are equal in U (E), then a r = b r for all r, and so these words are also equal inŨ (E). Hence the map is injective and we are done.
We say that the group scheme U is presented byŨ . Now suppose we are given an arbitrary system of F-polynomials f rt (a, b) and g rt (a, b), for 1 ≤ r < t ≤ N ; and h rst (a), for 1 ≤ r < s < t ≤ N . Define the group functorŨ by takingŨ (E) to be the abstract group given by generators x r (a), for a ∈ E, r = 1, . . . , N , and relations (3), (4), and (5). We callŨ an FC group functor over F. FC stands for field-commutator, since the relations involve field operations and commutators, just as the PC presentation of a nilpotent group involves powers and commutators. We callŨ consistent if the map is injective for every commutative F-algebra E. Theorem 2.2 implies that every F-unipotent group is presented by a consistent FC group functor. We now prove the converse: Theorem 2.3. Every consistent FC group functor defined over F is an F-unipotent group.
Proof. LetŨ be the consistent FC group functor. Ignoring the multiplication, we can considerŨ to be the N -dimensional affine scheme. Using collection, as in the proof of Theorem 2.2, we can find polynomials F r and G r such that equations (1) and (2) are satisfied inŨ (E). SoŨ is an F-algebraic group scheme, since F r and G r are clearly defined over F. Finally define algebraic subgroups U r = N k=r im(x r ). These give a normal series for U in which every quotient is isomorphic to G a , and soŨ is an F-unipotent group.
Let U be an F-unipotent group. Suppose the projection U r → G a splits as a homomorphism of F-group schemes, not just as a morphism of F-schemes. Then we can take x r : G a → U r to be a homomorphism, and so replace (3) and (4) by It follows immediately that and so all the polynomials f rt and g rt are zero. If x r is a homomorphism for r = 1, . . . , N , we call the corresponding FC group functor split.
Theorem 2.4. If F is a field of characteristic zero, then every unipotent group defined over F is presented by a split FC group functor over F.
Proof. Since F has characteristic zero, every unipotent group U defined over F is F-unipotent by Proposition 2.1. By induction, we can assume that U/U N is presented by a split FC group functor. Fix maps y r : G a → U/U N , for r = 1, . . . , N − 1, defining this functor. By [Ser88, Proposition VII.8], Ext(G a , G a ) = 0. Hence Ext(U/U N , G a ) = 0, by repeated application of the long exact sequence for Hom(•, G a ). So there exists a homomorphism y : U/U N → U splitting the projection U → U/U N . Define x r = y • y r for r = 1, . . . , N − 1. Take x N to be the F-injection G a ∼ = U N → U . These maps clearly define a split FC group functor presenting U .
If F has positive characteristic, then the Witt-vector groups [Ser88] provide examples of F-unipotent groups which cannot be presented by split FC group functors. The full unipotent subgroup of a split reductive group is always presented by a split FC group functor, as we show in Proposition 4.1 below.

Collection and symbolic collection
We now extend some of the standard collection strategies for PC groups to FC group functors. The precise order in which the relations are applied has a huge impact on the speed of collection. Many strategies have been suggested, and we have not attempted to extend them all to FC group functors. We have implemented two fundamental techniques: collection from the left [LGS90,VL90]; and a slightly improved version of collection to the left [HJ76] (we collect the rightmost rather than the leftmost occurrence of the least uncollected letter).
Let U be an FC group functor over F, and let E be a commutative F-algebra. The algorithms in this section operate on a word w ∈ U (E). This word is always equal to M i=1 x ri (a i ) εi , ie, the parameters M ∈ N, a i ∈ E, ε i = ±1, and r i ∈ {1, . . . , N } are automatically modified when w is. Algorithm 1 describes the basic step of collection. When we say "apply a certain relation to a subword", we mean match the subword with the left hand side of the relation, and replace it by the right hand side. CollectSubword looks at the term at position j in the word w, and either removes an inverse (if ε j = −1) or ensures that r j−1 < r j . In addition to the modified word w, it returns indices j 1 and j 2 . Collection to the left (Algorithm 2) apply (4) to the subword x rj (a j ) −1 j 1 := j, j 2 := j else if j > 1 and r j−1 = r j then apply (3) to the subword x rj (a j−1 )x rj (a j ) j 1 := j − 1, j 2 := j 1 + #{t : f rjt (a j−1 , a j ) = 0} else if j > 1 and r j−1 > r j then apply (5) to the subword x rj−1 (a j−1 )x rj (a j ) j 1 := j − 1 if j 1 > 1 and r j1−1 < r j1 then j 2 := j 1 else j 2 := j 1 + 1 + #{t : h rjrj−1t (a j−1 , a j ) = 0} end if else j 1 := j, j 2 := j 1 + 1 end if return w, j 1 , j 2 Algorithm 1: Collect subword works by collecting all terms x 1 (a), followed by all terms x 2 (a), and so on. This uses the index j 1 , which gives the new largest j such that r j = r. Collection from Input: An FC group functor U and a word w = M i=1 x ri (a i ) εi . Output: A product N r=1 x r (b r ) that is equal to w as an element of U (E). for r := 1 to N do let j be the largest i such that r i = r while j ≥ r do w, j 1 , j 2 := CollectSubword(U, w, j), j := j 1 end while end for return w Algorithm 2: Collection to the left the left (Algorithm 3) goes through the word from left to right, correcting each term that is out of position. This uses the index j 2 , which gives the next term which is potentially out of position.
Symbolic collection is a standard method for improving the efficiency of element multiplication in a PC group. This depends on the observation that we can collect a generic product, and then substitute into polynomials for subsequent collections. This is particularly easy in the case of FC group functors: simply take where c rs is a polynomial in b and a r+1 , . . . , a N . Now, taking arbitrary E again, we can multiply two collected words values from E into the (N −1)N/2 polynomials c rs in the obvious manner. A similar method can be used to compute inverses.
The advantage of symbolic collection is that each operation is faster. The disadvantage is that more preprocessing time and memory are required. In order to save memory, we represent our polynomials as straight-line programs (see [LG01] for a description of straight-line programs for group elements; the implementation for polynomials is due to Allan Steel). This means that the polynomials are basically just the collection preserved in amber, so the collection method used is still important. We note that there is another common symbolic collection algorithm, called Deep Thought [LGS98,Mer97], but we have not implemented it for unipotent groups.

Collection in the full unipotent subgroup
We now describe a new collection strategy for the full unipotent subgroup of a reductive group. Let G be an F-split reductive algebraic group [Spr98]. Fix a split maximal torus T in G, and a Borel subgroup B containing T . Let U be the unipotent radical of B. Since U is unique up to G-conjugacy, we refer to U as the full unipotent subgroup of G. Let Φ be the root system of G with respect to T , and let Φ + ⊆ Φ be the positive roots with respect to B.
Write Φ + = {α 1 , α 2 , . . . , α N } with the roots in an order compatible with height, ie, ht(α r ) < ht(α s ) implies r < s. For each α ∈ Φ + , there is a subgroup X α of U isomorphic to G a . Write x r for the isomorphism G a → X αr . Then U r = N s=r X αs , for r = 1, . . . , N + 1, defines a central series for U . The corresponding FC group functor has relations (6) and where the constants C ijαr αs are defined as in [Car72]. Recall that these constants depend on the combinatorics of Φ, and on the choice of a sign for each nonsimple positive root. In [CMT04], a method for computing these constants is given which is efficient for small rank groups. For large ranks, we outline a new method in Section 5. We now have: Proposition 4.1. The full unipotent subgroup of a split reductive group is presented by a split FC group functor.
Note that most of the polynomials h rst from (5) of Section 2 are zero in this case. This gives us much greater flexibility in how we collect words. The ordering of the roots is of vital importance in this section. We specify an ordering in terms of subscripts: α 1 , . . . , α N . The subscripts on the injections x r : G a → U are always kept in agreement with the root ordering under discussion.
Words in U need not be collected into an order compatible with height. In fact, the algorithms of the previous section work for all orderings α 1 , α 2 , . . . , α N of Φ + with the property that α r + α s = α t implies t > r and t > s. We call such an ordering left-additive.
An ordering α 1 , α 2 , . . . , α N of Φ + is called additive if α r + α s = α t implies t lies between r and s (ie, r < t < s or s < t < r). Additive orderings reflect more of the combinatorial structure of the root system than left-additive orderings do. The existence and construction of additive orderings is considered in [Pap94] (see Section 6 below for more details).
In order to collect a word into the additive ordering, we replace relation (9) with which can be proved by applying (9) to x r (a)x s (−b). We then use collection from the outside (Algorithm 4), which is a modified version of collection from the left. The basic idea is to run collection from both sides simultaneously, until we meet in the middle. The two collections could easily be run in parallel, but we alternate between them. The subroutine CollectSubword from Algorithm 3 is slightly modified for both collections (CollectSubwordL and CollectSubwordR). The returned value L is the increase in the word length and k is the index of the next term potentially out of position.
Finally we note that symbolic collection works with collection from the outside, with the obvious minor modifications.

The full unipotent subgroup of a classical group
In this section, we present an alternative to collection which is much more efficient when G has large semisimple rank. We derive formulas for the defining polynomials of the full unipotent subgroup U of a split classical group G. This allows us to write code that implicitly applies the defining polynomials of U without having to store them explicitly in memory. We do not consider exceptional groups here, because their semisimple rank is at most 8.
The rough outline of our method is as follows: We index the roots by pairs of integers. We then construct a minimal degree matrix representation of G. We take the basis for the representation consisting of weight vectors, ordered according to the dominance ordering on the corresponding weights [Hum78]. We then order the roots by going down each column of this matrix representation, and seeing where the parameters corresponding to each root appear. We call this the representation apply (7) to the subword x rj (a j ) −1 k := j, L := 0 else if j < M and r j = r j+1 then apply (6) to the subword x rj (a j )x rj (a j+1 ) k := j, L := −1 else if j < M and r j > r j+1 then apply (10) to the subword x rj (a j )x rj+1 (a j+1 ) L := #{t : α t = kα rj+1 + lα rj for k, l > 0}, k := j + 1 + L else k := j − 1, L := 0 end if return w, k, L Input: An FC group functor U and a word w = M i=1 x ri (a i ) εi . Output: A product m r=1 x r (b r ) that is equal to the input as an element of U (E).
Algorithm 4: Collection from the outside ordering. Note that the representation ordering is also an additive ordering, except in Cartan type C ℓ , where it gives an additive ordering on the coroots.
The representation of roots by pairs of integers can also be used to compute the constants C ijαr βr . For large classical groups, this is much more efficient than the method given in [CMT04]. We omit the details since this is a technical but straightforward application of formulas in [Car72].
We consider each classical type in Subsections 5.1 to 5.4. In each subsection, we fix a particular isogeny type and particular extraspecial signs [Spr98]. The choice of isogeny class is irrelevant, since the structure of the unipotent subgroup is independent of isogeny. We can easily transform between different choices of extraspecial signs using Theorem 29 of [Ste68]. 5.1. Cartan type A ℓ : Linear of degree ℓ + 1. Let G = SL l+1 and let U be the algebraic subgroup of all lower unitriangular matrices. The root system of G has Cartan type A ℓ . Let V = R ℓ+1 with basis e 1 , . . . , e ℓ+1 . Then the roots are Define the map x ij : G a → G by x ij (a) = I + aE ji . The representation order on the roots is simply the lexicographic order on the corresponding pairs of integers. We label the coordinates of A (ℓ+1)ℓ/2 by the root pairs in this order, ie, a ∈ A (ℓ+1)ℓ/2 (E) has the form a = (a 12 , a 13 , . . . , a 1,ℓ+1 , a 23 , . . . , a 2,ℓ+1 , . . . , a ℓ,ℓ+1 ).
We can now define a parametrisation ϕ : The formulas for inversion are defined recursively and are computed in reverse representation order. We note that it is easy to derive a direct formula for d ij , but the recursive version can be evaluated with fewer operations. We assume, for this subsection only, that F has odd characteristic. Since the group of type B ℓ is isomorphic to the group of type C ℓ in characteristic 2, this restriction is not critical. Let G = SO 2ℓ+1 be the special orthogonal group of the orthogonal form with matrix  Let U be the group of all lower unitriangular matrices in G. Define the root maps by Let J i be the sequence of integers [i + 1, i + 2, . . . , ℓ, 0, −ℓ, . . . , −(i + 2), −(i + 1)]. Let The representation order on the positive roots is the lexicographic order on pairs, with the integers ordered as in J 0 . Label the coordinates of A ℓ 2 by the root pairs in this order. Now define a parametrisation ϕ : All of these equations are recursive and are computed in reverse representation order.
5.3. Cartan type C: Symplectic. Let G = Sp 2ℓ be the symplectic group of the symplectic form with matrix Let U be the group of all lower unitriangular matrices in G. The root system of G has Cartan type C ℓ . Let V = R ℓ with basis e 1 , . . . , e ℓ . The roots are α si,tj = se i − te j , for i, j = 1, . . . , ℓ with i = j, and s, t = ±1. Once again α ij = αī for all i, j = 0, ±1, . . . , ±ℓ. The simple roots are α i,i+1 for i = 1, . . . , ℓ − 1, and α ℓl . A root α i,tj is positive if, and only if, i < j.
The representation order on the positive roots is the lexicographic order on pairs, with the integers ordered as in J ′ 0 . Label the coordinates of A ℓ 2 by the root pairs in this order. Now define a parametrisation ϕ : And ϕ(a) −1 = ϕ(d) where 5.4. Cartan type D: Even-degree orthogonal. Let G = SO 2ℓ be the orthogonal group of the orthogonal form with matrix F 2ℓ . Let U be the group of all lower unitriangular matrices in G. The root system of G has Cartan type D ℓ . Let V = R ℓ with basis e 1 , . . . , e ℓ . The roots are α si,tj = se i − te j , for i, j = 1, . . . , ℓ with i = j and s, t = ±1. The simple roots are α i,i+1 , for i = 1, . . . , ℓ − 1, and α n−1,l . A root α i,tj for i, j > 0 is positive if, and only if, i < j. Define the root maps by x ij (a) = I + a(E ji − E 2ℓ−i+1,2ℓ−j+1 ) and x i (a) = I + a(E 2ℓ−j+1,i − E 2ℓ−i+1,j ).
The representation order on the positive roots is the lexicographic order on pairs, with the integers ordered as in J ′ 0 . Label the coordinates of A ℓ(ℓ−1)/2 by the root pairs in this order. Now define a parametrisation ϕ : And ϕ(a) −1 = ϕ(d) where

Analysis and reductive groups
We can now give precise asymptotic timings for operations in reductive groups and their full unipotent subgroups. We give our analysis in terms of the number of basic operations in the algebra E: addition, negation, multiplication, and testing equality. Once again let G be an F-split reductive algebraic group, with split maximal torus T , and Borel subgroup B containing T . Let U be the unipotent radical of B. Let W = N G (T )/T be the Weyl group and let Φ be the root system. The reflection in W corresponding to the root α is denoted s α . Let Φ + be the positive roots with respect to B.
First we give an analysis for element operations in U (E).
Theorem 6.1. Let F be a field and let E be a commutative unital F-algebra. Let U be the full unipotent subgroup of a split reductive linear algebraic group G over F. Let ℓ be the semisimple rank of G. Then there is a normal form for elements of U (E). The word problem for elements in normal form requires O(ℓ 2 ) algebra operations, and multiplying or inverting them requires O(ℓ 3 ) algebra operations.
Proof. The normal form is a collected word, so the timing for the word problem follows from the fact that N = |Φ + | is O(ℓ 2 ). We can assume that G is simple, since U is a direct sum of the full unipotent subgroups of the simple components of G.
If G is classical, the formulas of Section 5 require O(ℓ 3 ) field operations. If G is exceptional, then ℓ is bounded. In this case we use symbolic collection. The Hall polynomials of the full unipotent subgroup of a split reductive group are independent of the algebra E, since split reductive groups can be constructed as Z-schemes. So the number of algebra operations required for inversion or multiplication is independent of the choice of E.
In the rest of this section, we take E to be an extension field of F and we add inversion to the list of basic operations in E. We are primarily interested in computing in U (E) because it allows us to compute in G(E) with the algorithms of [CMT04, Section 5]. Recall that G(E) has a Steinberg presentation with generators x α (a), for α ∈ Φ and a ∈ E; n α , for α ∈ Φ; and t ∈ T (E). Note that the generator x r (a) of Section 4 can be identified with the generator x αr (a) of the Steinberg presentation. Every element g ∈ G(E) can be written uniquely in Bruhat form:
Given two elements in Bruhat form, we need to find the Bruhat form of their product. The usual element operations in U (E) are not sufficient for this purpose. There are two difficult steps, each of which requires a new operation in U . We now describe these operations and show how to carry them out with the methods of the previous sections.
6.1. Single-term separation. One difficult step is multiplying g = utẇu ′ by n α for some α ∈ Φ. This is achieved with Algorithm 3 of [CMT04], which uses the following operation: . We call this operation single-term separation. This is easily done by collection: simply collect the term x α (a α ) to the front of the product as in collection to the left, then put v in the required form with collection from the outside. No extra terms of the form x α (b) can appear in v because only terms corresponding to roots higher than α are created. We can also do single term separation symbolically as in Section 3.
Alternatively, for classical groups, we can compute v as the product x α (−a α )u ′ using the formulas of Section 5. If α = α ij , then the only possible nonzero constants in ϕ(a) are a ij , a ′ ij , and a ′′ i . Hence at most O(ℓ) of the formulas for c ij are nontrivial. Each such formula has at most a constant number of nonzero terms. We now have: Proof. Use formulas for classical components and symbolic collection for exceptional components.
Note that, when both of the elements being multiplied are in Bruhat form, Algorithm 3 of [CMT04] only uses single-term separation for α simple. We have considered nonsimple roots as well, because they will be useful in the next subsection.
6.2. Weyl separation. The other difficult step for multiplication in G is computing the product of g ∈ G and v ∈ U . Write g in Bruhat form utẇu ′ . Then multiply u ′ and v, and decompose the product into the form We call this operation Weyl separation. We now get the Bruhat form If we take the elements of Φ + \ Φ w in an order compatible with height, followed by the elements of Φ w in an order compatible with height, we get a left-additive ordering on Φ + . So the algorithms of Section 3 can also be used for separation. But note that (v ′′ )ẇ −1 t −1 will need to be collected again, since the image of the left additive ordering on Φ + \ Φ w under w −1 need not be left additive.
We can also use collection from the outside for Weyl separation. We need the following classification of additive orderings from [Pap94]: Theorem 6.3. Let w be an element of the Weyl group W . Let s β1 · · · s βm be a reduced expression for w. Then β 1 s β2 · · · s βN , . . . , β N −2 s βN−1 s βN , β N −1 s βN , β N is an additive ordering on Φ w . All additive orderings on Φ w arise from reduced expressions in this manner. Now let w 0 be the longest word in W and fix a reduced expression s α1 · · · s αN for w 0 (in practice, we use the lexicographically least reduced expression, but this is not necessary). We use the additive ordering on Φ + corresponding to this reduced expression as the fixed order for collection. Now let w be a Weyl group element. If we restrict the fixed ordering to Φ w we get an additive ordering, with corresponding reduced expression s β1 . . . s βm = w. Similarly we restrict to get an ordering on Φ w0w −1 = (Φ + \ Φ w )w −1 and a corresponding reduced expression s γ1 . . . s γN−m = w 0 w −1 . Now w 0 = s γ1 . . . s γN−m s β1 . . . s βm is reduced. The corresponding ordering is: our fixed ordering restricted to Φ + \ Φ w and transformed by w, followed by our fixed ordering restricted to Φ w . This is precisely the ordering we need for separation.
Finally we analyse Weyl separation: Proposition 6.4. Weyl separation in U requires O(ℓ 3 ) field operations.
Proof. For classical components, we apply single-term separation for each root in Φ w . By Proposition 6.2, this takes O(N ℓ) = O(ℓ 3 ) operations. For exceptional components use symbolic collection.
In the exceptional case, this proposition assumes we have a system of symboliccollection polynomials for every Weyl element. Although this is polynomial time, the memory required to store all these polynomials is prohibitive. In practice, it is much faster to use collection from the outside for Weyl separation in exceptional groups.
6.3. Operations in reductive groups. We now prove the following result on computation in G: Theorem 6.5. Let F be a field and let E be an extension of F. Let G be a split reductive linear algebraic group over the field F. Let ℓ be the semisimple rank of G and let n be the reductive rank. Then there is a normal form for elements of G(E).
The word problem for elements in normal form requires O(n + ℓ 2 ) field operations, and multiplying or inverting them requires O(nℓ 2 ) field operations.
Proof. We use the Bruhat decomposition to store g ∈ G in the normal form g = uhẇu ′ . Here u, u ′ , andẇ are words of length at most N , while h has length n. Once again the timing for the word problem is clear. Now G is a central product of simple algebraic groups and a central torus of dimension at most n.

Implementation and timings
A number of heuristic improvements are built into our implementations of the algorithms described. Most of them are either obvious or were suggested by our profiling of the code. We restrict ourselves here to a brief description of the basic data types used. Representations of elements of the field F or algebra E are taken care of by the Magma computer algebra system [BCP97]. Most of our code is written in traditional C [KR88] and incorporated into the Magma core. Less timecritical code is written in the Magma language itself.
A collected product N r=1 x r (a r ) is stored as a sequence [a 1 , . . . , a N ]. While doing the collection, we represent a term x r (a) as a pair (r, a) of an integer and an element of E. Note that pairs (r, 0) are trivial -they are always eliminated as soon as they occur. A word M i=1 x ri (a i ) εi is represented as a doubly linked chain. That is, every root element in the chain contains a reference to its predecessor and successor, which is a null-reference if the element is the first (resp. last) in the chain: ← • ⇆ • ⇆ · · · ⇆ • → We use this data structure because inserting and deleting terms in the word when applying relations (3)-(5) can be done in constant time. For sequences, insertion and deletion would be more expensive, since the tail of the sequence has to be copied in memory. The chain is doubly linked, since we need both the predecessor and the successor of a term in the word for the CollectSubword functions.
In our tables we use the following abbreviations for collection algorithms: CTL: Collection to the left, Section 3. CFL: Collection from the left, Section 3. CFO: Collection from the outside, Section 4. SCFL: Symbolic collection from the left, Section 3. SCFO: Symbolic collection from the outside, Section 4.
We have two different implementations of the method of Section 5: D: Modified matrix multiplication. For given a, b, we use formulas of Section 5 to compute ϕ(a) and the significant part of ϕ(b) (we do not use b ′ ij and, except in types B (even characteristic) and C, we do not use b ′′ i ). Then the product of the two matrices is computed using algorithms implemented in the Magma computer algebra system [BCP97]. The resulting matrix agrees with ϕ(c) in the entries c ij and in the entries c ′′ i (where they are needed). Thus we can recover the product c = ab from the resulting matrix by formulas of Section 5. SD: Compute the polynomials of (8) in Section 3, using the formulas instead of collection.
Method D outperforms SD in most cases, since asymptotically fast algorithms are used for matrix multiplication. But SD is faster for fields with very rapid blow-up of terms, such as multivariate rational function fields. All timings were run on an AMD Opteron 150 Processor with 2393 MHz. Table 1 gives times and memory consumption for creating the reductive groups and precomputing all constants. For symbolic algorithms, this also includes time taken to compute the polynomials. Note that all constants and polynomials are independent of the field, and are computed on a per-root-datum basis. This means that preprocessing time is nearly zero if a group with the same root datum has already been created in the same Magma session. We used a workspace of 4 gigabytes -when this is insufficient we do not give a time and write > 4GB in the memory column. In columns D and SD, the constants are computed as they are needed and not stored in memory. Table 2 gives average times for multiplying and inverting random elements of full unipotent groups over the field with 17 elements. The average is taken over 100 multiplications. The same random elements are used for different algorithms. If a single multiplication required more than 2 gigabytes of memory, we write > 2GB instead of a time. We did not attempt those cases where the preprocessing took more than 4 gigabytes of memory. Table 3 gives similar times for multiplying and inverting random elements of the reductive group itself. Each such operation involves a number of collections. Computing random elements in a reductive group can be time consuming, but this is not included in our timings. Table 4 gives average times for multiplying and inverting random elements of full unipotent groups of reductive groups over different fields. Over the field of rational numbers, the random field elements are chosen by taking a random numerator and a random denominator of size up to the given number of bits and a random sign.     Table 5. Total degrees of Hall polynomials Similar random elements were used for the Gaussian integers Q(i) and for Q(p), which is the splitting field of a random irreducible polynomial of degree 6 with integral coefficients in the range 1 to 10. The field R is the multivariate rational function field over Q with 10 variables. Random field elements over R were taken to be random invariates. In B 20 (R) the coefficient blowup is so large that over 2 gigabytes of memory was needed in some cases (see entries in the table). Finally, in Table 5, we compare the total degrees of the polynomials used for different kinds of symbolic collection. The last column contains lim ℓ→∞ avg{deg(p) : p ∈ P}, where P is the set of polynomials used for symbolic collection. This goes a long way towards explaining why collection from the outside works so well. Since the polynomials are multivariate in 2N = 2|Φ + | variables, we still can have large polynomials. To have a very rough idea of the size, we printed the largest of the polynomials in type B 15 as a string and measured its size in bytes. Using collection from the outside, the size is 9226 bytes; using collection from the left, the size is about 297 megabytes.