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