Newton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. We generalize it to a matrix recurrence (allRootsNI) that approximates all the roots simultaneously. In this form, the process yields a better circuit complexity in the case when the ... more >>>

The orbit of an n-variate polynomial f(\mathbf{x}) over a field \mathbb{F} is the set \{f(A \mathbf{x} + b)\,\mid\, A\in \mathrm{GL}({n,\mathbb{F}})\mbox{ and }\mathbf{b} \in \mathbb{F}^n\}, and the orbit of a polynomial class is the union of orbits of all the polynomials in it. In this paper, we give improved constructions of ... more >>>