research-article

On the Complexity of Computing Real Radicals of Polynomial Systems

Authors:

Mohab Safey El Din,

Lihong ZhiAuthors Info & Claims

ISSAC '18: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation

Pages 351 - 358

https://doi.org/10.1145/3208976.3209002

Published: 11 July 2018 Publication History

Abstract

Let f= (f₁, ..., f_s) be a sequence of polynomials in Q[X₁,...,X_n] of maximal degree D and V⊂ Cⁿ 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 . When V is smooth, we show that re < f >, has a finite set of generators with degrees bounded by V. Moreover, we present a probabilistic algorithm of complexity (snDⁿ )^O(1) to compute the minimal primes of re < f >. When V is not smooth, we give a probabilistic algorithm of complexity s^O(1) (nD)^{O(nr2^r)} to compute rational parametrizations for all irreducible components of the real algebraic set V ∩ Rⁿ. Experiments are given to show the efficiency of our approaches.

References

[1]

Basu, S., Pollack, R., Roy, M.-F., 2006. Algorithms in Real Algebraic Geometry. Springer Berlin Heidelberg, Berlin, Heidelberg.

Digital Library

[2]

Becker, E., Neuhaus, R., 1993. Computation of real radicals of polynomial ideals. In: Eyssette, F., Galligo, A. (Eds.), Computational Algebraic Geometry. Vol. 109. Birkhauser, Boston, MA, pp. 1--20.

[3]

Blanco, C., Jeronimo, G., Solernó, P., 2004. Computing generators of the ideal of a smooth affine algebraic variety. Journal of Symbolic Computation 38 (1), 843--872.

[4]

Bochnak, J., Coste, M., Roy, M.-F., 1998. Real algebraic geometry. Vol. 36. Springer, Berlin, Heidelberg.

[5]

Brake, D. A., Hauenstein, J. D., Liddell, Jr., A. C., 2016. Validating the completeness of the real solution set of a system of polynomial equations. In: Proceedings of the 2016 International Symposium on Symbolic and Algebraic Computation. ISSAC'16. ACM, New York, NY, USA, pp. 143--150.

Digital Library

[6]

Chen, C., Davenport, J. H., May, J. P., Maza, M. M., Xia, B., Xiao, R., 2010. Triangular decomposition of semi-algebraic systems. In: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation. ISSAC'10. ACM, New York, NY, USA, pp. 187--194.

Digital Library

[7]

Chen, C., Davenport, J. H., May, J. P., Maza, M. M., Xia, B., Xiao, R., 2013. Triangular decomposition of semi-algebraic systems. Journal of Symbolic Computation 49, 3--26.

Digital Library

[8]

Chen, C., Davenport, J. H., Moreno Maza, M., Xia, B., Xiao, R., 2011. Computing with semi-algebraic sets represented by triangular decomposition. In: Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation. ISSAC'11. ACM, New York, NY, USA, pp. 75--82.

Digital Library

[9]

Cox, D., Little, J., O'Shea, D., 1992. Ideals, varieties, and algorithms. Vol. 3. Springer.

[10]

Durvye, C., Lecerf, G., 2008. A concise proof of the Kronecker polynomial system solver from scratch. Expositiones Mathematicae 26 (2), 101--139.

[11]

Eisenbud, D., 1995. Commutative Algebra: with a View Toward Algebraic Geometry. Vol. 150. Springer New York, New York, NY.

[12]

Everett, H., Lazard, D., Lazard, S., Safey El Din, M., 2009. The Voronoi diagram of three lines. Discrete & Computational Geometry 42 (1), 94--130.

Digital Library

[13]

Fløystad, G., Kileel, J., Ottaviani, G., 2017. The Chow form of the essential variety in computer vision. Journal of Symbolic Computation.

[14]

Gelfand, I. M., Kapranov, M. M., Zelevinsky, A. V., 1994. Discriminants, Resultants, and Multidimensional Determinants. Birkhauser Boston, Boston, MA.

[15]

Giusti, M., Lecerf, G., Salvy, B., 2001. A Gröbner free alternative for polynomial system solving. Journal of complexity 17 (1), 154--211.

Digital Library

[16]

Jeronimo, G., Krick, T., Sabia, J., Sombra, M., 2004. The computational complexity of the Chow form. Foundations of Computational Mathematics 4 (1), 41--117.

