For polynomials, non negativity can be verified by using semidefinite programming (this is theoretically fast [polynomial time], practically, not the fastest thing you had ever done. done.) There are many references, see for example, Nemirovsky's very nice notes on convex optimization, or this reference.
The non negativity of polynomials can also be related to the Fejer-Riesz theorem (which deals with trigonometric polynomials on the unit circle), there are fast approximate algorithms based on signal processing techniques.
