Polynomial factorization through Toeplitz matrix computations

The problem of polynomial factorization is translated into the problem of constructing a Wiener-Hopf factorization, and three algorithms,are designed for the solution of the latter problem. These algorithms are based on solving linear systems with large (but finite) circulant and Toeplitz matrices. The algorithms are of low complexity and, perhaps most importantly, they are extremely lucid. An upper bound for the condition number of the problem of polynomial factorization is given in terms of the condition number of a certain Toeplitz matrix. (C) 2003 Elsevier Science Inc. All rights reserved.