Counting the number of roots of a polynomial in each quadrant of the complex plane I'm looking to answer the question:

Given a polynomial of a single variable $x$:   $\sum_n a_n x^n = 0 $, how many roots are there in each quadrant of
  the complex plane, counting positive/negative real/imaginary lines seperately?

I don't want to solve this numerically if I don't have to. This seems to me like it would be an ideal application of some kind of abstract algebra, except I don't know any? Can someone point me to a field which studies this problem - if it exists? How hard is this problem to solve?
On Wikipedia I've found Real Root Isolation, Descarte's Rule of Signs, and Sturm's Theorem. The one problem I have with Sturm's theorem is that I would like to find simple criteria, that can be worked out on paper, but this would seem to require a computer.  Is there anything else that would help me solve this problem?
 A: A slight variation of your problem: counting real roots of polynomial systems using tools from algebraic geometry, is a problem that is very much studied in Nonlinear Algebra. This is an important question as many applications only care about real solutions. So yes, in fact, there is an "Ideal application" here (ha ha).
The short answer to "how hard is this problem" is "very," but there definitely exist tools and a wide range of work regarding this topic. A good reference might be, Real solutions to equations from geometry by Frank Sottile, which examines the univariate case in Chapter Two.
One can also think about dividing the real parameter space $(a_0, ... ,a_n)$ into regions with a certain number of real roots by exploiting the fact that the number of real roots changes when two complex roots come together (forming a multiple root). The value of the discriminant of a univariate polynomial encodes some of this information, since it is zero exactly when a univariate polynomial has a multiple root. When the degree is four or higher, the discriminant is positive if and only if the number of non-real roots is a multiple of four.
You wanted to avoid numerical solvers, but I will mention that numerical solvers such as Bertini exist for polynomial systems which take advantage of the polynomial structure to find roots (and thus classify them).
As for classifying roots in other quadrants of the complex plane, I'm not entirely sure, but it's a very interesting one. One might be able to take advantage of the work on counting real solutions. For example, if one appends the equation $x^2-y=0$, one can then ask how many real solutions in $y$ are there, giving the count of purely imaginary plus real solutions.
