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.



Finding a low-degree polynomial vanishing on half the zeroes of a polynomial system
As @Federico notes (but does not say explicitly), the magic words are "spectral factorization" -- for an algorithm see [here.](https://www.evernote.com/shard/s24/sh/ba0b0a31-e398-41c7-a5a0-66e50b9554cd/3a98723085e004097be0ed22a5dfdda9) 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.


