This type of transformation is often required, and this chapter discusses this issue. The types of transformations required will be discussed, along with possible implementation schemes.
The first, basic type of expression one would like to be able to match is an expression like ...*a^n*...*a^m*..., which in its most general form discovers that an expression only contains multiplications, and that it contains a factor a^n and a factor a^m. We would like this expression to be changed into ...*a^(n+m)*....
Another example is simplification using trigonometric identities, where a term containing two trigonometric factors is reduced to two terms with each one trigonometric factor. Identities like
are easy to write down in one line. Ideally, Yacas would allow a programmer to write this down in one line and then have a global pattern matcher recognize when this pattern is applicable, and apply the transformation rule.
Other examples include:
and for a given integer k:
These are all patterns that could be found within one term containing only factors.
In this case, it is possible to write this expression as:
which in turn can be simplified further, by setting
yielding
and thus y= -1 , Exp(x/2)= -1 after factoring. It then follows that the solution is x=I*2*Pi:
In> Solve((Exp(x/2)+1)^2==0,x) Out> Complex(0,2*Pi); In> f(x):=N(Exp(x)+2*Exp(x/2)+1) Out> True; In> f(Complex(0,2*Pi)) Out> 0; |
For instance, for trigonometric identities, there is sometimes an exact result if the argument is a rational number times Pi. One would like to be able to recognize Pi/2 , 1/2*Pi , Pi*1/2 , 4*Pi*1/8, and perhaps even 0.5*Pi as being half Pi.
With integration, there is often an antiderivative for an expression if an argument can be written as a*x+b where x is the variable being integrated over, and a and b are constants that do not depend on x.
Furthermore, in keeping with the rest of the design of the language, it should be possible to write only a few lines of code in order to specify patterns to be matched and transformations to be performed.
...*a^n*...*a^m*... .
One solution is to do it in scripts. One needs to gather all the factors. The first option is to write a custom bit of code for this type of transformation, where all factors are gathered in a list, combining the symbol with its exponent. While traversing the expression, one adds items to this list.
For instance for an expression a*b^2*c*d*a one would first add (a,1), then (b,2), (c,1) and (d,1). Lastly, for the last factor, a, the system could notice that it was already in the list, and just update this item to (a,2). One would end up with the set ((a,2),(b,2),(c,1),(d,1)). This could be called an internal representation.
After this process finishes, one can traverse this list, producing the required result a^2*b^2*c*d.
This process can be generalized. The steps involved are:
The above scheme is flexible, in that the specific method of adding a sub-expression to the already existing database can be customized for different types of simplification or pattern matching. transformations could even be done in-place. The specific algorithm for adding a term to the database then acts as a filter.
The difficult part is to choose the form of the database, as that ultimately defines the types of transformations and simplifications that are possible.
When only transformations within one term are needed, the situation is not too difficult.
$$ (a[1][1] * ... *a[1][n1]) / (b[1][1] * ... * b[1][m1]) + ... + (a[p][1] * ... *a[p][np]) / (b[p][1] * ... * b[p][mp]) $$
Eg. one could write an expression as a set of terms, where each term is a rational function, consisting of a numerator and denominator, each with just simple factors. One could then process each term, and maintain a database for each term. Thus one could readily simplify a^n/a^m to a^(n-m), or (n+1)! /n! to n+1. The trigonometric simplification scheme described earlier in this chapter would be more sophisticated, as it would require changing one term to two (as a multiplication within a term is changed into an addition of two terms).
For instance, the database might already have an entry representing a^n. When a new term a^m is encountered, one would want to combine these two into a^(n+m). This is easy to do with custom code that can directly access the database internal representation.
At the same time, one would ideally want to specify this transformation using notation similar to
In stead of writing custom hand-written code for this transformation, one would want a system were the a^n part is matched in the database and the a^m part in the expression being processed. The result, a^(n+m), would be the result, and one would want the system to remove the a^n from the database and put back a^(n+m).
Actually, for efficiency reasons, one would want the system to change a^n to a^(n+m) in the database. But this is a very specific example where this is easily possible. For transformation rules like
one needs a database for a rational function, and one needs to remove one factor and replace it with many other factors.
In the case of the trigonometric identities, one needs to replace something of the form A*B to something of the form C+D, which requires actually removing the actual term at hand (and not just one factor) and replace it with two terms.
One option is to have the a^n*a^m=a^(n+m) simplification be performed automatically, then convert the entire expression into internal representation with one additional facility in the internal representation that one additional collection is made; one can collect factors or terms that one knows will be relevant for the simplification. when simplifying factorials, one can collect all factorials in a special part of the internal representation so they are all grouped together. The algorithm can then proceed to process only these parts. For instance,
could be converted to
So that the left side part can be further simplified, resulting in
This can be a problem when the expression is brought into the form described above, as this normalization step would first convert (a+b)/c to a/c+b/c. This breaks up the expression. If a+b and c had common factors, this is now lost.
Thus the rational expression first needs to be scanned for greatest common divisors before being split up.
The problem of finding greatest common divisors is a little bit more complicated than described here. For instance the following expression
is actually equivalent to
This can only be discovered if the first and the last term are combined into one, leaving out the middle term. Perhaps the fact that the two denominators have a greatest common divisor not equal to one can be used to find terms that can be combined.
Another option is to not split up rational terms when there is an addition involved in the denominator, as little is expected to be gained from the simplification any way after removing greatest common divisors. In stead, the numerator and denominator could be simplified as sub-expressions in their own simplification step.
This scheme might not be the most suitable solution when matching patterns for use in other algorithms. In such cases one is generally interested in whether an expression can possibly be brought into a specific form, which does not necessarily match the form the simplifier brings the expression in.
Suppose we want to find out if an expression matches the form a*x+b where both a and b don't depend on x. Further more, the algorithm is likely to need the actual values for a and b.
If the algorithm for simplification described earlier were used, one would end up with a list of terms, each with lists of factors in the intermediate format. The information that is needed would be missing. For example:
would have to be written down as
before one can recognize that a*x+b fits, and find the exact forms for a and b.
In a sense the method for arriving at this stage is almost the same: first gather information, and then return the information in the requested form. The problem is that this feature, global pattern matching, requires more flexibility.
The fact that the algorithms and internal representation of the simplification scheme described above are not suited for this task can be seen from the following example; suppose we wanted to match a*x+b to the expression
One would want this expression written out as
so that the constants can readily be identified. However, as discussed in the section on rational terms, for simplification it is not wise to split up such rational terms. It is required for this example, however. The filtering step could be made more sophisticated so that this operation can be dealt with.
A more serious concern is with efficiency. Apart from splitting up the expression in too small chunks (one only needs a and b, and thus would only need to gather these), there is another danger: the conversion to internal representation continues until the full expression is processed.
In practice, while the expression is being processed, if custom code were written, the matcher could decide while matching, that the pattern will never fit, and terminate immediately. For example, a and b should be independent of x, so if a factor like Sin(x) is encountered the matching can stop immediately.
If the scheme described in the section dealing with simplification is to be used for general pattern matching also, another step needs to be added to it; the filter operation should be able to terminate the process when it decides early on that code further upstream will fail any way.
In this case, if Sin(b*a) were first converted to Sin(a*b), the system could readily collect terms and discover that the terms described above cancel each other out and result in zero.
For this, the system needs to impose an order for factors. For this, LessThan can be used. LessThan defines an ordering for atoms:
In> LessThan(a,b) Out> True; In> LessThan(b,a) Out> False; In> LessThan(2,a) Out> True; In> LessThan(2,1) Out> False; In> LessThan(a,"b") Out> False; |
Ordering for composed expressions can be created based on the LessThan function.
does not hold. This has consequences for a system that is trying to simplify the expression passed in. When gathering information to be stored in the database, what the operation is in fact doing is moving factors around until they are next to each other and can be combined. For instance,
would first be re-ordered to
which then readily converts to
Extending this system to also support non-commuting algebra involves disallowing these swaps. For groups of symbols, one could specify that two symbols do not commute. For the above example, supposing A and B do not commute, the resulting expression could then terminate as:
One step further would be to support commutation relations. Suppose that after one established that A and B do not commute, that the following relation holds:
Then the part of the expression B*A could be converted to A*B-C. This could then result in the expression:
Which then can be written as:
Factoring could then yield:
A potential risk is with the global transformation rules, which do not necessarily adhere to the rules for non-commuting algebras. A special non-commuting multiplication operator could be defined for this to guarantee that this is never a problem.