4.2. Technical details

Canonicalization:
The canonicalization process has essentially six steps, of which only steps 4 and 5 are really hard. Assume we start from a generic syntactically correct input in xTensor` on which we act with ToCanonical:
    1) Expand the expression to convert it into a sum (Plus) of terms, each being a product (Times) of indexed objects, sharing dummy indices. This can be considered a polynomial in tensor variables, and as with any normal polynomial, it cannot be canonicalized without first expanding it. We use the Mathematica command Expand. It might happen that during the expansion some parts of the expression are evaluated and give new products to expand. That means that Expand must be used repeatedly until the expression does no longer change (we use the Mathematica command FixedPoint for that).
    2) Minimize the number of different dummies in the whole expression. We use the xTensor` command SameDummies.
    3) ToCanonical is threaded on each term. Steps 4 and 5 cannot compare different terms in the expression. From now on we only deal with products of objects.
    4) The objects in each term must be sorted according to certain priorities depending on the types and properties of the objects, but not on the actual indices they have. The term is then considered to be a single tensor, whose properties can be deduced from the properties of the elementary objects composing it. This idea is taken from R. Portugal (put journal ref. here).
    5) We extract the list of indices of that composite tensor and canonicalize that list according to the symmetries of the composite object and comparing with the "ideal" ordering of those indices (given in xTensor` by the function IndexSort). This "ideal" ordering is also decided by a number of priorities depending on the properties of the indices (type, character and state), as explained below. In general, the indices can change slot, but there is no creation of new indices, the exception being the treatment of derivatives which generate new terms. A very important issue at this step is the interaction between metrics and derivatives, discussed below. The problem will be even harder if frames are involved. The canonicalization algorithms for tensors are basically those of R. Portugal et al (put journal refs here).
    6) By now each term is already canonicalized. The function Plus will add up equal terms and the result is returned, in canonical form. No simplification (e.g. factorization) is attempted by ToCanonical.
The priorities for sorting objects in step 4 are fixed, even though they could be easily changed if a user needs it, but the priorities for sorting indices in step 5 can be configured by the user. In this section we shall describe what those priorities are and how some of them affect the efficiency of the whole process.

Sorting objects:
Objects are sorted according to seven considerations, most based in lexicographic ordering (this is also what Mathematica does). Objects are sorted with respect to the first of these criteria applying:
    1) Type: use alphabetical order in the types:
        Constant
        ConstantSymbol
        Parameter
        Scalar (see subsection 8.7 for a description of this head)
        Tensor
         In subexpressions sometimes we need the type of a composite object: the type of a product is the product of types, and the type of a sum is the sum of types. Both Times and Plus sort their arguments lexicographically.
    2) Order (in the sense of number of elements) of the group of symmetry of the objects. More symmetric (higher order) objects come last (to improve efficiency for tensors with lots of indices), though I have found that the opposite choice is aesthetically better in general.
    3) Names of objects. Every object is given a name which depends on the names and the structure of its components, but not on its indices.
    4) Number of indices of objects. Sort first the objects with less indices. This is also more efficient.
    5) Number of free indices (of the whole term) of objects. Sort first the objects with more free indices.
    6) If the global variable $CommuteFreeIndices is False then sort first the object with the least free index according to IndexSort. If it is True (the default) then do not take into account the actual free indices and jump to step 6.
    7) If several objects cannot be sorted according to the previous considerations, then they are considered equivalent (I call them "commuting") and left then marked as CommutingObjects[o1, o2, ...], what will be used by the permutations algorithms to add new symmetries among the indices of those equivalent tensors.

Sorting indices:
These are all possible things we can consider when sorting indices, in no special order.
    - Relative position of free and dummy indices.
    - Relative position of the members of the same dummy pair.
    - Relative position of up and down indices.
    - Alphabetic order of indices.
    - The order that the indices have in IndicesOfManifold (the order at definition time).
The default is the following, chosen "experimentally" as the most efficient, in average (I don't really have an explanation of why this seems to be more efficient than other choices):
    1) free indices come before dummy indices.
    2) sort the indices according to lexicographic order.
    3) up-indices come before down-indices.
Those priorities can be changed. We need three priorities, that must be chosen from four pairs of strings, not choosing two of the same pair: free / dummy, up / down, lexicographic / antilexicographic and positional / antipositional.

IndexSort                Sort a list of indices
SetIndexSortPriorities    Define priorities for index sorting

Functions that sort indices.

In[246]:=

Indices of manifold TangentM3:

In[247]:=

Out[247]=

Study this case, taking into account the default priorities given above:

In[248]:=

Out[248]=

Now we change priorities. The list is sorted differently

In[249]:=

In[250]:=

In[251]:=

Out[251]=

Note that once positional or lexicographic is chosen (or their opposite), then the priority free/dummy becomes irrelevant:

In[252]:=

In[253]:=

Out[253]=

The choice of priorities can make a huge difference in the efficiency of the dummy-canonicalization process. In principle, it is not possible to predict which set of priorities will be better in a given situation, but experimentally we have found that trying to match pairs of dummies with symmetry pairs of S gives better results:

In[254]:=

Out[254]=

Having one of up/down before free/up seems terrible in the Dummy algorithm:

In[255]:=

In[256]:=

Out[256]=

This is the default choice, instead. Note that the final result is different. This is not a problem: what we want is a uniquely defined process of canonicalization, but which one we choose is "only" a matter of efficiency and aesthetics.

In[257]:=

In[258]:=

Out[258]=

Created by Mathematica  (May 16, 2008)