Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Facial reduction for exact polynomial sum of squares decomposition


Author: Santiago Laplagne
Journal: Math. Comp. 89 (2020), 859-877
MSC (2010): Primary 14P05, 90C22; Secondary 68W30
DOI: https://doi.org/10.1090/mcom/3476
Published electronically: September 10, 2019
MathSciNet review: 4044453
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: We develop new tools for decomposing a non-negative polynomial as an exact sum of squares (SOS) in the case where the associated semidefinite program is feasible but not strictly feasible (for example if the polynomial has real zeros). Computing symbolically roots of the original polynomial and applying facial reduction techniques, we can solve the problem algebraically or restrict to a subspace where the problem becomes strictly feasible and a numerical approximation can be rounded to an exact solution.

Our motivation for studying this problem is to determine when a rational polynomial that is a sum of squares of polynomials with real coefficients can be written as sum of squares of polynomials with rational coefficients. Applying our new strategy we can answer this question for some previously unknown cases. We first prove that if $ f$ is the sum of two squares with coefficients in an algebraic extension of $ \mathbb{Q}$ of odd degree, then it can always be decomposed as a rational SOS. For the case of more than two polynomials we provide an example of an irreducible polynomial that is the sum of three squares with coefficients in $ \mathbb{Q}(\sqrt [3]{2})$ that cannot be decomposed as a rational SOS.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 14P05, 90C22, 68W30

Retrieve articles in all journals with MSC (2010): 14P05, 90C22, 68W30


Additional Information

Santiago Laplagne
Affiliation: Departamento de Matemática, FCEN, Universidad de Buenos Aires - Ciudad Universitaria, Pabellón I - (C1428EGA) - Buenos Aires, Argentina
Email: slaplagn@dm.uba.ar

DOI: https://doi.org/10.1090/mcom/3476
Received by editor(s): October 17, 2018
Received by editor(s) in revised form: May 22, 2019
Published electronically: September 10, 2019
Article copyright: © Copyright 2019 American Mathematical Society