Acceleration of Newton’s Polynomial Factorization: Army of Constraints, Convolution, Sylvester Matrices, and Partial Fraction Decomposition ∗

We try to arm Newton’s iteration for univariate polynomial factoriza-tion with greater convergence power by shifting to a larger basic system of multivariate constraints. The convolution equation is a natural means for a desired expansion of the basis for this iteration versus the classi-cal univariate method, which is more vulnerable to foreign distractions from its convergence course. Compared to Viete’s equations, the convolu-tion equation directs the Newton’s root-finding iteration to factorization (which is a task of independent interest) and enables approximation of a single root. Combining convolution with partial fraction decomposition (PFD) yields even a greater army of constraints. By linking PFD with Sylvester and generalized Sylvester matrices we extend to their inverses the celebrated formula by Gohberg and Semencul for Toeplitz matrix in-version. Furthermore, we accelerate the solution of Sylvester and gener-alized Sylvester linear systems in the important case where all but one of the basic polynomials defining the matrix have small degrees. This enables us to speed up Newton’s convolution steps