Skip to main content

symbolic - How to decompose a complex expression containing repeated subexpressions?



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)



Answer



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$.


Comments

Post a Comment

Popular posts from this blog

functions - Get leading series expansion term?

Given a function f[x] , I would like to have a function leadingSeries that returns just the leading term in the series around x=0 . For example: leadingSeries[(1/x + 2)/(4 + 1/x^2 + x)] x and leadingSeries[(1/x + 2 + (1 - 1/x^3)/4)/(4 + x)] -(1/(16 x^3)) Is there such a function in Mathematica? Or maybe one can implement it efficiently? EDIT I finally went with the following implementation, based on Carl Woll 's answer: lds[ex_,x_]:=( (ex/.x->(x+O[x]^2))/.SeriesData[U_,Z_,L_List,Mi_,Ma_,De_]:>SeriesData[U,Z,{L[[1]]},Mi,Mi+1,De]//Quiet//Normal) The advantage is, that this one also properly works with functions whose leading term is a constant: lds[Exp[x],x] 1 Answer Update 1 Updated to eliminate SeriesData and to not return additional terms Perhaps you could use: leadingSeries[expr_, x_] := Normal[expr /. x->(x+O[x]^2) /. a_List :> Take[a, 1]] Then for your examples: leadingSeries[(1/x + 2)/(4 + 1/x^2 + x), x] leadingSeries[Exp[x], x] leadingSeries[(1/x + 2 + (1 - 1/x...
Post a Comment
Read more

How to thread a list

I have data in format data = {{a1, a2}, {b1, b2}, {c1, c2}, {d1, d2}} Tableform: I want to thread it to : tdata = {{{a1, b1}, {a2, b2}}, {{a1, c1}, {a2, c2}}, {{a1, d1}, {a2, d2}}} Tableform: And I would like to do better then pseudofunction[n_] := Transpose[{data2[[1]], data2[[n]]}]; SetAttributes[pseudofunction, Listable]; Range[2, 4] // pseudofunction Here is my benchmark data, where data3 is normal sample of real data. data3 = Drop[ExcelWorkBook[[Column1 ;; Column4]], None, 1]; data2 = {a #, b #, c #, d #} & /@ Range[1, 10^5]; data = RandomReal[{0, 1}, {10^6, 4}]; Here is my benchmark code kptnw[list_] := Transpose[{Table[First@#, {Length@# - 1}], Rest@#}, {3, 1, 2}] &@list kptnw2[list_] := Transpose[{ConstantArray[First@#, Length@# - 1], Rest@#}, {3, 1, 2}] &@list OleksandrR[list_] := Flatten[Outer[List, List@First[list], Rest[list], 1], {{2}, {1, 4}}] paradox2[list_] := Partition[Riffle[list[[1]], #], 2] & /@ Drop[list, 1] RM[list_] := FoldList[Transpose[{First@li...
Post a Comment
Read more

front end - keyboard shortcut to invoke Insert new matrix

I frequently need to type in some matrices, and the menu command Insert > Table/Matrix > New... allows matrices with lines drawn between columns and rows, which is very helpful. I would like to make a keyboard shortcut for it, but cannot find the relevant frontend token command (4209405) for it. Since the FullForm[] and InputForm[] of matrices with lines drawn between rows and columns is the same as those without lines, it's hard to do this via 3rd party system-wide text expanders (e.g. autohotkey or atext on mac). How does one assign a keyboard shortcut for the menu item Insert > Table/Matrix > New... , preferably using only mathematica? Thanks! Answer In the MenuSetup.tr (for linux located in the $InstallationDirectory/SystemFiles/FrontEnd/TextResources/X/ directory), I changed the line MenuItem["&New...", "CreateGridBoxDialog"] to read MenuItem["&New...", "CreateGridBoxDialog", MenuKey["m", Modifiers-...
Post a Comment
Read more