7
$\begingroup$

Here's a simple example for Solve:

test[f_] :=
 ListPlot[Table[{n, 
    First@AbsoluteTiming@With[{c = Nest[f, c, n]}, Solve[c x^2 + x + 1 == 0, x]]}, 
       {n, 0, 100, 5}], Filling -> Axis, PlotRange -> All]

test[Sqrt[c + #] &]

enter image description here

For any value of n, Solve is essentially dealing with the same equation, but the timing increases signifiantly as the coefficient c becomes more compilcated. Similar behavior can be observed in the tests for DSolve and RSolve. (I believe there're more.)

This truth astonishes me, because I thought Mathematica is clever enough to handle this sort of thing so I decide to write this post for complaining. To make this post a question, I want to ask:

  1. Why Mathematica is cheated by the complicated coefficient?

  2. Is there any general method to circumvent the issue? In my simple example, we just need to replace to only complicated coefficient with a simple one, but the coefficient to be replaced is not always obvious.

$\endgroup$
2
  • 3
    $\begingroup$ Maybe something like my ConstantsGrouping` package would be useful here? $\endgroup$
    – jkuczm
    Mar 11, 2016 at 13:55
  • $\begingroup$ @jkuczm That sounds like an answer to me $\endgroup$ Mar 11, 2016 at 14:00

1 Answer 1

8
$\begingroup$

I don't know why Mathematica is slowed down by complicated constant, maybe there's a simple way to avoid it, but until someone finds this simple way you could use my ConstantsGrouping` package.

It provides GroupConstants function that can replace combinations of arbitrary complicated constant expressions with auto-generated "simple" constants. It returns pair containing "simplified" expression and Association of new constants to old constants combinations:

eq = Nest[Sqrt[c + #] &, c, 5] x^2 + x + 1 == 0
GroupConstants[eq, x]
(* 1 + x + Sqrt[c + Sqrt[c + Sqrt[c + Sqrt[Sqrt[2] Sqrt[c] + c]]]] x^2 == 0 *)
(* {
       1 + x + x^2 C[1] == 0,
       <|C[1] -> Sqrt[c + Sqrt[c + Sqrt[c + Sqrt[Sqrt[2] Sqrt[c] + c]]]]|>
} *)

One can solve "simplified" equation, then replace "simple" constants with original combinations of constants to get the same result as solving original equation:

Solve[eq, x] ===
    With[{eqConstsPair = GroupConstants[eq, x]},
        Solve[First@eqConstsPair, x] /. Last@eqConstsPair
    ]
(* True *)

Solve timings with and without GroupConstants:

ListPlot[
    With[{f = Sqrt[c + #] &},
        Table[
            {
                n, 
                With[{c = Nest[f, c, n]}, 
                    First@AbsoluteTiming@Solve[c x^2 + x + 1 == 0, x]
                ]
            },
            {n, 0, 100, 5}]
    ],
    Filling -> Axis, PlotRange -> All
]

ListPlot[
    With[{f = Sqrt[c + #] &}, 
        Table[
            {
                n,
                With[{c = Nest[f, c, n]},
                    First@AbsoluteTiming@With[
                        {eqConstsPair = GroupConstants[c x^2 + x + 1 == 0, x]},
                        Solve[First@eqConstsPair, x] /. Last@eqConstsPair
                    ]
                ]
            },
            {n, 0, 100, 5}
        ]
    ],
    Filling -> Axis, PlotRange -> All
]

Timing plots

$\endgroup$
2
  • $\begingroup$ I really like this answer, and I really like your package as well! Have you considered adding it to the listings at PackageData.net? (+1 of course) $\endgroup$
    – MarcoB
    Mar 11, 2016 at 15:30
  • $\begingroup$ @MarcoB Done. Currently it just links to M.SE answer which, I guess, is not very convenient. When I find some time I'll move it to GitHub. $\endgroup$
    – jkuczm
    Mar 12, 2016 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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