Finding a low-degree polynomial vanishing on half the zeroes of a polynomial system 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.
 A: 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.
A: 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.
