I would guess that the most general way of going about this would be through the use of Gröbner bases, 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.