Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Suppose I have an expression like

1/8 + 1/8 Sqrt[1 - 28 (2/(3 (Sqrt[4197] - 9)))^(1/3) + 2 (2/3)^(2/3) (Sqrt[4197] - 9)^(1/3)]
 - 1/2 Sqrt[1/8 - (1/2 (Sqrt[4197] - 9))^(1/3)/(4 3^(2/3)) + 7/(2 2^(2/3) (3 (Sqrt[4197] - 9))^(1/3))
 - 7/(8 Sqrt[1 - 28 (2/(3 (Sqrt[4197] - 9)))^(1/3) + 2 (2/3)^(2/3) (Sqrt[4197] - 9)^(1/3)])]

which contains repeated common subexpressions. I am interested in an algorithm that can decompose it into parts of the minimal (or close to minimal) total complexity. The expected output should be something like this:

(1 + α - Sqrt[3 - β - 14/α]) / 8 
  /. α -> Sqrt[β]
  /. β -> 1 + 2 γ - 56/(3 γ)  
  /. γ -> (4 Sqrt[4197]/9 - 4)^(1/3)

(if you ever worked with Maple, this is similar to how it formats complex output expressions)

share|improve this question

marked as duplicate by Oleksandr R., Michael E2, Sjoerd C. de Vries, Mr.Wizard Jun 9 '13 at 1:45

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2  
FullSimplify looks like it does a better job. –  Spawn1701D Jun 6 '13 at 3:56
3  
You've seen Experimental`OptimizeExpression? Although it's meant for numerical applications, its job is indeed CSE. –  Oleksandr R. Jun 6 '13 at 3:59
    
@Oleksandr, I think there was a question before that was also answered by Experimental`OptimizeExpression[]; would you happen to remember it? –  J. M. Jun 6 '13 at 4:00
1  
@0x4A4D (25132), (2878), (8787)? More closely related to this question: (9750). –  Oleksandr R. Jun 6 '13 at 4:06
    
@Oleksandr, I had the second one in mind. Thanks! –  J. M. Jun 6 '13 at 4:11
show 4 more comments

1 Answer 1

up vote 4 down vote accepted

I once tried doing something like this myself, and ended up with a semi-manual process.

Clear[branches, tallyBranches];
branches[b_?AtomQ] := {};
branches[b_?NumberQ] := {};
branches[h_[b___]] := Flatten@Append[branches /@ List[b], h[b]];
tallyBranches[e_, k_Integer: 2] := 
  TableForm[Reverse /@ Cases[Tally[branches[e]], {_, t_ /; t >= k}]]

Let's take the solution to the cubic as an example:

cube = Solve[a x^3 + b x^2 + c x + d == 0, x];

Generate a table of common branches (with at least 9 occurrences):

tallyBranches[cube, 9]

9   1/a
9   b^2
9   -b^2
9   3 a c
9   -b^2+3 a c
12  b^3
12  -2 b^3
12  9 a b c
12  a^2
12  -27 a^2 d

Then we can manually pick a branch to substitute:

cube2 = cube //. -b^2 + 3 a c -> α;

And then repeat:

tallyBranches[cube2, 6];

Etc..

After three substitutions we end up with something like this:

$$\left\{\left\{x\to -\frac{\sqrt[3]{2} \alpha }{3 a \sqrt[3]{\gamma }}-\frac{b}{3 a}+\frac{\sqrt[3]{\gamma }}{3 \sqrt[3]{2} a}\right\},\left\{x\to \frac{\left(1+i \sqrt{3}\right) \alpha }{3\ 2^{2/3} a \sqrt[3]{\gamma }}-\frac{b}{3 a}-\frac{\left(1-i \sqrt{3}\right) \sqrt[3]{\gamma }}{6 \sqrt[3]{2} a}\right\},\left\{x\to \frac{\left(1-i \sqrt{3}\right) \alpha }{3\ 2^{2/3} a \sqrt[3]{\gamma }}-\frac{b}{3 a}-\frac{\left(1+i \sqrt{3}\right) \sqrt[3]{\gamma }}{6 \sqrt[3]{2} a}\right\}\right\}$$

where $\alpha =3 a c-b^2$, $\beta =-27 a^2 d+9 a b c-2 b^3$, and $\gamma =\sqrt{4 \alpha ^3+\beta ^2}+\beta$.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.