1
$\begingroup$

Why is CoefficientRules so slow in this example (v10.2 on OS X 10.11.4)?

expr = Sum[x^i, {i, 1, 15}]^30;
CoefficientRules[expr/(expr + expr^2), y]; // AbsoluteTiming
MonomialList[expr/(expr + expr^2), y]; // AbsoluteTiming
CoefficientRules[Expand@(expr/(expr + expr^2)), y]; // AbsoluteTiming
CoefficientList[expr/(expr + expr^2), y]; // AbsoluteTiming

(* Out: 
    {1.83157, Null}
    {1.42334, Null}
    {8.48815, Null}
    {0.000063, Null}
*)

Note that it does not seem to be related to the similar issue that Coefficient does not always expand the expression. Also note that the expression to which CoefficientRules[#, y] & is applied does not actually contain y.

Is there any clever way of efficiently achieving the result of CoefficientRules or MonomialList without parsing the output of CoefficientList (as I want to generally be able to use this efficiently in the multivariate case)?

Improve this question
$\endgroup$
7
  • $\begingroup$ Am I missing something here? expr/(expr + expr^2) does not result in a polynomial, which is what's expected for the first argument of those functions. $\endgroup$
    – ciao
    Commented Apr 27, 2016 at 23:12
  • $\begingroup$ @ciao it is not a polynomial in x, but it is a zero degree polynomial in y, and is correctly processed by all these functions $\endgroup$
    – Peter Kravchuk
    Commented Apr 28, 2016 at 0:21
  • $\begingroup$ What version of Mathematica are you using? On v8, my computer takes 270 seconds to finish CoefficientRules[Expand@#,y]& (but only 1 second to do the first two). Timings on v9 are similar to yours. On v10.3, it takes 15 seconds to do first three (regression?) on 10.4 it takes 17 seconds on the first three (further regression). $\endgroup$
    – QuantumDot
    Commented Apr 28, 2016 at 7:54
  • 2
    $\begingroup$ Peter, @QuantumDot, I wonder if you could repeat the measurements using AbsoluteTiming, rather than Timing. The latter may be confusing sometimes and it is hard to compare different operating systems / CPU architectures (see Details on AbsoluteTiming, "On certain computer systems with multiple CPUs, the Wolfram Language kernel may sometimes spawn additional threads on different CPUs. On some operating systems, Timing may ignore these additional threads. On other operating systems, it may give the total time spent in all threads, which may exceed the result from AbsoluteTiming."). $\endgroup$
    – MarcoB
    Commented Apr 28, 2016 at 17:16
  • 1
    $\begingroup$ On MMA 10.4, Win7-64, using AbsoluteTiming, it takes roughly 9s to execute each of the first three lines, and 38ms for the last. $\endgroup$
    – MarcoB
    Commented Apr 28, 2016 at 17:18

2 Answers 2

Reset to default
5
$\begingroup$

Not an answer, but just a collection of results on my computer (Mac OS X 11.4).

The timings are in seconds as reported by AbsoluteTiming. They are in the same order as the test cases provided by OP

On Mathematica 8: -- {1.44, 1.33, 271.7, 0.000066}

On Mathematica 9: -- {0.62, 0.61, 9.00, 0.00012}

On Mathematica 10.3 : {8.82, 8.78, 8.62, 0.00006}

On Mathematica 10.4 : {8.71, 8.93, 8.83, 0.00011}

On Mathematica 11.0: {8.04, 8.17, 8.24, 0.00023}

On Mathematica 11.2: {8.55, 8.52, 8.38, 0.0056}

Edit: the behavior continues through version 11.2.0

Improve this answer
$\endgroup$
1
  • $\begingroup$ @MarcoB v10.2, OS X El Cap. 10.11.4, AbsoluteTiming gives {1.83, 1.42, 8.48, 0.00006} $\endgroup$
    – Peter Kravchuk
    Commented Apr 28, 2016 at 17:52
4
$\begingroup$

This is not an answer. But I can pinpoint the origin of performance regression of CoefficientRules from version 9.0 to 10.3. This requires Spelunking tools.

After calling CoefficientRules to initialize it, run

<< Spelunk`
Spelunk[CoefficientRules]

CoefficientRules code

This code is identical in v9 and v10. Now spelunk deeper by inspecting GroebnerBasis`DTL, accessed by clicking on one of the DTL buttons in the code above.

The code for DTL is longer. But two-thirds of the way down, is the first call to GroebnerBasis`DistributedTermsList (also a button). That line has been changed from version 9 to 10. In version 9, it is:

Version 9 DTL code

but in version 10, they have slipped in a call to Expand (which I highlighted for clarity):

Version 10 DTL code

This extra Expand causes the performance degradation for large polynomials. Presumably, this was added because a bug was found causing DTL to return an incorrect result in certain cases without Expanding the input polynomial.

It seems like GroebnerBasis`DistributedTermsList is the faster low-level function, and CoefficientRules has a bunch of overhead. In principle, if you know the precise form of the input polynomial along with the relevant variables, it should be possible to directly make the call to GroebnerBasis`DistributedTermsList in your code.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I do recall there was a bug fix along those lines, so this is indeed probably what happened. A plausible improvement I need to consider is a precheck whether the input is already explicitly polynomial in the given variables. $\endgroup$
    – Daniel Lichtblau
    Commented Sep 22, 2016 at 9:15

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.