[GAP Forum] RootsOfPolynomialAsRadicals - nffactor: the PARI stack overflows

[John McKay]

 I remark on solving for the radical roots of f(x) in Z[x]?

We need all  solution (g,h) to f divides g(h(x)) which I call the
ideal decompositon problem. This - by Casperson, Ford, & McKay -
is in:

Casperson, D., Ford, D., McKay, J., Ideal Decompositions and
Subfields. J. Symbolic Computation, J.Symb.Comp., 21,133-137, (1996).
where we use lattice reduction.

Thanks,

John McKay








On Wed, 8 May 2013, Andreas Distler wrote:

> Dear Daniel,
>
> I cannot reproduce your problem. Which version of PARI/GP are you using?
>
> Anyway, you can use the function SetPariStackSize from the Alnuth
> package to increase the amount of memory PARI/GP will use. The function
> takes a positive integer as argument specifying the amount of memory in
> MB. The default value is 128 MB as you may have guessed.
>
> It's an oversight that SetPariStackSize is not documented. I will change
> this in the next version of Alnuth. Thanks for pointing me to this
> shortcoming.
>
> Best wishes,
>
>     Andreas
>
> On 07/05/13 21:31, Daniel Blazewicz wrote:
> > Hi,
> >
> > I use RootsOfPolynomialAsRadicals from RadiRoot package to compute roots of some simple polynomials of degree 5 and 6. In many cases mentioned method works excellent and produces very nice formulas. However for few specific polynomials it fails with stack overflow error. This is fully deterministic behavior on my environment, e.g. for f(x) = x^6+30*x+93 :
> >
> >
> >   ┌───────┐   GAP, Version 4.6.2 of 02-Feb-2013 (free software, GPL)
> >   │  GAP  │   http://www.gap-system.org
> >   └───────┘   Architecture: i686-pc-linux-gnu-gcc-default32
> >   Libs used:  gmp, readline
> >   Loading the library and packages ...
> >   Components: trans 1.0, prim 2.1, small* 1.0, id* 1.0
> >   Packages:   AClib 1.2, Alnuth 3.0.0, AtlasRep 1.5.0, AutPGrp 1.5, Browse 1.8.2, CRISP 1.3.5, Cryst 4.1.11, CrystCat 1.1.6, CTblLib 1.2.1,
> >               FactInt 1.5.3, FGA 1.2.0, GAPDoc 1.5.1, IO 4.2, IRREDSOL 1.2.1, LAGUNA 3.6.3, Polenta 1.3.1, Polycyclic 2.10.1, RadiRoot 2.6,
> >               ResClasses 3.3.0, Sophus 1.23, TomLib 1.2.2
> >   Try '?help' for help. See also  '?copyright' and  '?authors'
> > gap> x := Indeterminate( Rationals, "x" );;
> > gap> f := UnivariatePolynomial( Rationals, [93,30,0,0,0,0,1]);;
> > gap> RootsOfPolynomialAsRadicals(f, "latex", "x6_30x_93");;
> >    ***   at top-level: ...n(),[2,4,3])>=0,fac=lift(nffactor(f,pol)),if(
> >    ***                                             ^--------------------
> >    *** nffactor: the PARI stack overflows !
> >    current stack size: 128000000 (122.070 Mbytes)
> >    [hint] you can increase GP stack with allocatemem()
> >
> >    ***   at top-level: for(i=1,#fac[,1],for(j=1,fac[i,2
> >    ***                             ^--------------------
> >    ***   _[,_]: not a matrix.
> > Error, List Element: <list>[1] must have an assigned value in
> >    faktoren[1] := lcoeff * faktoren[1]; called from
> > FactorsPolynomialPari( AlgExtEmbeddedPol( H, poly ) ) called from
> > FactorsPolynomialAlgExt( erw.H, CyclotomicPolynomial( Rationals, i ) ) called from
> > RR_RootOfUnity( erw, DegreeOverPrimeField( erw.K ) ) called from
> > CallFuncList( RootsOfPolynomialAsRadicalsNC, arg ) called from
> > <function "RootsOfPolynomialAsRadicals">( <arguments> )
> >   called from read-eval loop at line 3 of *stdin*
> > you can 'return;' after assigning a value
> > brk>
> >
> >
> > Other examples:
> > f(x) = x^6+105*x+237
> > f(x) = x^6+243*x+513
> >
> > I don't know how to work around this problem. Tried to increase workspace size but it did not solve the issue. I will be grateful for your help.
> >
> > With regards,
> > Daniel
> >
> > _______________________________________________
> > Forum mailing list
> > Forum at mail.gap-system.org
> > http://mail.gap-system.org/mailman/listinfo/forum
>
>
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
>