This is a Sample Idea for optimising the mathematical expressions via gist in expression templates.

ExpressionOptimization.md

Optimising an Expression using Strings

This idea assumes that we already have expression templates implemented via Boost.YAP.

Example

Let's assume user writes following snippets of code using our expression template BLAS library :

Tensor a = {{1,1}, {1,1}, {1,1}};
Tensor b = {{2,2}, {2,2}, {2,2}};
Tensor c = {{1,1}, {1,1}, {1,1}}; // Notice this is same as a
Tensor d = {{3,3}, {3,3}, {3,3}};

// Also our overload for == should return true

assert(a == c); // pretty obvious :)

auto expr1 = (a + b) - (c - d); 
// Poor user does not knows that a == c
// Hence this expreession should collapse into b - d;

Now For the above Expression we will get an A.S.T in YAP. We can easily print the A.S.T we got using boost.YAP internal print() function.

The A.S.T generated can be visualised in this case, I am not providing a Flow chart for it at this moment.

Here is what we will follow to optimise this expression during evaluation. We will delay the optimisation of expression as well until expression is requested for evaluation.

Step 1

We will create a std::unordered_map<char, Tensor&>

We now visit every terminal node in the A.S.T using a simple transform of boost.YAP

Every terminal node in the A.S.T contains a reference to some of the tensors in this case to one of a, b, c, d.

In Quadratic time complexity we will fill the above std::unordered_map. The Idea here is that we will assign each unique tensor reference a Latin Character (A, B, C, ....)

After running the above rule we can expect to get the following content in the map.

map['X'] = a;
map['Y'] = b;
map['Z'] = d;
// We skipped c here because only unique variables were required. 
// We skipped it because already a == c is in the map.

The reason for creating the map is so that we can recreate an optimised expression later on with just the char of the map keys.

Step 2

Using the keys we have in the map, We recreate a String representation of the expression tree.

In the above example our string representation will look like :

((X + Y) - (X - Z))

Note how c has been replaced with the key of a because they were same.

The above string representation could be build recursively from the A.S.T just by traversing it via any yap transform.

Okay, Cool So What's next.

Step 3

Now we run some algorithms to optimise the string representation we have got. It will generally follow following order of optimisation :

• Remove Redundant Parenthesis from String.
  • After this operation above expression becomes
    • X + Y - X - Z
  • There is a catch however, We cannot simply remove all the braces out of blue say we have a expression such as (X - (Y - Z)/X). We need to only remove the braces where there is no need of having braces such as A + (B + C) == A + B + C
• Cancel out the terms that could be cancelled.
  • After this operation above expression becomes
    • Y - Z
  • In order to cancel the terms we generally need to split the complete expression into set of non-distinct terms . (Terms are separated by + or -). Such as A*B + B*C - C/D contains 3 terms. We can only cancel those terms which are same but of opposite sign.
• Scalar Operation
  • This operation has no effect on the above expression as there is no scalar addition or subtraction we could do. However as an example Say we have an expression such as A + A + B
    • 3A + B
  • No Brain-er here ;)
• Distributive Law optimization
  • This will be last optimisation we will do in the string. You get the point anyways, it will somehow use some magical algorithm to convert A*B + A*C to A*(B+C)

Step 4

After all the above optimisation have been applied to the string representation. We will get the final optimised string representation. In this case, Y - Z .

We use the map created in the last step to reconstruct a new expression tree corresponding to the above representation. We then evaluate this expression and done.

Pros

• It is fast. In worst case O(n*n), where n is number of terminal nodes in the original A.S.T

• It can be used to optimise very complex expression such as

  • ((((X+Y)/Z) - ((A - B)/C)) - ((((X+Y)/Z) - ((A - B)/C)))) to
  • -2((A-B)/C)

  Yeah, that's amazing.

• It can bring nested optimisations as well such as

  • (((A*B) - (A*C)) + ((C*B) - (C*C))) to
  • (A + C)*(B - C)

  That's even amazing..

Cons

Make a PR and write / add some

• A lot of string optimisation algorithm required.
• Involves creation of intermediate temporary data-structures such as maps in the above case.