Approximate gcds of polynomials and sparse SOS relaxations

DOI10.1016/J.TCS.2008.09.003MaRDI QIDQ2378493zbMATH OpenOpenAlexFDO

Authors Bin Li, Lihong Zhi, Jiawang Nie

Publication date 8 January 2009

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2008.09.003

zbMATH Keywords

global minimizationgreatest common divisorsemidefinite programmingsums of squares

Mathematics Subject Classification ID

Computational aspects and applications of commutative rings (13P99) Semialgebraic sets and related spaces (14P10) Symbolic computation and algebraic computation (68W30) Semidefinite programming (90C22)

Recommendations

• Approximate polynomial GCD by approximate syzygies
• Approximate polynomial GCD.
• scientific article; zbMATH DE number 1262453
• An algorithm for computing certified approximate GCD of n univariate polynomials
• Computation of approximate polynomial GCDs and an extension

Cites work

• Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials
• Class of global minimum bounds of polynomial functions
• Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
• Detecting Global Optimality and Extracting Solutions in GloptiPoly
• Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars
• Extremal psd forms with few terms
• Global minimization of rational functions and the nearest GCDs
• Global optimization of rational functions: a semidefinite programming approach
• Global optimization with polynomials and the problem of moments
• Handbook of semidefinite programming. Theory, algorithms, and applications
• scientific article; zbMATH DE number 1253975 (Why is no real title available?)
• scientific article; zbMATH DE number 1254271 (Why is no real title available?)
• scientific article; zbMATH DE number 1262453 (Why is no real title available?)
• scientific article; zbMATH DE number 1262454 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 1984325 (Why is no real title available?)
• Hybrid method for computing the nearest singular polynomials
• Modified \(r\)-algorithm to find the global minimum of polynomial functions
• Nearest singular polynomials
• On approximate GCDs of univariate polynomials
• Semidefinite Programming
• Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials
• Sparsity in sums of squares of polynomials
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones

Cited in

(12)

• Approximate polynomial GCD by approximate syzygies
• Approximate square-free part and decomposition
• Variable projection methods for approximate (greatest) common divisor computations
• An ODE-based method for computing the approximate greatest common divisor of polynomials
• Global minimization of rational functions and the nearest GCDs
• Computation of the nearest non-prime polynomial matrix: structured low-rank approximation approach
• Irreducibility and greatest common divisor algorithms for sparse polynomials
• Exact certification in global polynomial optimization via rationalizing sums-of-squares
• A heuristic verification of the degree of the approximate GCD of two univariate polynomials
• Overdetermined Weierstrass iteration and the nearest consistent system
• A complete algorithm to find exact minimal polynomial by approximations
• Relaxed NewtonSLRA for approximate GCD

Describes a project that uses

Uses Software

• Sostools
• SeDuMi
• GloptiPoly
• YALMIP

This page was built for publication: Approximate gcds of polynomials and sparse SOS relaxations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2378493)