MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
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. – David Speyer Jul 26 '13 at 14:41
@DavidSpeyer: What IS the multivariate problem? Do you have a zero-dimensional variety, or?! – Igor Rivin Jul 26 '13 at 18:45

Take a look at -- 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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