# Factorization of Analytic Functions by means of Koenig's Theorem and Toeplitz Computations

By providing a matrix version of Koenig's theorem we reduce the
problem of evaluating the coefficients of
a monic factor $r(z)$ of degree $h$ of
a power series $f(z)$ to that of approximating
the first $h$ entries in the first row of the inverse of
an infinite Toeplitz matrix in block Hessenberg
form. This matrix is reduced to a band matrix if
$f(z)$ is a polynomial.
We devise a suitable algorithm, based on cyclic reduction and
on the concept of displacement rank, for generating a sequence
of vectors $\B v^{(2^j)}$ that quadratically
converges to the vector $\B v$ having as components the
coefficients of the factor $r(z)$.
In the case of a polynomial $f(z)$ of degree $N$, the cost
of computing the entries of $\B v^{(2^j)}$ given $\B v^{(2^{j-1})}$ is
$O(N\log N+\theta(N))$, where $\theta(N)$ is the cost of solving
an $ N\times N$ Toeplitz-like system.
In the case of analytic functions the cost depends on the numerical
degree of the power series involved in the computation.
The algorithm is strictly related to the Graeffe
method for lifting the roots of a polynomial.
From the numerical experiments performed with several test
polynomials and power series,
the algorithm has shown good numerical
properties and promises to be a
good candidate for implementing polynomial rootfinders based
on recursive splitting