Cited By
View all- Telen S(2023)Polynomial Equations: Theory and PracticePolynomial Optimization, Moments, and Applications10.1007/978-3-031-38659-6_8(235-261)Online publication date: 28-Dec-2023
Computing Real Radicals by Moment Optimization
Pages 43 - 50
Abstract
We present a new algorithm for computing the real radical of an ideal I and, more generally, the S-radical of I, which is based on convex moment optimization. A truncated positive generic linear functional σ vanishing on the generators of I is computed solving a Moment Optimization Problem (MOP). We show that, for a large enough degree of truncation, the annihilator of σ generates the real radical of I. We give an effective, general stopping criterion on the degree to detect when the prime ideals lying over the annihilator are real and compute the real radical as the intersection of real prime ideals lying over I.
The method involves several ingredients, that exploit the properties of generic positive moment sequences. A new efficient algorithm is proposed to compute a graded basis of the annihilator of a truncated positive linear functional. We propose a new algorithm to check that an irreducible decomposition of an algebraic variety is real, using a generic real projection to reduce to the hypersurface case. There we apply the Sign Changing Criterion, effectively performed with an exact MOP. Finally we illustrate our approach in some examples.
References
[1]
Michael Artin. 2017. Algebra 2 edizione ed.). Pearson College Div, New York, New York.
[2]
M. F. Atiyah and I. G. MacDonald. 1994. Introduction To Commutative Algebra. Avalon Publishing.
[3]
Lorenzo Baldi and Bernard Mourrain. 2020. Exact Moment Representation in Polynomial Optimization. (2020). https://hal.archives-ouvertes.fr/hal-03082531 preprint.
[4]
Daniel J. Bates, Jonathan D. Haunstein, Andrew J. Sommese, and Charles W. Wampler. 2013. Numerically Solving Polynomial Systems with Bertini. Society for Industrial and Applied Mathematics, USA.
[5]
E. Becker and R. Neuhaus. 1993. Computation of Real Radicals of Polynomial Ideals. In Computational Algebraic Geometry (Progress in Mathematics ), Frédéric Eyssette and André Galligo (Eds.). Birkhäuser, Boston, MA, 1--20. https://doi.org/10.1007/978-1-4612-2752-6_1
[6]
Eberhard Becker and Joachim Schmid. 1999. On the Real Nullstellensatz. In Algorithmic Algebra and Number Theory, B. Heinrich Matzat, Gert-Martin Greuel, and Gerhard Hiss (Eds.). Springer, Berlin, Heidelberg, 173--185. https://doi.org/10.1007/978-3-642-59932-3_9
[7]
Cristina Blanco, Gabriela Jeronimo, and Pablo Solernó. 2004. Computing generators of the ideal of a smooth affine algebraic variety. Journal of Symbolic Computation, Vol. 38, 1 (2004), 843--872.
[8]
Jacek Bochnak, Michel Coste, and Marie-Francoise Roy. 1998. Real Algebraic Geometry. Springer-Verlag, Berlin Heidelberg.
[9]
Alin Bostan, Frédéric Chyzak, Marc Giusti, Romain Lebreton, Grégoire Lecerf, Bruno Salvy, and Éric Schost. 2017. Algorithmes Efficaces en Calcul Formel 1° edizione ed.). Frédéric Chyzak.
[10]
Daniel A. Brake, Jonathan D. Hauenstein, and Alan C. Liddell. 2016a. Validating the Completeness of the Real Solution Set of a System of Polynomial Equations. In Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation. ACM, Waterloo ON Canada, 143--150. https://doi.org/10.1145/2930889.2930910
[11]
Daniel A. Brake, Jonathan D. Hauenstein, and Alan C. Liddell. 2016b. Validating the Completeness of the Real Solution Set of a System of Polynomial Equations. In Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (ISSAC '16). Association for Computing Machinery, New York, NY, USA, 143--150.
[12]
Changbo Chen, James H. Davenport, John P. May, Marc Moreno Maza, Bican Xia, and Rong Xiao. 2013. Triangular Decomposition of Semi-Algebraic Systems. Journal of Symbolic Computation, Vol. 49 (Feb. 2013), 3--26. https://doi.org/10.1016/j.jsc.2011.12.014
[13]
David A. Cox, John B. Little, and Donal O'Shea. 2015. Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra fourth edition ed.). Springer, Cham Heidelberg New York Dordrecht London.
[14]
Raúl E. Curto and Lawrence A. Fialkow. 1998. Flat Extensions of Positive Moment Matrices: Recursively Generated Relations. American Mathematical Soc.
[15]
A. Galligo and N. Vorobjov. 1995. Complexity of Finding Irreducible Components of a Semialgebraic Set. Journal of Complexity, Vol. 11, 1 (March 1995), 174--193. https://doi.org/10.1006/jcom.1995.1007
[16]
Jonathan D. Hauenstein, Andrew J. Sommese, and Charles W. Wampler. 2011. Regenerative Cascade Homotopies for Solving Polynomial Systems. Appl. Math. Comput., Vol. 218, 4 (2011), 1240--1246.
[17]
Jean-Louis Krivine. 1964. Anneaux préordonnés. Journal d'analyse mathématique, Vol. 12 (1964), p. 307--326.
[18]
Robert Krone and Anton Leykin. 2017. Numerical Algorithms for Detecting Embedded Components. Journal of Symbolic Computation, Vol. 82 (2017), 1--18.
[19]
Jean B. Lasserre. 2001. Global Optimization with Polynomials and the Problem of Moments. SIAM Journal on Optimization, Vol. 11, 3 (2001), 796--817.
[20]
Jean-Bernard Lasserre, Monique Laurent, Bernard Mourrain, Philipp Rostalski, and Philippe Trébuchet. 2013. Moment matrices, border bases and real radical computation. Journal of Symbolic Computation, Vol. 51 (2013), 63--85.
[21]
Jean Bernard Lasserre, Monique Laurent, and Philipp Rostalski. 2008. Semidefinite Characterization and Computation of Zero-Dimensional Real Radical Ideals. Foundations of Computational Mathematics, Vol. 8, 5 (2008), 607--647.
[22]
Monique Laurent and Bernard Mourrain. 2009. A Generalized Flat Extension Theorem for Moment Matrices. Archiv der Mathematik, Vol. 93, 1 (2009), 87--98.
[23]
Monique Laurent and Philipp Rostalski. 2012. The Approach of Moments for Polynomial Equations. In Handbook on Semidefinite, Conic and Polynomial Optimization, Miguel F. Anjos and Jean B. Lasserre (Eds.). Springer US, Boston, MA, 25--60. https://doi.org/10.1007/978-1-4614-0769-0_2
[24]
Grégoire Lecerf. 2003. Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers. Journal of Complexity, Vol. 19, 4 (2003), 564--596.
[25]
Yue Ma, Chu Wang, and Lihong Zhi. 2016. A Certificate for Semidefinite Relaxations in Computing Positive-Dimensional Real Radical Ideals. Journal of Symbolic Computation, Vol. 72 (2016), 1--20. https://doi.org/10.1016/j.jsc.2014.12.002
[26]
Murray Marshall. 2008. Positive Polynomials and Sums of Squares. American Mathematical Soc.
[27]
Bernard Mourrain. 2017. Fast algorithm for border bases of Artinian Gorenstein algebras. In ISSAC'17 -- International Symposium on Symbolic and Algebraic Computation. ACM New York, NY, USA, Kaiserslautern, Germany, 333--340.
[28]
Bernard Mourrain. 2018. Polynomial--Exponential Decomposition From Moments. Foundations of Computational Mathematics, Vol. 18, 6 (2018), 1435--1492.
[29]
Rolf Neuhaus. 1998. Computation of Real Radicals of Polynomial Ideals textemdash II. Journal of Pure and Applied Algebra, Vol. 124, 1--3 (Feb. 1998), 261--280. https://doi.org/10.1016/S0022--4049(96)00103-X
[30]
Philipp Rostalski. 2009. Algebraic moments: real root finding and related topics. Doctoral Thesis. ETH Zurich. Accepted: 2017-06--13T08:51:18Z.
[31]
Marie-Francoise Roy and Nicolai Vorobjov. 2002. The Complexification and Degree of a Semi-Algebraic Set. Mathematische Zeitschrift, Vol. 239 (2002), 131--142.
[32]
Mohab Safey El Din, Zhi-Hong Yang, and Lihong Zhi. 2021. Computing Real Radicals and S -Radicals of Polynomial Systems. Journal of Symbolic Computation, Vol. 102 (2021), 259--278. https://doi.org/10.1016/j.jsc.2019.10.018
[33]
Yoshiyuki Sekiguchi, Tomoyuki Takenawa, and Hayato Waki. 2013. Real Ideal and the Duality of Semidefinite Programming for Polynomial Optimization. Japan Journal of Industrial and Applied Mathematics, Vol. 30, 2 (2013), 321--330. https://doi.org/10.1007/s13160-013-0104-6
[34]
Igor R. Shafarevich. 2013. Basic Algebraic Geometry 1: Varieties in Projective Space 3 ed.). Springer-Verlag, Berlin Heidelberg.
[35]
Andrew J. Sommese, Jan Verschelde, and Charles W. Wampler. 2001. Numerical Decomposition of the Solution Sets of Polynomial Systems into Irreducible Components. SIAM J. Numer. Anal., Vol. 38, 6 (2001), 2022--2046.
[36]
Silke J Spang. 2008. A Zero-Dimensional Approach to Compute Real Radicals. Computer Science Journal of Moldova, Vol. 16, 1 (2008), 64--92.
[37]
Gilbert Stengle. 1974. A Nullstellensatz and a Positivstellensatz in Semialgebraic Geometry. Math. Ann., Vol. 207, 2 (1974), 87--97.
[38]
Lloyd N. Trefethen and David Bau. 1997. Numerical Linear Algebra. SIAM.
[39]
Bican Xia and Lu Yang. 2002. An Algorithm for Isolating the Real Solutions of Semi -Algebraic Systems. Journal of Symbolic Computation, Vol. 34, 5 (Nov. 2002), 461--477. https://doi.org/10.1006/jsco.2002.0572
Index Terms
- Computing Real Radicals by Moment Optimization
Recommendations
On the Complexity of Computing Real Radicals of Polynomial Systems
ISSAC '18: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic ComputationLet f= (f1, ..., fs) be a sequence of polynomials in Q[X1,...,Xn] of maximal degree D and V⊂ Cn be the algebraic set defined by f and r be its dimension. The real radical re < f > associated to f is the largest ideal which defines the real trace of V . ...
Quadratures with multiple nodes, power orthogonality, and moment-preserving spline approximation
Special issue on numerical analysis 2000 Vol. V: quadrature and orthogonal polynomialsImplicit Moment Invariants
The use of traditional moment invariants in object recognition is limited to simple geometric transforms, such as rotation, scaling and affine transformation of the image. This paper introduces so-called implicit moment invariants. Implicit invariants ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2021
379 pages
Copyright © 2021 ACM.
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 the author(s) 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].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 18 July 2021
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- POEMA
Conference
ISSAC '21
Sponsor:
ISSAC '21: International Symposium on Symbolic and Algebraic Computation
July 18 - 23, 2021
Virtual Event, Russian Federation
Acceptance Rates
Overall Acceptance Rate 395 of 838 submissions, 47%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 72Total Downloads
- Downloads (Last 12 months)12
- Downloads (Last 6 weeks)4
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
Cited By
View all- Telen S(2023)Polynomial Equations: Theory and PracticePolynomial Optimization, Moments, and Applications10.1007/978-3-031-38659-6_8(235-261)Online publication date: 28-Dec-2023
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in