# 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.

-

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.