Optimizing an expression – find identical subexpressions and substitute them

Question

I'd like to simplify a complex symbolic expression expr by substituting and listing subexpressions that appear more than once in expr – kind of like Matlab does.

I need to port the result to C code, so the motivation is avoiding unnecessary recomputation of subterms.

To illustrate the idea, let's pick a simple expression expr = Inverse[Array[a, {2,2}]]:

Actual output of MMA when executing Inverse[Array[a, {3,3}]]:

$$ \left( \begin{array}{cc} \frac{a(2,2)}{a(1,1) a(2,2)-a(1,2) a(2,1)} & -\frac{a(1,2)}{a(1,1) a(2,2)-a(1,2) a(2,1)} \\ -\frac{a(2,1)}{a(1,1) a(2,2)-a(1,2) a(2,1)} & \frac{a(1,1)}{a(1,1) a(2,2)-a(1,2) a(2,1)} \\ \end{array} \right) $$

By looking at the output of this simple expression, I can see that the denominator is exactly the same in all of the matrix's elements (the determinant of the matrix).

The desired output of MMA: $$ \left( \begin{array}{cc} \frac{a(2,2)}{S_1} & -\frac{a(1,2)}{S_1} \\ -\frac{a(2,1)}{S_1} & \frac{a(1,1)}{S_1} \\ \end{array} \right), $$

Where:

$$S_1 = a(1,1) a(2,2)-a(1,2) a(2,1)$$

Answer 1

As I noted in my comment above, the undocumented (thus, caveat emptor as usual) method is to use Experimental`OptimizeExpression[]:

Experimental`OptimizeExpression[Inverse[Array[a, {2, 2}]]]
   Experimental`OptimizedExpression[
       Block[{Compile`$9, Compile`$10, Compile`$11, Compile`$12, Compile`$14,
              Compile`$15, Compile`$16, Compile`$17}, 
             Compile`$9 = a[2, 2]; Compile`$10 = a[1, 2]; Compile`$11 = a[2, 1]; 
             Compile`$12 = -Compile`$10 Compile`$11; Compile`$14 = a[1, 1]; 
             Compile`$15 = Compile`$14 Compile`$9; 
             Compile`$16 = Compile`$12 + Compile`$15; 
             Compile`$17 = 1/Compile`$16;
             {{Compile`$9 Compile`$17, -Compile`$10 Compile`$17},
              {-Compile`$11 Compile`$17, Compile`$14 Compile`$17}}]]

The output has a slightly messy appearance, but if you take a careful look at the output, you'll see that e.g. the common factor in the elements of the matrix inverse (i.e. the reciprocal of the determinant) has been separated out, in this case as Compile`$17.