Let $f(x)$ be a real polynomial of degree $2d$ without real roots. Let the complex roots be $z_1$, $\bar{z_1}$, $z_2$, $\bar{z_2}$, ..., $z_d$, $\bar{z_d}$ with $z_i$ in the upper half plane. Let $g(x) = \prod(x-z_i)$, a complex polynomial of degree $d$. Is there a way to compute the coefficients of $g$ which is better than finding the roots of $f$?

That was a simpler version of what I actually want. My actual problem is in two variables: Let $f_1(x,y)$ and $f_2(x,y)$ be real polynomials of degree $m$ and $n$, with all the roots of $f_1=f_2=0$ isolated and nonreal. Let $p_1$, $\bar{p}_1$, ..., $p_{mn/2}$, $\bar{p}_{mn/2}$ be the roots of $f_1=f_2=0$, with the $y$-coordinates of the $p_i$ in the upper half plane. I want to compute a basis for the vector space of degree $d$ complex polynomials in $(x,y)$ which vanish on the $p_i$. Again, is there a method which is better than finding the $p_i$?

In both cases, it is an easy Galois theory exercise to show that there is no solution is radicals, so the question is about numerical methods.


As @Federico notes (but does not say explicitly), the magic words are "spectral factorization" -- for an algorithm see here. I should say that it is very far from clear to what extent the fancy algorithms are better than just factoring the polynomial, it probably depends on many things.

  • $\begingroup$ Thanks for telling me the magic words; I now have a pile of papers to read. Any idea about the multivariate problem? I can reduce it to a single variable by taking resultants, but this seems like a terrible idea. $\endgroup$ – David E Speyer Jul 26 '13 at 14:41
  • $\begingroup$ @DavidSpeyer: What IS the multivariate problem? Do you have a zero-dimensional variety, or?! $\endgroup$ – Igor Rivin Jul 26 '13 at 18:45

Take a look at https://www.sciencedirect.com/science/article/pii/S0024379513001511?np=y -- they treat factorizations with roots inside/outside the unit circle, but it's essentially the same problem up to a Cayley transform. I have no direct experience of this problem in the scalar case, but I guess this method is more efficient than computing all the roots.

The analogous problem for matrices is also well studied: given a matrix (or a matrix polynomial) with $n$ eigenvalues in the left half-plane and $m$ in the right one, find the invariant subspace spanned by the eigenvectors relative to those in the left (or the right) half-plane. This problem is related to the matrix sign function and to algebraic Riccati equations. In that context, there are much better methods than diagonalizing the matrix.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.