Narrow Results

This paper develops optimal family of fourth-order iterative techniques in order to find a single root and to generalize them for simultaneous finding of all roots of polynomial equation. Convergence study reveals that for single root finding methods, its optimal convergence order is 4, while for simultaneous methods, it is 12. Computational cost and numerical illustrations demonstrate that the newly developed family of methods outperformed the previous methods available in the literature.

We study functions of the roots of an integer polynomial $p=p(x)$ with $m\ge 2$ distinct roots $\rho =({\rho }_1,\dots ,{\rho }_m)$ of multiplicity $\mu =({\mu }_1,\dots ,{\mu }_m)$, ${\mu }_1\ge \cdots \ge {\mu }_m\ge 1$. Traditionally, root functions are studied via the theory of symmetric polynomials; we generalize this theory to $\mu$-symmetric polynomials. We initiate the study of the vector space of $\mu$-symmetric polynomials of a given degree $\delta$ via the concepts of $\mu$-gist and $\mu$-ideal. In particular, we are interested in the root $D_{\mu }^{+}(r_1,\dots ,r_m):={\prod }_{1\le i<j\le m}{(r_i-r_j)}^{{\mu }_i+{\mu }_j}$. The D-plus discriminant of $p$ is $D^{+}(p):=D_{\mu }^{+}({\rho }_1,\dots ,{\rho }_m)$. This quantity appears in the complexity analysis of the root clustering algorithm of Becker et al. (ISSAC 2016). We conjecture that $D_{\mu }^{+}(r_1,\dots ,r_m)$ is $\mu$-symmetric, which implies $D^{+}(p)$ is rational. To explore this conjecture experimentally, we introduce algorithms for checking if a given root function is $\mu$-symmetric. We design three such algorithms: one based on Gröbner bases, another based on canonical bases and reduction, and the third based on solving linear equations. Each of these algorithms has variants that depend on the choice of a basis for the $\mu$-symmetric functions. We implement these algorithms (and their variants) in Maple and experiments show that the latter two algorithms are significantly faster than the first.