Where are the roots of approximate polynomials? By combining the OM algorithm, cluster pictures, Berkovich skeletons and Brink’s continuity of roots inequality, we produce balls enclosing the roots of all the approximations at a given precision of a given univariate polynomial over a complete field with discrete valuation. Those balls can be presented in an approximate cluster picture or Berkovich skeleton. We present and showcase an algorithm to compute them.

In this paper, we study the connection between the OM-factorization of a polynomial and its cluster pictures, which is a representation of the relative configuration of the roots. Our contribution is threefold, assuming that the residual characteristic is zero or large enough (i.e. the field extension is tame) :(1)We provide and showcase an implementation of the OM algorithms.(2)We make explicit and constructive the connection between the valuative tree of a polynomial, the cluster picture of its roots and the Berkovich skeleton of its roots. As such, we provide a complexity result on the computation of cluster pictures.(3)We elaborate on this connection to provide and showcase an algorithm to compute cluster pictures based on the OM algorithms.

We improve significantly the Nart-Montes algorithm for factoring polynomials over a complete discrete valuation ring A. Our first contribution is to extend the Hensel lemma in the context of generalised Newton polygons, from which we derive a new divide and conquer strategy. Also, if A has residual characteristic zero or high enough, we prove that approximate roots are convenient representatives of types, leading finally to an almost optimal complexity both for irreducibility and factorisation issues, plus the cost of factorisations above the residue field. For instance, to compute an OM-factorisation of F∈A[x], we improve the complexity results of [3] by a factor δ, the discriminant valuation of F.