I would guess that the most general way of going about this would be through the use of [Gröbner bases][1], since you did mention that the root relations you have are algebraic in nature. To use a simple instance, here's how to reconstruct a quadratic polynomial in *Mathematica* from some simple algebraic relations of the roots `a` and `b`:

    GroebnerBasis[{(x - a)(x - b), a + b - 5, a - 3b}, x, {a, b}]

(in English: find the (unique?) quadratic whose roots have a sum of 5 and has one root that is thrice the other)

which returns the polynomial $16x^2-80x+75$ (verify that the roots of this polynomial satisfy the preset conditions).

Of course, as with most algorithms of such generality, I would imagine this to be excruciatingly slow on a problem of even moderate complexity. Exploiting every little bit of structure present in your problem (which you say you have) would certainly help a great deal.

  [1]: http://en.wikipedia.org/wiki/Gr%25C3%25B6bner_basis