MathGroup Archive 2010

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: SymbolicPolynomialMod

  • To: mathgroup at smc.vnet.net
  • Subject: [mg106580] Re: [mg106564] SymbolicPolynomialMod
  • From: danl at wolfram.com
  • Date: Sun, 17 Jan 2010 07:10:42 -0500 (EST)
  • References: <201001141046.FAA19729@smc.vnet.net>

> Dear Mathematica Gurus!
>
> Who know how to execute SymbolicPolynomialMod
> PolynomialMod working only on numbers (not for symbols)
>
> If we know that a,b,c,d,f are five roots of general quintic polynomial
> X^5+t X^4+p X^3+q X^2+r X+s==0
>
> Then we can do SymbolicPolynomialMod of g (manually not by Mathemathica
> unfortunatelly)
>
> g=(a^6 b^7 c^5 d^2 + a^7 b^5 c^6 d^2 + a^5 b^6 c^7 d^2 +
>  a^7 b^6 c^2 d^5 + a^2 b^7 c^6 d^5 + a^6 b^2 c^7 d^5 +
>  a^5 b^7 c^2 d^6 + a^7 b^2 c^5 d^6 + a^2 b^5 c^7 d^6 +
>  a^6 b^5 c^2 d^7 + a^2 b^6 c^5 d^7 + a^5 b^2 c^6 d^7 -
>  a^6 b^8 c^3 d^2 f - a^8 b^3 c^6 d^2 f - a^3 b^6 c^8 d^2 f -
>  a^8 b^6 c^2 d^3 f - a^2 b^8 c^6 d^3 f - a^6 b^2 c^8 d^3 f -
>  a^3 b^8 c^2 d^6 f - a^8 b^2 c^3 d^6 f - a^2 b^3 c^8 d^6 f -
>  a^6 b^3 c^2 d^8 f - a^2 b^6 c^3 d^8 f - a^3 b^2 c^6 d^8 f +
>  a^7 b^6 c^5 f^2 + a^5 b^7 c^6 f^2 + a^6 b^5 c^7 f^2 -
>  a^8 b^6 c^3 d f^2 - a^3 b^8 c^6 d f^2 - a^6 b^3 c^8 d f^2 -
>  a^6 b^8 c d^3 f^2 - a^8 b c^6 d^3 f^2 - a b^6 c^8 d^3 f^2 +
>  a^6 b^7 d^5 f^2 + a^7 c^6 d^5 f^2 + b^6 c^7 d^5 f^2 +
>  a^7 b^5 d^6 f^2 - a^8 b^3 c d^6 f^2 - a b^8 c^3 d^6 f^2 +
>  b^7 c^5 d^6 f^2 + a^5 c^7 d^6 f^2 - a^3 b c^8 d^6 f^2 +
>  a^5 b^6 d^7 f^2 + a^6 c^5 d^7 f^2 + b^5 c^6 d^7 f^2 -
>  a^3 b^6 c d^8 f^2 - a^6 b c^3 d^8 f^2 - a b^3 c^6 d^8 f^2 -
>  a^6 b^8 c^2 d f^3 - a^8 b^2 c^6 d f^3 - a^2 b^6 c^8 d f^3 -
>  a^8 b^6 c d^2 f^3 - a b^8 c^6 d^2 f^3 - a^6 b c^8 d^2 f^3 -
>  a^2 b^8 c d^6 f^3 - a^8 b c^2 d^6 f^3 - a b^2 c^8 d^6 f^3 -
>  a^6 b^2 c d^8 f^3 - a b^6 c^2 d^8 f^3 - a^2 b c^6 d^8 f^3 +
>  a^6 b^7 c^2 f^5 + a^7 b^2 c^6 f^5 + a^2 b^6 c^7 f^5 +
>  a^7 b^6 d^2 f^5 + b^7 c^6 d^2 f^5 + a^6 c^7 d^2 f^5 +
>  a^2 b^7 d^6 f^5 + a^7 c^2 d^6 f^5 + b^2 c^7 d^6 f^5 +
>  a^6 b^2 d^7 f^5 + b^6 c^2 d^7 f^5 + a^2 c^6 d^7 f^5 +
>  a^7 b^5 c^2 f^6 + a^2 b^7 c^5 f^6 + a^5 b^2 c^7 f^6 -
>  a^8 b^3 c^2 d f^6 - a^2 b^8 c^3 d f^6 - a^3 b^2 c^8 d f^6 +
>  a^5 b^7 d^2 f^6 - a^3 b^8 c d^2 f^6 - a^8 b c^3 d^2 f^6 +
>  a^7 c^5 d^2 f^6 + b^5 c^7 d^2 f^6 - a b^3 c^8 d^2 f^6 -
>  a^8 b^2 c d^3 f^6 - a b^8 c^2 d^3 f^6 - a^2 b c^8 d^3 f^6 +
>  a^7 b^2 d^5 f^6 + b^7 c^2 d^5 f^6 + a^2 c^7 d^5 f^6 +
>  a^2 b^5 d^7 f^6 + a^5 c^2 d^7 f^6 + b^2 c^5 d^7 f^6 -
>  a^2 b^3 c d^8 f^6 - a^3 b c^2 d^8 f^6 - a b^2 c^3 d^8 f^6 +
>  a^5 b^6 c^2 f^7 + a^6 b^2 c^5 f^7 + a^2 b^5 c^6 f^7 +
>  a^6 b^5 d^2 f^7 + b^6 c^5 d^2 f^7 + a^5 c^6 d^2 f^7 +
>  a^2 b^6 d^5 f^7 + a^6 c^2 d^5 f^7 + b^2 c^6 d^5 f^7 +
>  a^5 b^2 d^6 f^7 + b^5 c^2 d^6 f^7 + a^2 c^5 d^6 f^7 -
>  a^3 b^6 c^2 d f^8 - a^6 b^2 c^3 d f^8 - a^2 b^3 c^6 d f^8 -
>  a^6 b^3 c d^2 f^8 - a b^6 c^3 d^2 f^8 - a^3 b c^6 d^2 f^8 -
>  a^2 b^6 c d^3 f^8 - a^6 b c^2 d^3 f^8 - a b^2 c^6 d^3 f^8 -
>  a^3 b^2 c d^6 f^8 - a b^3 c^2 d^6 f^8 - a^2 b c^3 d^6 f^8)
>
> by substitutions g/. {a^5->-t a^4-p a^3-q a^2-r a-s,b^5->-t b^4-p b^3-q
> b^2-r b-s,
> c^5->-t c^4-p c^3-q c^2-r c-s,d^5->-t d^4-p d^3-q d^2-r d-s,f^5->-t
> f^4-p f^3-q f^2-r f-s}
>
> etc.
>
> How we can do full SymbolicPolynomialMod on the form g after such
> procedure will be not higher degree as 4 for a,b,c,d,f ?
>
> Best wishes
> Artur

