Enhancing the Power of Cardinal's Algorithm
For researchers in polynomial root-finding and matrix computations, this work makes Cardinal's algorithm practically viable after two decades of being theoretically recognized but computationally infeasible.
The paper addresses the high computational cost of Cardinal's polynomial factorization algorithm by reducing its final stage to manageable computations with structured matrices, enabling practical splitting of factors with root sets separated by the imaginary axis.
Cardinal's factorization algorithm of 1996 splits a univariate polynomial into two factors with root sets separated by the imaginary axis, which is an important goal itself and a basic step toward root-finding. The novelty of the algorithm and its potential power have been well recognized by experts immediately, but by 2016, that is, two decades later, its practical value still remains nil, particularly because of the high computational cost of performing its final stage by means of computing approximate greatest common divisor of two polynomials. We briefly recall Cardinal's algorithm and its difficulties, amend it based on some works performed since 1996, extend its power to splitting out factors of a more general class, and reduce the final stage of the algorithm to quite manageable computations with structured matrices. Some of our techniques can be of independent interest for matrix computations.