Digital Library

[17]

Kalkbrener, M., 1991. Three contributions to elimination theory. Ph.D. thesis, Johannes Kepler University, Linz.

[18]

Kaltofen, E., 1989. Factorization of polynomials given by straight-line programs. Randomness and Computation 5, 375--412.

[19]

Kaltofen, E., Li, B., Yang, Z., Zhi, L., 2008. Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars. In: Proceedings of the Twenty-first International Symposium on Symbolic and Algebraic Computation. ISSAC'08. ACM, New York, NY, USA, pp. 155--164.

Digital Library

[20]

Kaltofen, E., Trager, B. M., 1990. Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators. Journal of Symbolic Computation 9 (3), 301--320.

Digital Library

[21]

Krick, T., 2002. Straight-line programs in polynomial equation solving. Foundations of computational mathematics: Minneapolis 312, 96--136.

[22]

Lasserre, J.-B., Laurent, M., Mourrain, B., Rostalski, P., Trébuchet, P., 2013. Moment matrices, border bases and real radical computation. Journal of Symbolic Computation 51, 63--85.

Digital Library

[23]

Lasserre, J. B., Laurent, M., Rostalski, P., 2008. Semidefinite characterization and computation of zero-dimensional real radical ideals. Foundations of Computational Mathematics 8 (5), 607--647.

Digital Library

[24]

Lax, P., 2005. On the discriminant of real symmetric matrices. Selected Papers Volume II, 577--586.

[25]

Lazard, D., 1991. A new method for solving algebraic systems of positive dimension. Discrete Applied Mathematics 33 (1--3), 147--160.

Digital Library

[26]

Lecerf, G., 2000. Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions. In: Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation. ISSAC'00. ACM, New York, NY, USA, pp. 209--216.

Digital Library

[27]

Lecerf, G., 2003. Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers. Journal of Complexity 19 (4), 564--596.

Digital Library

[28]

Ma, Y., Wang, C., Zhi, L., 2016. A certificate for semidefinite relaxations in computing positive-dimensional real radical ideals. Journal of Symbolic Computation 72, 1--20.

Digital Library

[29]

Marshall, M., 2008. Positive polynomials and sums of squares. No. 146. American Mathematical Soc.

[30]

Moreno Maza, M., 1997. Calculs de pgcd au-dessus des tours d'extensions simples et résolution des systèmes d'équations algébriques. Ph.D. thesis, Université Paris 6.

[31]

Neuhaus, R., 1998. Computation of real radicals of polynomial ideals -- II. Journal of Pure and Applied Algebra 124 (1), 261--280.

[32]

Poteaux, A., Schost, É., 2013. On the complexity of computing with zero-dimensional triangular sets. Journal of Symbolic Computation 50 (Supplement C), 110 -- 138.

Digital Library

[33]

Safey El Din, M., 2005. Finding sampling points on real hypersurfaces is easier in singular situations. MEGA (Effective Methods in Algebraic Geometry) Electronic proceedings.

[34]

Safey El Din, M., 2007. RAGLib (Real Algebraic Geometry Library), Maple package.

[35]

Safey El Din, M., 2007. Testing sign conditions on a multivariate polynomial and applications. Mathematics in Computer Science 1 (1), 177--207.

[36]

Safey El Din, M., Schost, É., 2003. Polar varieties and computation of one point in each connected component of a smooth real algebraic set. In: Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation. ISSAC'03. ACM, New York, NY, USA, pp. 224--231.

Digital Library

[37]

Safey El Din, M., Schost, É., 2004. Properness defects of projections and computation of at least one point in each connected component of a real algebraic set. Discrete & Computational Geometry 32 (3), 417--430.

Digital Library

[38]

Safey El Din, M., Schost, É., 2017. A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets. Journal of the ACM 63 (6), 48:1--48:37.

Digital Library

[39]

Schost, É., 2003. Computing parametric geometric resolutions. Applicable Algebra in Engineering, Communication and Computing 13 (5), 349--393.

[40]

Spang, S. J., 2007. On the computation of the real radical. Ph.D. thesis, Technische Universitat Kaiserslautern.

[41]

Spang, S. J., 2008. A zero-dimensional approach to compute real radicals. The Computer Science Journal of Moldova 16 (1), 64--92.

[42]