You will want to use PolynomialReduce in one way or another. You could
simply reduce by what amounts to the rules you indicate above. That does
not really do anything to enforce that the roots are distinct, because
those defining polynomials alone do not enforce distinctness. For that,
one can use the set of relations between roots and coefficients. I'll show
this approach. I use Array to get indexed coefficients and roots, so will
translate your polynomial accordingly.

In[19]:= deg = 5;
coeffs = Array[c, deg, 0];
poly = x^deg + coeffs.x^Range[0, deg - 1];
rts = Array[z, deg];
clist = CoefficientList[Apply[Times, x - rts] - poly, x]

Out[52]= {-c[0] - z[1] z[2] z[3] z[4] z[5], -c[1] +
  z[1] z[2] z[3] z[4] + z[1] z[2] z[3] z[5] + z[1] z[2] z[4] z[5] +
  z[1] z[3] z[4] z[5] + z[2] z[3] z[4] z[5], -c[2] - z[1] z[2] z[3] -
  z[1] z[2] z[4] - z[1] z[3] z[4] - z[2] z[3] z[4] - z[1] z[2] z[5] -
  z[1] z[3] z[5] - z[2] z[3] z[5] - z[1] z[4] z[5] - z[2] z[4] z[5] -
  z[3] z[4] z[5], -c[3] + z[1] z[2] + z[1] z[3] + z[2] z[3] +
  z[1] z[4] + z[2] z[4] + z[3] z[4] + z[1] z[5] + z[2] z[5] +
  z[3] z[5] + z[4] z[5], -c[4] - z[1] - z[2] - z[3] - z[4] - z[5]}

That gives the set of defining relations between roots and coefficients.
I'll form a Groebner basis for use in later reduction.

In[25]:= Timing[
 gb = GroebnerBasis[clist, rts,
    MonomialOrder -> DegreeReverseLexicographic,
    CoefficientDomain -> RationalFunctions];]

Out[25]= {0.016, Null}

Fast. Turns out it is the reduction that is slow. Next we translate from
your notation to mine.

g2 = g /. Thread[{a, b, c, d, f} -> rts];

In[30]:= LeafCount[g2]
Out[30]= 2221

We now do the reduction, using the same term ordering as before. Might
want to get a cup of coffee...

In[42]:= Timing[{mults2, red2} =
   PolynomialReduce[g2, gb, rts,
    MonomialOrder -> DegreeReverseLexicographic,
    CoefficientDomain -> RationalFunctions];]
Out[42]= {375.339, Null}

In[43]:= LeafCount[red2]
Out[43]= 22638

That's far bigger than I want to look at, let alone put in email.

Daniel Lichtblau
Wolfram Research




  • Prev by Date: Re: Re: Simplify with NestedLessLess?
  • Next by Date: Re: Re: Simplify with NestedLessLess?
  • Previous by thread: SymbolicPolynomialMod
  • Next by thread: help with finding solutions