# Re: [sage-devel] Re: AlgebraicReal.minpoly slow

Am 2016-09-20 um 20:22 schrieb Marc Mezzarobba:
> Clemens Heuberger wrote:
>> x = polygen(QQ)
>> equation = -960000000*x^7 + 416000000*x^6 - 66400000*x^5 + 5600000*x^4
>> - 280000*x^3 + 8400*x^2 - 140*x + 1 roots = equation.roots(QQbar)
>> a_root = roots[-1][0]
>> abs_root = abs(a_root)
> [...]
>> Is this expected behaviour?
>
> Well, QQbar has a number of well-known but not yet fixed efficiency
> problems...
>
>> I am intersted in the smallest root(s) in
>> absolute value only, any suggestions for achieving that in less time?
>
> You could perhaps compute a polynomial whose roots include the z·conj(z)
> for all roots z of equation (e.g., with a resultant), factor that
> polynomial, and sort its root numerically while increasing the
> precision until you can tell which of the factors correspond to
> dominant roots. Or something like that :-/

The problem is the square root:

sage: x = polygen(QQ)
sage: polynomial = x^5 - 1/3*x^4 + 1/30*x^3 - 1/600*x^2 + 1/24000*x - 1/2400000
sage: %time root = polynomial.roots(QQbar)[1][0]
CPU times: user 20 ms, sys: 0 ns, total: 20 ms
Wall time: 19.7 ms

sage: %time norm_root = root.norm()
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 74.1 µs

sage: %time norm_root.minpoly()
CPU times: user 136 ms, sys: 4 ms, total: 140 ms
Wall time: 137 ms
x^10 - 1/30*x^9 + 37/72000*x^8 - 97/21600000*x^7 + 613/25920000000*x^6 -
2009/25920000000000*x^5 + 19/115200000000000*x^4 - 97/414720000000000000*x^3 +
1/4608000000000000000*x^2 - 1/8294400000000000000000*x +
1/33177600000000000000000000

sage: %time abs_root = sqrt(norm_root)
CPU times: user 8 ms, sys: 0 ns, total: 8 ms
Wall time: 9.44 ms

sage: %time abs_root.minpoly()
CPU times: user 2min 17s, sys: 31.3 s, total: 2min 48s
Wall time: 2min 48s
x^20 - 1/30*x^18 + 37/72000*x^16 - 97/21600000*x^14 + 613/25920000000*x^12 -
2009/25920000000000*x^10 + 19/115200000000000*x^8 - 97/414720000000000000*x^6 +
1/4608000000000000000*x^4 - 1/8294400000000000000000*x^2 +
1/33177600000000000000000000

Especially for taking the square root, it would be rather easy to get a minimal
polynomial by hand:

sage: %time AA.polynomial_root(norm_root.minpoly().subs(x=x^2), ....:
sqrt(RIF(norm_root))).minpoly()
CPU times: user 124 ms, sys: 0 ns, total: 124 ms
Wall time: 124 ms
x^20 - 1/30*x^18 + 37/72000*x^16 - 97/21600000*x^14 + 613/25920000000*x^12 -
2009/25920000000000*x^10 + 19/115200000000000*x^8 - 97/414720000000000000*x^6 +
1/4608000000000000000*x^4 - 1/8294400000000000000000*x^2 +
1/33177600000000000000000000

For my particular problem (finding the root of minimal absolute value), the
solution is actually much simpler: comparing the norms is certainly sufficient
and works instanteneouly.

Regards,

Clemens

--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email