Polynomial factorization through Toeplitz matrix computations (Q1874656)

The authors consider a polynomial of the form \[ p(z)=p_0+p_1z+\dots+p_{n-1}z^{n-1}+z^n (p_0 \neq 0) \] for which it is known that there are \(m\geq 1\) zeros in \(\{z\in \mathbb{C}:|z|<r<1\}\) and \(n-m\) zeros in \(\{z\in \mathbb{C}:|z|>R>1\}\) and it is assumed (without loss of generality) that \(m\geq n-m\). The factorization problem is to decompose \(p(z)\) as a product \(p(z)=v(z)l(z)\) of two monic polynomials with degrees \(m\) and \(n-m\) respectively that have precisely the former and the latter sets of zeros. It is well-known that this problem is equivalent to the construction of a Wiener-Hopf factorization of the Laurent polynomial \(z^{-m}p(z)\) which in turn can be related to a problem in Toeplitz matrices. The present paper is an elaboration of this idea. The authors show three simple ways to translate the problem of polynomial factorization into problems on the inversion of infinite matrices. The latter problems are solved by the finite bisection method. They also obtain an upper bound for the condition number of the problem of polynomial factorization in terms of the condition number of a certain Toeplitz matrix. The paper contains a numerical example as well.