18
$\begingroup$

I have a very simple question which appears not to have already been answered on this forum. Is there built-in functionality that returns the degree of a multivariable polynomial? For example if the polynomial is 

s1 + s2^2 s3 + s3^2 s4^7

I want Mathematica to return 9. If there is no automatic solution, could somebody please suggest a simple (and fast) implementation?

EDIT: I removed my "solution" because it actually only works for simple examples. I tested out the four solutions presented so far on a degree 20 polynomial in 6 variables (ByteCount[poly] = 2006352). I used AbsoluteTiming to determine that the answer I chose is the fastest, with a run-time of 53.06 s for 1000 evaluations. This is quite a bit faster than the closest competitor's run-time of 283.76 s for 1000 evaluations.

UPDATE: I tested the improved version of the solution (the one with random reals) and found that the run-time is now slightly worse but still far better than the competition at 90.52 s for 1000 evaluations.

Improve this question
$\endgroup$
2
  • $\begingroup$ It is written that it is an undecidable problem to find the degree of multivariate polynomial ? mathworld.wolfram.com/PolynomialDegree.html $\endgroup$
    – Smilia
    Jan 24, 2017 at 8:22
  • $\begingroup$ @Smilia, that does not necessarily mean it's impossible to determine the degree of a given specific polynomial. What you were quoting is related to the constant problem, and not being able to determine the highest-degree term in general is equivalent to not being able to determine if the requisite coefficients are zero. $\endgroup$
    – J. M.'s missing motivation ♦
    Jan 24, 2017 at 9:15

5 Answers 5

Reset to default
17
$\begingroup$

Perhaps

 Exponent[# /. Thread[Variables[#] -> \[FormalX]], \[FormalX]] &[s1 + s2^2 s3 + s3^2 s4^7]
 (* 9 *)

?

UPDATE: As noted by Daniel in the comments, the original function gives the wrong result if cancellations occur after all variables are replaced by the same symbol. To fix this issue, one can modify the function as 

Exponent[# /. ((# -> \[FormalX] RandomReal[]) & /@ Variables[#]), \[FormalX]] &

(per Daniel's suggestion), or as

Max@Exponent[MonomialList[#] /.Thread[Variables[#] -> \[FormalX]], \[FormalX]]&
Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ In practice, one would use a formal variable for safety... $\endgroup$
    – J. M.'s missing motivation ♦
    Nov 20, 2012 at 12:30
  • $\begingroup$ @J.M. thank you; updated using your suggestion. $\endgroup$
    – kglr
    Nov 20, 2012 at 12:35
  • 2
    $\begingroup$ Use random reals times \[FormalX] to avoid accidental cancellations. $\endgroup$
    – Daniel Lichtblau
    Nov 20, 2012 at 15:55
  • 6
    $\begingroup$ I learned this the hard way, trying to figure out why a definite integral I knew we were unable to do was instead giving zero. Now zero is, for a number of reasons, a "common" wrong answer in that part of the computational world. But this one was not caused by any of the usual suspects. The thing was split into two pieces, both of which failed. You can guess what $Failed-$Failed gives. $\endgroup$
    – Daniel Lichtblau
    Nov 20, 2012 at 20:04
  • 2
    $\begingroup$ Also safe would be : Exponent[# /. Thread[Variables[#] -> (\[FormalX] Variables[#]]), \[FormalX]] &[s1 + s2^2 s3 + s3^2 s4^7] $\endgroup$
    – Rolf Mertig
    Nov 20, 2012 at 22:35
9
$\begingroup$ 
Max[Plus @@@ CoefficientRules[#][[All, 1]]] &@ (s1 + s2^2 s3 + s3^2 s4^7)

=> 9

Edit

J.M. (in a comment) suggests the following neat modification: 

Max[Cases[CoefficientRules[s1 + s2^2 s3 + s3^2 s4^7], v_?VectorQ :> Total[v], 2]]
Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Alternatively: Max[Cases[CoefficientRules[s1 + s2^2 s3 + s3^2 s4^7], v_?VectorQ :> Total[v], 2]] $\endgroup$
    – J. M.'s missing motivation ♦
    Nov 20, 2012 at 12:29
  • $\begingroup$ That's a very elegant method $\endgroup$
    – user1066
    Nov 20, 2012 at 12:59
  • $\begingroup$ This is the method I was about to add, +1. $\endgroup$
    – rcollyer
    Nov 20, 2012 at 14:12
6
$\begingroup$

Here's an implementation adapted from a routine by Eric Weisstein:

AlgebraicDegree[eqn_, vars_List] := Max[Total[
      GroebnerBasis`DistributedTermsList[eqn /. Equal :> Subtract, vars][[1, All, 1]], {2}]]

AlgebraicDegree[eqn_] := AlgebraicDegree[eqn, Variables[eqn]]

Example:

AlgebraicDegree[s1 + s2^2 s3 + s3^2 s4^7]
   9
Improve this answer
$\endgroup$
2
$\begingroup$

OP's MonomialList[] approach could certainly be simplified somewhat:

Max[Composition[Total[#[[All, 2]]] &, Rest, FactorList] /@
    MonomialList[s1 - s2^2 s3 + 3 s3^2 s4^7]]
   9
Improve this answer
$\endgroup$
0
$\begingroup$

Another way:

In[1]:= ClearSystemCache[]

In[2]:= Through[Thread[
            {
                    (*kglr*)Exponent[# /. ((# -> \[FormalX] RandomReal[])& /@ \
        Variables[
                        #]), \[FormalX]]&
                    ,
                    (*Rolf Mertig*)Max @ Exponent[MonomialList[#] /. \
        Thread[Variables[
                        #] -> \[FormalX]], \[FormalX]]&
                    ,
                    (*user1066*)Max[Plus @@@ CoefficientRules[#][[All, 1]]]&
                    ,
                    (*J. M.'s lack of A.I.１*)Max[Cases[CoefficientRules[#], \
        v_
                        ?VectorQ :> Total[v], 2]]&
                    ,
                    (*J. M.'s lack of \
        A.I.２*)Max[Total[GroebnerBasis`DistributedTermsList[
                        # /. Equal :> Subtract, Variables[#]][[1, All, 1]], \
        {2}]]&
                    ,
                    (*J. M.'s lack of A.I.３*)Max[Composition[Total[#[[All, \
        2]]
                        ]&, Rest, FactorList] /@ MonomialList[#]]&
                    ,
                    (*Mine:*) (Plus @@ # ~ Exponent ~ Variables @ #& /@ \
        MonomialList
                         @ # // Max)&
                } /* EchoTiming
        ][(w + x + y + z) ^ 1*^2]]
>> 0.0001861
>> 9.57767
>> 4.6006
>> 5.28342
>> 3.61365
>> 19.1789
>> 15.815

Out[2]= {100, 100, 100, 100, 100, 100, 100}

Unfortunately, my implementation is rather inefficient. (Why?)

Improve this answer
$\endgroup$

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.