Differences

This shows you the differences between two versions of the page.

Link to this comparison view

documentation:guide:standard_form_of_mathematical_expressions [2015/11/21 12:33]
documentation:guide:standard_form_of_mathematical_expressions [2015/11/21 12:33] (current)
Line 1: Line 1:
 +====== Standard form of mathematical expressions ======
 +<​html>​
 +<div class="​text-right"​ style="​font-size:​ 15px; ">
 +</​html>​
 +Next topic: [[documentation:​guide:​symmetries_of_tensors]]
 +<​html>​
 +<span class="​glyphicon glyphicon-arrow-right"></​span>​
 +</​div>​
 +</​html>​
 +
 +----
 +A core feature of any CAS is its ability to reduce arbitrary expression to some 
 +standard form (**SF**) in which it is then used everywhere in manipulations. This 
 +approach facilitates comparison and matching of expressions and gives a way for 
 +more robust and fast algorithms for almost all CAS operations. Redberry uses the 
 +same paradigm: any intermediate and resulting expression is guaranteed to be in the 
 +**SF**.
 +
 +====Standard form of indexless expressions ====
 +
 +
 +The standard form of indexless expressions is same as in the majority of other CASs. Consider the following examples, which give an idea of **SF** in Redberry:
 +<sxh groovy;​gutter:​ false>
 +println '​(a-b)+c+(b-a)'​.t
 +</​sxh>​
 +<sxh plain; gutter: false>
 +   > c
 +</​sxh>​
 +<sxh groovy;​gutter:​ false>
 +println '​c*(a-b)*(b-a)/​c'​.t
 +</​sxh>​
 +<sxh plain; gutter: false>
 +   > -(a-b)**2
 +</​sxh>​
 +<sxh groovy;​gutter:​ false>
 +println '​2/​3-27**(1/​3)/​9'​.t
 +</​sxh>​
 +<sxh plain; gutter: false>
 +   > 1/3
 +</​sxh>​
 +<sxh groovy;​gutter:​ false>
 +println 'Sin[2 + 2.*I]**(1/​4)'​.t
 +</​sxh>​
 +<sxh plain; gutter: false>
 +   > 1.38307 - 0.144188*I
 +</​sxh>​
 +The first example demonstrates that Redberry performs the reduction of similar ​
 +terms. The second --- that same (to within a sign) multipliers are collected into 
 +powers or reduced. Numbers are always collected and reduced if possible. If 
 +expression contains floating-point numbers, then it will be completely reduced ​
 +(calculated). This behaviour is similar to the majority of "​scalar"​ CASs and needs no more detailed explanation.
 +====Standard form of indexed expressions====
 +The additional conventions on standard form arise in expressions that contain ​
 +tensors. The most remarkable convention is on the **SF** of [[documentation:​ref:​Sum]]. It is best to 
 +demonstrate it by example:
 +<sxh groovy; gutter: false>
 +println '​a*F_mn+(a+b)*F_mn'​.t
 +</​sxh>​
 +<sxh plain; gutter: false>
 +   > (2*a+b)*F_{mn}
 +</​sxh>​
 +As one can see, Redberry tries to factor out tensorial and leave “scalar” (with zero sized  [[documentation:​ref:​indices]]) parts of products; this is a general rule used by Redberry for bringing sums into standard form. Consider another example:
 +<sxh groovy; gutter: false>
 +println '​(x_a^a + y_b^b)*X_m*X_n + (z_a^a - y_d^d)*X_m*X_n'​.t
 +</​sxh>​
 +<sxh plain; gutter: false>
 +   > (x_{a}^{a}+z_{a}^{a})*X_{m}*X_{n}
 +</​sxh>​
 +Here Redberry factored tensorial part ''​X_m*X_n''​ since both sums ''​(x_a^a+y_b^b)''​ and ''​(z_n^n-y_d^d)''​ have indices with zero size (because ​ [[documentation:​ref:​indices]] of  [[documentation:​ref:​Sum]] are free indices of its summands):
 +<sxh groovy; gutter: false>
 +println 'x_a^a + y_b^b'​.t.indices.size()
 +</​sxh>​
 +<sxh plain; gutter: false>
 +   > 0
 +</​sxh>​
 +On the other hand, the following tensor will not be further reduced:
 +<sxh groovy; gutter: false>
 +println 'x_a^a * X_m*X_n + y_a^a * X_m*X_n'​.t
 +</​sxh>​
 +<sxh plain; gutter: false>
 +   > x_a^a * X_m*X_n + y_a^a * X_m*X_n
 +</​sxh>​
 +This is because each multiplier of e.g. ''​x_a^a * X_m*X_n''​ (and in particular ''​x_a^a''​) has indices of nonzero size:
 +<sxh groovy; gutter: false>
 +def ind = '​x_a^a'​.t.indices
 +//only free indices has zero size
 +println [ind.size(),​ ind.free.size()]
 +</​sxh>​
 +<sxh plain; gutter: false>
 +   > [2, 0]
 +</​sxh>​
 +
 +Consider the last example:
 +<sxh groovy; gutter: false>
 +println '​(x_a^a + y_b^b)*X_m*X^m + (z_m^m - y_d^d)*X_a*X^a'​.t
 +</​sxh>​
 +<sxh plain; gutter: false>
 +   > (x_{a}^{a}+z_{a}^{a})*X^{m}*X_{m}
 +</​sxh>​
 +Here Redberry factored the same tensorial part (''​X_m*X^m''​ equals to ''​X_a*X^a''​) and collected similar terms in the formed ​ [[documentation:​ref:​Sum]]. One can also see that Redberry automatically relabelled conflicting dummy indices.
 +====The ordering of terms====
 +
 +The important detail is ordering of summands and multipliers within sums and 
 +products. Elements of sums and products are sorted by their 32 bit hash codes. ​
 +Hashes for simple tensors (e.g. ''​x''​ or ''​k_p''​) are generated ​
 +randomly at each Redberry run, while hashes of complicated tensors (e.g. 
 +''​Sin[x]*k_i''​) are calculated ​ according to certain complex ​
 +rules. Actually, hash functions are organised in such a way that they are "​insensitive"​ for particular names of indices but "​sensitive"​ for their contractions. So, renaming of dummy or free indices does not affect hash code, but any modification of structure of contractions (e.g. contraction of two 
 +free indices) does.
 +
 + Usage of the pseudorandom generator allows to obtain nearly ​
 +uniform distribution of hashes of tensors, which significantly improves the 
 +performance. However, the ordering of expressions changes from run to run, and e.g. 
 +product ''​a*b*c''​ will be sorted differently at different runs 
 +(''​b*c*a''​ or ''​b*a*c''​ etc.). Of course, all similar expressions ​
 +will have similar ordering in current session. One can fix 
 +the seed of pseudorandom generator inside, so that expressions will have same 
 +ordering from run to run, by putting the following line in the beginning of the code:
 +<sxh groovy;​gutter:​ false>
 +import cc.redberry.core.context.CC
 +import cc.redberry.groovy.Redberry
 +
 +use(Redberry) {
 +    CC.resetTensorNames(1)
 +
 +    //your code here
 +}
 +</​sxh>​
 +====Internal details====
 +
 +The reduction to **SF** is a light-weight operation which does not perform any time-consuming simplifications. ​
 +
 +In contrast to many other open-source tensorial CASs, Redberry not uses so-called //indices canonicalisation//​ (sorting) approach. It uses another approach for the problem of tensors comparison and simplification,​ which will be discussed in more detail in [[documentation:​guide:​Mappings of indices]].
 +
 +User can rely on the fact that inside any calculation all expressions are reduced to the **SF**. This fairly simplifies implementation of custom transformations and algorithms.