factoring over the complex rationals
clicl...@freenet.de
Hello,
the Computer Algebra system Derive cannot factor polynomials over the
complex rational numbers. Can the other systems regularly featured on
sci.math.symbolic do this? Can they decompose
-7*x^6 + 10*x^4 + 24*x^3 - 14*x^2 - 27*x - 42 +
#i*(3*x^6 - 9*x^5 + 30*x^4 + 15*x^3 + 17*x^2 - 33*x - 7)
for example? Can the complex problem perhaps be reduced to the real
problem? If so how? This might allow teaching Derive to handle the
complex case too.
Martin.
PS: Erroneously posted to sci.math, hence reposted here. Thanks to G. A.
Edgar (Maple) for answering there!
Martin Rubey
> Hello,
>
> the Computer Algebra system Derive cannot factor polynomials over the
> complex rational numbers. Can the other systems regularly featured on
> sci.math.symbolic do this? Can they decompose
>
> -7*x^6 + 10*x^4 + 24*x^3 - 14*x^2 - 27*x - 42 +
> #i*(3*x^6 - 9*x^5 + 30*x^4 + 15*x^3 + 17*x^2 - 33*x - 7)
>
> for example?
In FriCAS:
(1) -> p := -7*x^6 + 10*x^4 + 24*x^3 - 14*x^2 - 27*x - 42 + %i*(3*x^6 - 9*x^5 + 30*x^4 + 15*x^3 + 17*x^2 - 33*x - 7)
(1)
6 5 4 3 2
(- 7 + 3%i)x - 9%i x + (10 + 30%i)x + (24 + 15%i)x + (- 14 + 17%i)x
+
(- 27 - 33%i)x - 42 - 7%i
Type: Polynomial(Complex(Integer))
(2) -> factors factor p
(2)
3 2
[[factor= (1 + %i)x - x + (5 - 3%i)x - 7%i,exponent= 1],
3 2
[factor= (5 + 2%i)x + (- 1 + 3%i)x - 2x - 6 - %i,exponent= 1]]
Type: List(Record(factor: Polynomial(Complex(Integer)),exponent: Integer))
Martin
Thomas Richard
I'm not familiar with FriCAS, but isn't a constant factor %i missing
here?
Or are the factors normed automatically in some way?
--
Thomas Richard
Technical Support Maple/MapleSim
Scientific Computers GmbH
http://www.scientific.de
Martin Rubey
I'm very sorry, I omitted
(3) -> unit (factor p)
(3) %i
Type: Polynomial(Complex(Integer))
Martin
mark mcclure
> the Computer Algebra system Derive cannot factor polynomials over the
> complex rational numbers. Can the other systems regularly featured on
> sci.math.symbolic do this? Can they decompose
>
> -7*x^6 + 10*x^4 + 24*x^3 - 14*x^2 - 27*x - 42 +
> #i*(3*x^6 - 9*x^5 + 30*x^4 + 15*x^3 + 17*x^2 - 33*x - 7)
>
> for example?
In Mathematica:
Factor[-7*x^6 + 10*x^4 + 24*x^3 - 14*x^2 - 27*x - 42 +
I*(3*x^6 - 9*x^5 + 30*x^4 + 15*x^3 + 17*x^2 - 33*x - 7),
GaussianIntegers -> True] // InputForm
(7+(3+5*I)*x-I*x^2-(1-I)*x^3)*((-6-I)-2*x-(1-3*I)*x^2+(5+2*I)*x^3)
In Maxima:
gfactor(-7*x^6 + 10*x^4 + 24*x^3 - 14*x^2 - 27*x - 42 +
%i*(3*x^6 - 9*x^5 + 30*x^4 + 15*x^3 + 17*x^2 - 33*x - 7));
(3*%i-7)*(2*x^3+%i*x^2-x^2-8*%i*x+2*x-7*%i-7)*
(29*x^3+17*%i*x^2+x^2+4*%i*x-10*x+7*%i-32)/58
Expanding the difference in either system yields zero.
Mark McClure
Eberhard Schruefer
>
> Hello,
>
> the Computer Algebra system Derive cannot factor polynomials over the
> complex rational numbers. Can the other systems regularly featured on
> sci.math.symbolic do this? Can they decompose
>
> -7*x^6 + 10*x^4 + 24*x^3 - 14*x^2 - 27*x - 42 +
> #i*(3*x^6 - 9*x^5 + 30*x^4 + 15*x^3 + 17*x^2 - 33*x - 7)
>
> for example? Can the complex problem perhaps be reduced to the real
> problem? If so how? This might allow teaching Derive to handle the
> complex case too.
>
Open-reduce can do it. The problem is indeed reduced to factor a
polynomial over the integer. Roughly speaking one calculates the
norm of the polynomial (which is a polynomial over the integer)
and then recovers the factor by gcd calculations. References for the
algorithms are B. Trager, van der Waerdens. The complexity of this
algorithm is of course bad as one has to factor the norm.
Eberhard
Axel Vogt
> "G. A. Edgar" <ed...@math.ohio-state.edu.invalid> writes:
>> In article <4AF80D68...@freenet.de>, <clicl...@freenet.de>
>> wrote:
>>
>>> Hello,
>>>
>>> the Computer Algebra system Derive cannot factor polynomials over the
>>> complex rational numbers. Can the other systems regularly featured on
>>> sci.math.symbolic do this? Can they decompose
>>>
>>> -7*x^6 + 10*x^4 + 24*x^3 - 14*x^2 - 27*x - 42 +
>>> #i*(3*x^6 - 9*x^5 + 30*x^4 + 15*x^3 + 17*x^2 - 33*x - 7)
>>>
>>> for example? Can the complex problem perhaps be reduced to the real
>>> problem? If so how? This might allow teaching Derive to handle the
>>> complex case too.
>>>
>> Maple...
>>
>> p :=
>>
>> factor(p);
>>
>> (-7/58+(3/58)*I)*((-7-7*I)+2*x-(8*I)*x-x^2+I*x^2+2*x^3)
>> *(29*x^3+x^2+(17*I)*x^2-10*x+(4*I)*x+(-32+7*I))
>
> Maple = big gun. Never seen anything it couldn't do!
>
> The free Pari/GP pops this out happily:
>
> ? factor(f)
>
> [x^3 + (-1/2 + 1/2*I)*x^2 + (1 - 4*I)*x + (-7/2 - 7/2*I) 1]
>
> [x^3 + (1/29 + 17/29*I)*x^2 + (-10/29 + 4/29*I)*x + (-32/29 + 7/29*I) 1]
>
> (Yes, it deliberately bins the content (-7 + 3*I) of the polynomial.)
>
> Phil
Ok. Maple just replies by rational * integer polynomial, which may be matter of
taste.
All (?) the answers just take the example, but leave open the questions ...
Daniel Lichtblau
> Phil Carmody wrote:
> > "G. A. Edgar" <ed...@math.ohio-state.edu.invalid> writes:
One respondent (Eberhard Schruefer) on sci.math.symbolic mentioned how
to reduce to factoring over Q. To elaborate ever so slightly, here is
the example factored in Mathematica according to the approach he
mentioned. Okay, not quite factored; I'm omitting the adjustment-of-
unit-content step.
poly = -7*x^6 + 10*x^4 + 24*x^3 - 14*x^2 - 27*x - 42 +
I*(3*x^6 - 9*x^5 + 30*x^4 + 15*x^3 + 17*x^2 - 33*x - 7);
InputForm[normpoly = ComplexExpand[poly*Conjugate[poly]]]
Out[2]//InputForm=
1813 + 2730*x + 2756*x^2 - 2592*x^3 - 3061*x^4 - 2556*x^5 + 2681*x^6
+
1254*x^7 + 1028*x^8 - 786*x^9 + 121*x^10 - 54*x^11 + 58*x^12
InputForm[fax = FactorList[normpoly]]
Out[3]//InputForm=
{{1, 1}, {49 + 42*x + 34*x^2 - 24*x^3 + 5*x^4 - 2*x^5 + 2*x^6, 1},
{37 + 24*x + 10*x^2 - 60*x^3 - 10*x^4 + 2*x^5 + 29*x^6, 1}}
{fax2,expons} = Transpose[Rest[fax]];
InputForm[Map[PolynomialGCD[poly,#]&, fax2]^expons]
Out[5]//InputForm=
{-7*I + (5 - 3*I)*x - x^2 + (1 + I)*x^3, (-6 - I) - 2*x - (1 - 3*I)
*x^2 +
(5 + 2*I)*x^3}
The missing step would be to expand this product, divide it into the
original polynomial, and find the content. Or just do that with
leading coefficients, since that's cheaper.
Daniel Lichtblau
Wolfram Research
clicl...@freenet.de
Daniel Lichtblau schrieb:
This "||^2 plus GCD" approach should be straightforward to implement as
a Derive procedure. I think the increase in complexity from the degree
doubling will be more or less compensated by not having to deal with
complex numbers during the factorization. Thanks.
Martin.
Thomas Richard
> Ok. Maple just replies by rational * integer polynomial, which may be matter of
> taste.
You can also get the representation returned by some other systems
through GaussInt[GIfacpoly](p) where p is the original polynomial.
clicl...@freenet.de
clicl...@freenet.de schrieb:
There seems to be a problem with the GCD part though: if the polynomial
to be factored contains both the factor f_i and conj(f_i), a GCD
calculation cannot be used to separate the two. Instead a sqrt-type
algorithm is needed to split |f_i|^2 into f_i and conj(f_i). But if you
have such an algorithm you don't need GCD calculations at all, which
leads to the question: what do the various systems (and Open_Reduce in
particular) return as the (complex, rational) factorization of
29*x^6 + 2*x^5 - 10*x^4 - 60*x^3 + 10*x^2 + 24*x + 37
?
Martin.
Eberhard Schruefer
Open_Reduce returns the following
1: on complex;
2: w := 29*x^6+2*x^5-10*x^4-60*x^3+10*x^2+24*x+37;
6 5 4 3 2
w := 29*x + 2*x - 10*x - 60*x + 10*x + 24*x + 37
3: factorize w;
3 2
{{(2 + 5*i)*x + (3 - i)*x - 2*i*x - (1 + 6*i),1},
3 2
{(2 - 5*i)*x + (3 + i)*x + 2*i*x - (1 - 6*i),1}}
Eberhard
Axel Vogt
> On 9 Nov., 22:07, Axel Vogt <&nore...@axelvogt.de> wrote:
>
>> Ok. Maple just replies by rational * integer polynomial, which may be matter of
>> taste.
>
> You can also get the representation returned by some other systems
> through GaussInt[GIfacpoly](p) where p is the original polynomial.
Not quite a command taht I would have been searching for :-)
Eberhard Schruefer
Sorry, I forgot to attach how the algorithm works in this
case: If the norm of the polynomial to be factored is not
square-free then one makes the shift x -> x + i and proceeds
with this transformed polynomial as before.
After the gcd's are calculated one needs to undo the
shift to get the factors of the original polynomial.
Eberhard
clicl...@freenet.de
Eberhard Schruefer schrieb:
> On 11/10/2009 08:23 PM, Eberhard Schruefer wrote:
> > On 11/10/2009 08:13 PM, clicl...@freenet.de wrote:
> >> clicl...@freenet.de schrieb:
> >>>
> >>> as a Derive procedure. I think the increase in complexity from the
> >>> degree doubling will be more or less compensated by not having to
> >>> deal> with complex numbers during the factorization. Thanks.
> >>>
> >>
> >> There seems to be a problem with the GCD part though: if the polynomial
> >> to be factored contains both the factor f_i and conj(f_i), a GCD
> >> calculation cannot be used to separate the two. Instead a sqrt-type
> >> algorithm is needed to split |f_i|^2 into f_i and conj(f_i). But if you
> >> have such an algorithm you don't need GCD calculations at all, which
> >> leads to the question: what do the various systems (and Open_Reduce in
> >> particular) return as the (complex, rational) factorization of
> >>
> >> 29*x^6 + 2*x^5 - 10*x^4 - 60*x^3 + 10*x^2 + 24*x + 37
> >>
> >> ?
> >>
> >
> >
> > 1: on complex;
> >
> > 2: w := 29*x^6+2*x^5-10*x^4-60*x^3+10*x^2+24*x+37;
> >
> > 6 5 4 3 2
> > w := 29*x + 2*x - 10*x - 60*x + 10*x + 24*x + 37
> >
> > 3: factorize w;
> >
> > 3 2
> > {{(2 + 5*i)*x + (3 - i)*x - 2*i*x - (1 + 6*i),1},
> >
> > 3 2
> > {(2 - 5*i)*x + (3 + i)*x + 2*i*x - (1 - 6*i),1}}
> >
>
> case: If the norm of the polynomial to be factored is not
> square-free then one makes the shift x -> x + i and proceeds
> with this transformed polynomial as before.
> After the gcd's are calculated one needs to undo the
> shift to get the factors of the original polynomial.
>
There is a problem with this procedure too: if the polynomial p(x) to be
factored itself is not square-free, such as p(x) = x^4 + 2*x + 1, the
norm polynomial |p(x)|^2 cannot be made square-free by a (possibly
repeated) shift x -> x + i. The shift should therefore be applied only
until p and CONJ(p) have no common polynomial factor, i.e. until
POLY_GCD(p(x),CONJ(p(x))) does not depend on x. This finally seems to be
a general procedure!
Martin.
Eberhard Schruefer
If the polynomial to be factored is not square-free one would do a
square-free factorization first (also taking out the content of the
polynomial) and then performing the algorithm I described on the parts.
Eberhard