Re: polroots stack overflow

[Joerg Arndt <arndt@jjj.de>]

* Sören Lennart Berg <soeren.berg@st.ovgu.de> [Aug 13. 2012 17:47]:
> Hi,
> the input 
> polroots(94.500000000000000000000000000000000000*z^12 - 5652.0000000000000000000000000000000000*z^11 + 144408.00000000000000000000000000000000*z^10 - 2045344.0000000000000000000000000000000*z^9 + 17354184.000000000000000000000000000000*z^8 - 87874688.000000000000000000000000000000*z^7 + 238393856.00000000000000000000000000000*z^6 - 191892480.00000000000000000000000000000*z^5 - 384723072.00000000000000000000000000000*z^4 - 589317120.00000000000000000000000000000*z^3 + 5892556800.0000000000000000000000000000*z^2 - 6157312000.0000000000000000000000000000*z - 3262720000.0000000000000000000000000000)
> 
> results in a stack overflow even when using almost a gigabyte for the stack. Is that a bug or just due to the polynomial having large degree and 'big' coefficients?
> 
> Interestingly the input
> polroots(189/2*z^12 - 5652*z^11 + 144408*z^10 - 2045344*z^9 + 17354184*z^8 - 87874688*z^7 + 238393856*z^6 - 191892480*z^5 - 384723072*z^4 - 589317120*z^3 + 5892556800*z^2 - 6157312000*z - 3262720000)
> works fine (it's mathematically the same polynomial with precise coefficients).
> 
> Is it a good idea to convert the coefficients of a polynomial to precise types(t_INT, t_FRAC) before computing roots? Will this make polroots work 'more stable'?
> 
> Best regards,
> Sören

I can confirm this with:

 GP/PARI CALCULATOR Version 2.5.2 (released)
 amd64 running linux (x86-64/GMP-4.3.2 kernel) 64-bit version
 compiled: Aug  5 2012, gcc-4.5.0 20100604 [gcc-4_5-branch revision 160292] (SUSE Linux)
 (readline v6.1 enabled, extended help enabled)

? polroots(94.500000000000000000000000000000000000*z^12 - 5652.0000000000000000000000000000000000*z^11 + 144408.00000000000000000000000000000000*z^10 - 2045344.0000000000000000000000000000000*z^9 + 17354184.000000000000000000000000000000*z^8 - 87874688.000000000000000000000000000000*z^7 + 238393856.00000000000000000000000000000*z^6 - 191892480.00000000000000000000000000000*z^5 - 384723072.00000000000000000000000000000*z^4 - 589317120.00000000000000000000000000000*z^3 + 5892556800.0000000000000000000000000000*z^2 - 6157312000.0000000000000000000000000000*z - 3262720000.0000000000000000000000000000)
  ***   at top-level: polroots(94.50000000
  ***                 ^--------------------
  *** polroots: the PARI stack overflows !
  current stack size: 2600000000 (2479.553 Mbytes)
  [hint] you can increase GP stack with allocatemem()

  ***   Break loop: type 'break' to go back to GP
break> 

Using 2000 digits of realprecision doesn't change behavior.


The (exact) polynom factors as
[z - 10 4]
[189*z^8 - 3744*z^7 + 25656*z^6 - 62048*z^5 - 33152*z^4 + 217344*z^3 + 620672*z^2 - 1492480*z - 652544 1]
which (multiple root!) might be of help for
finding reduced test cases.


Best regards,   jj