  We consider the problem of computing exact sums of squares (SOS)
decompositions for certain classes of non-negative multivariate polynomials,
relying on semidefinite programming (SDP) solvers.
  We provide a hybrid numeric-symbolic algorithm computing exact rational SOS
decompositions with rational coefficients for polynomials lying in the interior
of the SOS cone. The first step of this algorithm computes an approximate SOS
decomposition for a perturbation of the input polynomial with an
arbitrary-precision SDP solver. Next, an exact SOS decomposition is obtained
thanks to the perturbation terms and a compensation phenomenon. We prove that
bit complexity estimates on output size and runtime are both singly exponential
in the cardinality of the Newton polytope (or doubly exponential in the number
of variables). Next, we apply this algorithm to compute exact Reznick,
Hilbert-Artin's representation and Putinar's representations respectively for
positive definite forms and positive polynomials over basic compact
semi-algebraic sets. We also report on practical experiments done with the
implementation of these algorithms and existing alternatives such as the
critical point method and cylindrical algebraic decomposition.
