Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.

  

Computing sum of squares decompositions with rational coefficients

Author(s):

H. Peyrl, P.A. Parrilo
Conference/Journal:

Theoretical Computer Science, vol. 409, no. 2, pp. 269-281
Abstract:

Sum of squares (SOS) decompositions for nonnegative polynomials are usually computed numerically, using convex optimization solvers. Although the underlying floating point methods in principle allow for numerical approximations of arbitrary precision, the computed solutions will never be exact. In many applications such as geometric theorem proving, it is of interest to obtain solutions that can be exactly verified. In this paper we present a numeric-symbolic method that exploits the efficiency of numerical techniques to obtain an approximate solution, which is then used as a starting point for the computation of an exact rational result. We show that under a strict feasibility assumption, an approximate solution of the semidefinite program is sufficient to obtain a rational decomposition, and quantify the relation between the numerical error versus the rounding tolerance needed. Furthermore, we present an implementation of our method for the computer algebra system Macaulay 2.

Year:

2008
Type of Publication:

(01)Article
Supervisor:



File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@Article { PeyPar:2008:IFA_3087,
    author={H. Peyrl and P.A. Parrilo},
    title={{Computing sum of squares decompositions with rational
	  coefficients}},
    journal={Theoretical Computer Science},
    year={2008},
    volume={409},
    number={2},
    pages={269--281},
    month=dec,
    url={http://control.ee.ethz.ch/index.cgi?page=publications;action=details;id=3087}
}
Permanent link