Article

A Macaulay 2 package for computing sum of squares decompositions of polynomials with rational coefficients

Authors:

Helfried Peyrl,

Pablo A. ParriloAuthors Info & Claims

SNC '07: Proceedings of the 2007 international workshop on Symbolic-numeric computation

Pages 207 - 208

https://doi.org/10.1145/1277500.1277534

Published: 25 July 2007 Publication History

Get Access

Abstract

In recent years semideffinite programming (SDP) has become the standard technique for computing sum of squares (SOS) decompositions of nonnegative polynomials. Due to the nature of the underlying methods, the solutions are computed numerically, and thus are never exact. In this paper we present a software package for Macaulay 2, which aims at computing an exact SOS decomposition from a numerical solution.

References

[1]

M. D. Choi, T. Y. Lam, and B. Reznick. Sums of squares of real polynomials. In K-theory and algebraic geometry: connections with quadratic forms and division algebras, volume 58 of Proc. Sympos. Pure Math., pages 103--126. Amer. Math. Soc., Providence, RI, 1995.

Google Scholar

[2]

G. Golub and C. van Loan. Matrix Computations, chapter 4, pages 133--148. Johns Hopkins Series in the Mathematical Sciences. The Johns Hopkins University Press, Baltimore Maryland, 2nd edition, 1989.

Google Scholar

[3]

D. R. Grayson and M. E. Stillman. Macaulay 2, a software system for research in algebraic geometry. Available at http://www.math.uiuc.edu/Macaulay2/

Google Scholar

[4]

E. Landau. Über die Darstellung de niter Funktionen als Summe von Quadraten. Math. Ann., 62:290--329, 1906.

Crossref

Google Scholar

[5]

P. A. Parrilo. Structured Semide nite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology, 2000.

Google Scholar

[6]

H. Peyrl and P. A. Parrilo. SOS.m2, a sum of squares package for Macaulay 2. Available at decompo-http://www.control.ee.ethz.ch/~hpeyrl 2007.

Google Scholar

[7]

B. Reznick. Some concrete aspects of Hilbert's 17th problem. In Real algebraic geometry and ordered structures, volume 253 of Contemporary Mathematics, pages 251--272. Amer. Math. Soc., Providence, RI, 2000.

Google Scholar

[8]

M. Schweighofer. Algorithmische Beweise für Nichtnegativ-und Positivstellensätze.Master's thesis, Universität Passau, 1999.

Google Scholar

[9]

N. Z. Shor. Class of global minimum bounds of polynomial functions. Cybernetics, 23(6):731--734, 1987.

Crossref

Google Scholar

[10]

L. Vandenberghe and S. Boyd. Semideffinite programming. SIAM Review, 38(1):49--95, March 1996.

Digital Library

Google Scholar

Cited By

View all

Ma YZhi LSchost ÉEmiris I(2011)The minimum-rank gram matrix completion via modified fixed point continuation methodProceedings of the 36th international symposium on Symbolic and algebraic computation10.1145/1993886.1993924(241-248)Online publication date: 8-Jun-2011
https://dl.acm.org/doi/10.1145/1993886.1993924
Kaltofen EYang ZZhi LSasaki TShirayanagi KKotsireas I(2009)A proof of the monotone column permanent (MCP) conjecture for dimension 4 via sums-of-squares of rational functionsProceedings of the 2009 conference on Symbolic numeric computation10.1145/1577190.1577204(65-70)Online publication date: 3-Aug-2009
https://dl.acm.org/doi/10.1145/1577190.1577204
Kaltofen ELi BYang ZZhi LSendra JGonzalez-Vega L(2008)Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalarsProceedings of the twenty-first international symposium on Symbolic and algebraic computation10.1145/1390768.1390792(155-164)Online publication date: 20-Jul-2008
https://dl.acm.org/doi/10.1145/1390768.1390792

Index Terms

A Macaulay 2 package for computing sum of squares decompositions of polynomials with rational coefficients

Recommendations

Computing sum of squares decompositions with rational coefficients

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, ...
An algorithm for decomposing a non-negative polynomial as a sum of squares of rational functions

This paper presents an algorithm for computing a decomposition of a non-negative real polynomial as a sum of squares of rational functions. Rational functions in our algorithm have the denominators that are powers of the sum of squares of coordinate ...
Computing recurrence coefficients of multiple orthogonal polynomials

Multiple orthogonal polynomials satisfy a number of recurrence relations, in particular there is a (r+2)-term recurrence relation connecting the type II multiple orthogonal polynomials near the diagonal (the so-called step-line recurrence relation) and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SNC '07: Proceedings of the 2007 international workshop on Symbolic-numeric computation

July 2007

218 pages

ISBN:9781595937445

DOI:10.1145/1277500

General Chair:
Stephen M. Watt
The University of Western Ontario, Canada
,
Program Chair:
Jan Verschelde
University of Chicago at Illinois

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISSAC07

Sponsor:

ISSAC07: International Symposium on Symbolic and Algebraic Computation

July 25 - 27, 2007

Ontario, London, Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
233
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ma YZhi LSchost ÉEmiris I(2011)The minimum-rank gram matrix completion via modified fixed point continuation methodProceedings of the 36th international symposium on Symbolic and algebraic computation10.1145/1993886.1993924(241-248)Online publication date: 8-Jun-2011
https://dl.acm.org/doi/10.1145/1993886.1993924
Kaltofen EYang ZZhi LSasaki TShirayanagi KKotsireas I(2009)A proof of the monotone column permanent (MCP) conjecture for dimension 4 via sums-of-squares of rational functionsProceedings of the 2009 conference on Symbolic numeric computation10.1145/1577190.1577204(65-70)Online publication date: 3-Aug-2009
https://dl.acm.org/doi/10.1145/1577190.1577204
Kaltofen ELi BYang ZZhi LSendra JGonzalez-Vega L(2008)Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalarsProceedings of the twenty-first international symposium on Symbolic and algebraic computation10.1145/1390768.1390792(155-164)Online publication date: 20-Jul-2008
https://dl.acm.org/doi/10.1145/1390768.1390792

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Computing sum of squares decompositions with rational coefficients

An algorithm for decomposing a non-negative polynomial as a sum of squares of rational functions

Computing recurrence coefficients of multiple orthogonal polynomials