Wang, D., 1998. Decomposing polynomial systems into simple systems. Journal of Symbolic Computation 25 (3), 295--314.

Digital Library

[43]

Wu, W.-T., 1984. Basic principles of mechanical theorem proving in elementary geometries. Journal of Systems Science and Mathematical Sciences 4, 207--235.

Cited By

Harris KHauenstein JSzanto A(2023)Smooth points on semi-algebraic setsJournal of Symbolic Computation10.1016/j.jsc.2022.09.003116(183-212)Online publication date: May-2023
https://doi.org/10.1016/j.jsc.2022.09.003
Baldi LMourrain B(2022)On the effective Putinar’s Positivstellensatz and moment approximationMathematical Programming10.1007/s10107-022-01877-6200:1(71-103)Online publication date: 6-Sep-2022
https://doi.org/10.1007/s10107-022-01877-6
Harris KHauenstein JSzanto A(2021)Smooth points on semi-algebraic setsACM Communications in Computer Algebra10.1145/3457341.345734754:3(105-108)Online publication date: 15-Mar-2021
https://dl.acm.org/doi/10.1145/3457341.3457347
Show More Cited By

Index Terms

On the Complexity of Computing Real Radicals of Polynomial Systems
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Representation of mathematical objects
    2. Symbolic and algebraic algorithms

Recommendations

Software for the Gale transform of fewnomial systems and a Descartes rule for fewnomials

We give a Descartes'-like bound on the number of positive solutions to a system of fewnomials that holds when its exponent vectors are not in convex position and a sign condition is satisfied. This was discovered while developing algorithms and software ...
Computing Real Radicals by Moment Optimization
ISSAC '21: Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation

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 ...
Minimum Ellipsoid Bounds for Solutions of Polynomial Systems via Sum of Squares

We study ellipsoid bounds for the solutions $$(x,\mu) \in \mathbb{R}^{n} \times \mathbb{R}^{r}$$ of polynomial systems of equalities and inequalities. The variable can be considered as parameters perturbing the solution x . For example, bounding the zeros of a system of polynomials whose coefficients ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '18: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation

July 2018

418 pages

ISBN:9781450355506

DOI:10.1145/3208976

Editor:
Carlos Arreche
University of Texas at Dallas, USA
,
General Chairs:
Manuel Kauers
Johannes Kepler University, Austria
,
Alexey Ovchinnikov
City University of New York, USA
,
Program Chair:
Éric Schost
University of Waterloo, Canada

Copyright © 2018 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 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]

In-Cooperation

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

ISSAC '18

ISSAC '18: International Symposium on Symbolic and Algebraic Computation

July 16 - 19, 2018

NY, New York, USA

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
73
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Harris KHauenstein JSzanto A(2023)Smooth points on semi-algebraic setsJournal of Symbolic Computation10.1016/j.jsc.2022.09.003116(183-212)Online publication date: May-2023
https://doi.org/10.1016/j.jsc.2022.09.003
Baldi LMourrain B(2022)On the effective Putinar’s Positivstellensatz and moment approximationMathematical Programming10.1007/s10107-022-01877-6200:1(71-103)Online publication date: 6-Sep-2022
https://doi.org/10.1007/s10107-022-01877-6
Harris KHauenstein JSzanto A(2021)Smooth points on semi-algebraic setsACM Communications in Computer Algebra10.1145/3457341.345734754:3(105-108)Online publication date: 15-Mar-2021
https://dl.acm.org/doi/10.1145/3457341.3457347
Chang SLuo ZQi L(2021)Tensor Manifold with Tucker Rank ConstraintsAsia-Pacific Journal of Operational Research10.1142/S021759592150022639:02Online publication date: 11-Jun-2021
https://doi.org/10.1142/S0217595921500226
Xiao FLu DMa XWang D(2020)An Improvement of the Rational Representation for High-Dimensional SystemsJournal of Systems Science and Complexity10.1007/s11424-020-9316-4Online publication date: 7-Nov-2020
https://doi.org/10.1007/s11424-020-9316-4
Wang CYang ZZhi L(2019)Global Optimization of Polynomials over Real Algebraic SetsJournal of Systems Science and Complexity10.1007/s11424-019-8351-532:1(158-184)Online publication date: 14-Feb-2019
https://doi.org/10.1007/s11424-019-8351-5

View Options

Get Access

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents