  The problem of computing a representation for a real polynomial as a sum of
minimum number of squares of polynomials can be casted as finding a symmetric
positive semidefinite real matrix (Gram matrix) of minimum rank subject to
linear equality constraints.
  In this paper, we propose algorithms for solving the minimum-rank Gram matrix
completion problem, and show the convergence of these algorithms. Our methods
are based on the modified fixed point continuation (FPC) method. We also use
the Barzilai-Borwein (BB) technique and a specific linear combination of two
previous iterates to accelerate the convergence of modified FPC algorithms. We
demonstrate the effectiveness of our algorithms for computing approximate and
exact rational sum of squares (SOS) decompositions of polynomials with rational
coefficients.
