ETD

• Cyclic Reduction
• Evaluation/Interpolation
• Graeffe
• matrix polynomials
• Newton method
• spectral factorization
• Wiener-Hopf factorization

In this Master Thesis we have considered the problem related to the Wiener-Hopf factorization, both for scalar and matrix polynomials. We have studied it from a numerical point of view and we have compared many different algorithms that, until now, were scattered in many papers.
After a theoretical introduction where we discuss the existence of the solutions, we consider the known algorithms to solve these problems. The aim of this work is providing a self contained presentation of the theory and a description of the available algorithms with a comparative implementation. We want to understand whether there exists the very ``best'' algorithm or at least in which settings each algorithm provides the best performance. As the reader may imagine the answer of the first question is negative. However we have been able to find when one algorithm is better than the others. For example, in the scalar case the Graeffe iteration and the algorithms based on the evaluation/interpolation technique are much faster than their competitors when the roots of the polynomial b(z) do not lie too near the unit circle, while they fail (or their precision drops) when this latter condition does not hold. On the other hand, algorithms based on the classical Newton method are more robust, therefore they are suited for this situation.
Moreover we propose another suitable starting vector for the Newton iteration, which generally provides a faster convergence. In most cases, with this new vector, the Newton iteration requires a smaller number of steps, even though there are rare cases where the convergence is slightly slower.
A more detailed abstract is presented at hte beginning of the thesis.