Cadabra
a field theory motivated approach to computer algebra

Applying operations until convergence

It often happens that you want to perform a series of operations on an expression, until the expression no longer changes. If it is just a single operation, you can use the repeat=True parameter to the algorithm. Let us have a look at a simple example:
ex:=Q Q Q Q Q Q; substitute(ex, $Q->A+B, A->3, B->5$);
\(\displaystyle{}Q Q Q Q Q Q\)
\(\displaystyle{}\left(A% +B\right) \left(A% +B\right) \left(A% +B\right) \left(A% +B\right) \left(A% +B\right) \left(A% +B\right)\)
Here the A->3 and B->5 bits of the substitution rule did not get applied because substitute only ran once. By adding the repeat=True flag you get the expected result:
ex:=Q Q Q Q Q Q; substitute(ex, $Q->A+B, A->3, B->5$, repeat=True);
\(\displaystyle{}Q Q Q Q Q Q\)
\(\displaystyle{}262144\)
However, this only works if you have a single algorithm to work with. If you want to apply a series of algorithms, you need to use the Cadabra specific converge construction (which is an extension of Python). It works very similar to a while loop, and will run until the indicated expression no longer changes. Here is an example:
ex:=Q Q Q Q Q Q; converge(ex): substitute(_, $Q->A+B, A B->3$, repeat=True); distribute(_);
\(\displaystyle{}Q Q Q Q Q Q\)
\(\displaystyle{}\left(A% +B\right) \left(A% +B\right) \left(A% +B\right) \left(A% +B\right) \left(A% +B\right) \left(A% +B\right)\)
\(\displaystyle{}A A A A A A% +A A A A A B% +A A A A B A% +A A A A B B% +A A A B A A% +A A A B A B% +A A A B B A% +A A A B B B% +A A B A A A% +A A B A A B% +A A B A B A% +A A B A B B% +A A B B A A% +A A B B A B% +A A B B B A% +A A B B B B% +A B A A A A% +A B A A A B% +A B A A B A% +A B A A B B% +A B A B A A% +A B A B A B% +A B A B B A% +A B A B B B% +A B B A A A% +A B B A A B% +A B B A B A% +A B B A B B% +A B B B A A% +A B B B A B% +A B B B B A% +A B B B B B% +B A A A A A% +B A A A A B% +B A A A B A% +B A A A B B% +B A A B A A% +B A A B A B% +B A A B B A% +B A A B B B% +B A B A A A% +B A B A A B% +B A B A B A% +B A B A B B% +B A B B A A% +B A B B A B% +B A B B B A% +B A B B B B% +B B A A A A% +B B A A A B% +B B A A B A% +B B A A B B% +B B A B A A% +B B A B A B% +B B A B B A% +B B A B B B% +B B B A A A% +B B B A A B% +B B B A B A% +B B B A B B% +B B B B A A% +B B B B A B% +B B B B B A% +B B B B B B\)
\(\displaystyle{}A A A A A A% +18A A A A% +135A A% +540% +135B B% +18B B B B% +B B B B B B\)
\(\displaystyle{}A A A A A A% +18A A A A% +135A A% +540% +135B B% +18B B B B% +B B B B B B\)
\(\displaystyle{}A A A A A A% +18A A A A% +135A A% +540% +135B B% +18B B B B% +B B B B B B\)
\(\displaystyle{}A A A A A A% +18A A A A% +135A A% +540% +135B B% +18B B B B% +B B B B B B\)
We have added semicolons to every line in order to show precisely what happens: in the first iteration, the substitution expands $Q$ to $A+B$. This gives an expression in which there are no $AB$ factors yet. Those arise only once the distribute algorithm is called. At the second iteration, the substitution algorithm then replaces the $AB$ product with $3$. Normally one would suppress the printing and only print at the end, as in:
ex:=Q Q Q Q Q Q; converge(ex): substitute(_, $Q->A+B, A B->3$, repeat=True) distribute(_) ;
\(\displaystyle{}Q Q Q Q Q Q\)
\(\displaystyle{}A A A A A A% +18A A A A% +135A A% +540% +135B B% +18B B B B% +B B B B B B\)
Note the semi-colon ; at the very end of the converge block, which triggers printing of the final result.
Copyright © 2001-2017 Kasper Peeters
Questions? info@cadabra.science