A certificate for semidefinite relaxations in computing positive-dimensional real radical ideals

DOI10.1016/J.JSC.2014.12.002zbMATH Open1444.13036arXiv1212.4924OpenAlexW2592191094MaRDI QIDQ492020FDOQ492020

Yue Ma, Chu Wang, Lihong Zhi

Publication date: 19 August 2015

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: For an ideal I with a positive dimensional real variety, based on moment relaxations, we study how to compute a Pommaret basis which is simultaneously a Groebner basis of an ideal J generated by the kernel of a truncated moment matrix and nesting between I and its real radical ideal. We provide a certificate consisting of a condition on coranks of moment matrices for terminating the algorithm. For a generic delta-regular coordinate system, we prove that the condition is satisfiable in a large enough order of moment relaxations.

Full work available at URL: https://arxiv.org/abs/1212.4924

Recommendations

• Semidefinite characterization and computation of zero-dimensional real radical ideals
• Computation of generalized real radicals of polynomial ideals
• Moment matrices, border bases and real radical computation
• scientific article; zbMATH DE number 833249
• Computing real radicals and \(S\)-radicals of polynomial systems

zbMATH Keywords

semidefinite programming\(\delta\)-regularinvolutive divisionPommaret basispositive-dimensional idealreal radical ideal

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Semidefinite programming (90C22) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Solving polynomial systems; resultants (13P15)

Cites Work

• Title not available (Why is that?)
• Semidefinite Programming
• GloptiPoly
• A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
• Sums of squares, moment matrices and optimization over polynomials
• Handbook of semidefinite programming. Theory, algorithms, and applications
• Involution. The formal theory of differential equations and its applications in computer algebra
• Semidefinite characterization and computation of zero-dimensional real radical ideals
• Gröbner bases and primary decomposition of polynomial ideals
• Computation of real radicals of polynomial ideals. II
• Moment matrices, border bases and real radical computation
• Title not available (Why is that?)
• Numerical Polynomial Algebra
• Solution of the truncated complex moment problem for flat data
• Revisiting two theorems of Curto and Fialkow on moment matrices
• Title not available (Why is that?)
• An algorithm for isolating the real solutions of semi-algebraic systems
• Title not available (Why is that?)
• On computing a set of points meeting every cell defined by a family of polynomials on a variety
• Title not available (Why is that?)
• Title not available (Why is that?)
• Real solving for positive dimensional systems.
• Polar varieties and efficient real elimination
• Regularity of ideals and their radicals
• Solving polynomial systems via symbolic-numeric reduction to geometric involutive form
• Radical computations of zero-dimensional ideals and real root counting.
• A prolongation-projection algorithm for computing the finite real variety of an ideal
• Computation of generalized real radicals of polynomial ideals
• On the complexity of the real Nullstellensatz in the 0-dimensional case
• Solution of the truncated moment problem with variety 𝑦=𝑥³
• Geometric Involutive Bases and Applications to Approximate Commutative Algebra
• A unified approach to computing real and complex zeros of zero-dimensional ideals
• On the computation of matrices of traces and radicals of ideals

Cited In (5)

• Voronoi cells of varieties
• Smooth points on semi-algebraic sets
• Generators for the \(C^m\)-closures of ideals
• Computing real radicals and \(S\)-radicals of polynomial systems
• Computing real radicals by moment optimization

Uses Software

• SINGULAR
• SeDuMi
• GloptiPoly
• realrad.lib

This page was built for publication: A certificate for semidefinite relaxations in computing positive-dimensional real radical ideals

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