How does roots work over AcbField?

[oskarhenriksson]

One way to approximate the complex roots of a univariate polynomial in Oscar is to define it over an AcbField, and then use the roots command like this:

R, x = polynomial_ring(AcbField(32),"x")
f = x^5-x+1
roots(f)

which returns:

5-element Vector{acb}:
 [-1.16730398 +/- 5.13e-9]
 [0.76488443 +/- 6.12e-9] + [0.35247155 +/- 6.61e-9]*im
 [0.76488443 +/- 6.51e-9] + [-0.35247155 +/- 6.88e-9]*im
 [-0.18123244 +/- 8.66e-9] + [1.08395410 +/- 5.14e-9]*im
 [-0.18123244 +/- 6.73e-9] + [-1.08395410 +/- 3.68e-9]*im 

How is this computed in Oscar? Is there any discussion about this in the documentation somewhere (I couldn't find anything, but maybe I'm looking in the wrong places), or any references available for the algorithm that is being used? Are there any guarantees that all roots are found?

[fieker]

It part of the Arb library, see https://arblib.org/acb_poly.html#root-finding The algorithm is explained there and is supposed to find all roots.

…

On Thu, 14 Dec 2023, 16:08 Oskar Henriksson, ***@***.***> wrote: One way to approximate the complex roots of a univariate polynomial is to define it over an AcbField <https://docs.oscar-system.org/stable/Nemo/acb/>, and then use the roots command like this: R, x = polynomial_ring(AcbField(32),"x") f = x^5-x+1 roots(f) How is this done? Is there any discussion about this in the documentation somewhere (I couldn't find anything, but maybe I'm looking in the wrong places), or any references available for the algorithm that is being used? Are there any guarantees that all roots are found? — Reply to this email directly, view it on GitHub <#3106>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AA36CV6Z4H2G3OYLREPRKFLYJMI5NAVCNFSM6AAAAABAVAAUJKVHI2DSMVQWIX3LMV43ERDJONRXK43TNFXW4OZVHE3DAOBQHE> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[thofma]

Just a minor comment (@fieker pointed you already in the right direction). If your input is exact (like a rational polynomial), then I suggest to compute the roots as follows:

julia> Qx, x = QQ["x"]
(Univariate polynomial ring in x over QQ, x)

julia> roots(AcbField(32), x^2 + 1)
2-element Vector{acb}:
 1.000000000*im
 -1.000000000*im

julia> roots(AcbField(32), (x + 1)^2)
1-element Vector{acb}:
 -1.000000000

Because in this case, we can rigorously take care of multiple roots.

This is not that easy if you work with polynomials over inexact fields:

julia> R, x  = AcbField(32)["x"]
(Univariate Polynomial Ring in x over Complex Field with 32 bits of precision and error bounds, x)

julia> roots((x + 1)^2)
ERROR: unable to isolate all roots (insufficient precision, or there is a multiple root)