Article

Polar varieties and computation of one point in each connected component of a smooth real algebraic set

Authors:

Mohab Safey El Din,

Éric SchostAuthors Info & Claims

ISSAC '03: Proceedings of the 2003 international symposium on Symbolic and algebraic computation

Pages 224 - 231

https://doi.org/10.1145/860854.860901

Published: 03 August 2003 Publication History

Abstract

Let f₁, ldots, f_s be polynomials in Q[X₁, ..., X_n] that generate a radical ideal and let V be their complex zero-set. Suppose that V is smooth and equidimensional; then we show that computing suitable sections of the polar varieties associated to generic projections of V gives at least one point in each connected component of V ∩ Rⁿ. We deduce an algorithm that extends that of Bank, Giusti, Heintz and Mbakop to non-compact situations. Its arithmetic complexity is polynomial in the complexity of evaluation of the input system, an intrinsic algebraic quantity and a combinatorial quantity.

References

[1]

M. E. Alonso, E. Becker, M.-F. Roy, and T. Wörmann. Zeroes, multiplicities and idempotents for zerodimensional systems. In Proceedings MEGA'94, volume 142 of Progress in Mathematics, pages 1--15. Birkhäuser, 1996.

Digital Library

[2]

P. Aubry, F. Rouillier, and M. Safey El Din. Real solving for positive dimensional systems. Journal of Symbolic Computation, 34(6):543--560, 2002.

Digital Library

[3]

B. Bank, M. Giusti, J. Heintz, and G.-M. Mbakop. Polar varieties and efficient real equation solving: the hypersurface case. Journal of Complexity, 13(1):5--27, 1997.

Digital Library

[4]

B. Bank, M. Giusti, J. Heintz, and G.-M. Mbakop. Polar varieties and efficient real elimination. Mathematische Zeitschrift, 238(1):115--144, 2001.

[5]

B. Bank, M. Giusti, J. Heintz, and L.-M. Pardo. The light is polar. Unpublished manuscript, 2003.

[6]

S. Basu. Algorithms in semi-algebraic geometry. PhD thesis, New-York University, 1996.

Digital Library

[7]

S. Basu, R. Pollack, and M.-F. Roy. On the combinatorial and algebraic complexity of quantifier elimination. Journal of ACM, 43(6):1002--1045, 1996.

Digital Library

[8]

S. Basu, R. Pollack, and M.-F. Roy. A new algorithm to find a point in every cell defined by a family of polynomials. In Quantifier elimination and cylindrical algebraic decomposition. Springer-Verlag, 1998.

[9]

M. Giusti, K. Hägele, J. Heintz, J.-E Morais, J.-L. Montaña, and L.-M. Pardo. Lower bounds for Diophantine approximation. In Proceedings of MEGA'96, number 117, 118 in Journal of Pure and Applied Algebra, pages 277--317, 1997.

[10]

M. Giusti, J. Heintz, J.-E. Morais, J. Morgenstern, and L.-M. Pardo. Straight-line programs in geometric elimination theory. Journal of Pure and Applied Algebra, 124:101--146, 1998.

[11]

M. Giusti, J. Heintz, J.-E. Morais, and L.-M. Pardo. When polynomial equation systems can be solved fast? In Proceedings of AAECC-11, volume 948 of LNCS, pages 205--231. Springer, 1995.

Digital Library

[12]

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

Digital Library

[13]

D. Grigoriev and N. Vorobjov. Solving systems of polynomials inequalities in subexponential time. Journal of Symbolic Computation, 5:37--64, 1988.

Digital Library

[14]

J. Heintz, M.-F. Roy, and P. Solernò. On the complexity of semi-algebraic sets. In Proceedings IFIP'89 San Francisco, North-Holland, 1989.

[15]

J. Heintz, M.-F. Roy, and P. Solernò. On the theoretical and practical complexity of the existential theory of the reals. The Computer Journal, 36(5):427--431, 1993.

[16]

Z. Jelonek. Testing sets for properness of polynomial mappings. Mathematische Annalen, 315(1):1--35, 1999.

[17]

G. Jeronimo, T. Krick, J. Sabia, and M. Sombra. The computational complexity of the Chow form. Technical report Institut de mathématiques de Jussieu, 2003.

[18]

G. Jeronimo, and J. Sabia. Effective equidimensional decomposition of affine varieties. Journal of Pure and Applied Algebra, 169(2-3):229--248, 2002.

[19]

G. Lecerf. Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers. To appear in Journal of Complexity, 2003.

Digital Library

[20]

F. Rouillier. Solving zero-dimensional systems through the Rational Univariate Representation. AAECC Journal, 9(5):433--461, 1999.

[21]

F. Rouillier, M.-F. Roy, and M. Safey El Din. Finding at least one point in each connected component of a real algebraic set defined by a single equation. Journal of Complexity, 16:716--750, 2000.

Digital Library

[22]

M. Safey El Din. Résolution réelle des systèmes polynomiaux de dimension positive. PhD thesis, Université Paris 6, January 2001.

[23]

M. Safey El Din and É. Schost. Properness defects of projections and computation of one point in each connected component of a real algebraic set. Technical report, RR INRIA, 2002.

[24]

I. Shafarevich. Basic Algebraic Geometry 1. Springer Verlag, 1977.

Cited By

Gaillard LSafey El Din M(2024)Solving parameter-dependent semi-algebraic systemsProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669718(447-456)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669718
Gopalakrishnan SNeiger VSafey El Din M(2024)Optimized Gröbner basis algorithms for maximal determinantal ideals and critical point computationsProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669713(400-409)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669713
Prébet RSafey El Din MSchost É(2024)Computing roadmaps in unbounded smooth real algebraic sets I: Connectivity resultsJournal of Symbolic Computation10.1016/j.jsc.2023.102234120(102234)Online publication date: Jan-2024
https://doi.org/10.1016/j.jsc.2023.102234
Show More Cited By

Index Terms

Polar varieties and computation of one point in each connected component of a smooth real algebraic set
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Probabilistic Algorithm for Computing the Dimension of Real Algebraic Sets
ISSAC '15: Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation

Let fΕ Q[X₁, …, X_n] be a polynomial of degree D. We consider the problem of computing the real dimension of the real algebraic set defined by f=0. Such a problem can be reduced to quantifier elimination. Hence it can be tackled with Cylindrical Algebraic ...
Classification of the perspective-three-point problem, discriminant variety and real solving polynomial systems of inequalities
ISSAC '08: Proceedings of the twenty-first international symposium on Symbolic and algebraic computation

Classifying the Perspective-Three-Point problem (abbreviated by P3P in the sequel) consists in determining the number of possible positions of a camera with respect to the apparent position of three points. In the case where the three points form an ...
Computing the global optimum of a multivariate polynomial over the reals
ISSAC '08: Proceedings of the twenty-first international symposium on Symbolic and algebraic computation

Let f be a polynomial in Q[X₁, ..., X_n] of degree D. We provide an efficient algorithm in practice to compute the global supremum sup_{x∈ Rⁿ} f(x) of f (or its infimum inf_{{x∈ Rⁿ}}f(x)). The complexity of our method is bounded by D^O(n)}. In a probabilistic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '03: Proceedings of the 2003 international symposium on Symbolic and algebraic computation

August 2003

284 pages

ISBN:1581136412

DOI:10.1145/860854

General Chair:
Hoon Hong
North Carolina State University, Raleigh, NC

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

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 August 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISSAC03

Sponsor:

ISSAC03: International Symposium on Symbolic and Algebraic Computation

August 3 - 6, 2003

PA, Philadelphia, USA

Acceptance Rates

ISSAC '03 Paper Acceptance Rate 36 of 68 submissions, 53%;

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

61
Total Citations
View Citations
255
Total Downloads

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

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gaillard LSafey El Din M(2024)Solving parameter-dependent semi-algebraic systemsProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669718(447-456)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669718
Gopalakrishnan SNeiger VSafey El Din M(2024)Optimized Gröbner basis algorithms for maximal determinantal ideals and critical point computationsProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669713(400-409)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669713
Prébet RSafey El Din MSchost É(2024)Computing roadmaps in unbounded smooth real algebraic sets I: Connectivity resultsJournal of Symbolic Computation10.1016/j.jsc.2023.102234120(102234)Online publication date: Jan-2024
https://doi.org/10.1016/j.jsc.2023.102234
Yabo ASafey El Din MCaillau JGouzé J(2023)Stability analysis of a bacterial growth model through computer algebraMathematicS In Action10.5802/msia.3712:1(175-189)Online publication date: 26-Sep-2023
https://doi.org/10.5802/msia.37
Labahn GRiener CSafey El Din MSchost EVu T(2023)Faster real root decision algorithm for symmetric polynomialsProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597097(452-460)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597097
Gopalakrishnan SNeiger VSafey El Din M(2023)Refined F5 Algorithms for Ideals of Minors of Square MatricesProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597077(270-279)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597077
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
Elliott JGiesbrecht MSchost É(2023)Bit complexity for computing one point in each connected component of a smooth real algebraic setJournal of Symbolic Computation10.1016/j.jsc.2022.08.010116(72-97)Online publication date: May-2023
https://doi.org/10.1016/j.jsc.2022.08.010
Li XLi BLiu L(2023)Stability and dynamic behaviors of a limited monopoly with a gradient adjustment mechanismChaos, Solitons & Fractals10.1016/j.chaos.2023.113106168(113106)Online publication date: Mar-2023
https://doi.org/10.1016/j.chaos.2023.113106
Guo FJiao LKim DPham T(2023)On Types of Isolated KKT Points in Polynomial OptimizationJournal of Systems Science and Complexity10.1007/s11424-023-2119-736:5(2186-2213)Online publication date: 19-Oct-2023
https://doi.org/10.1007/s11424-023-2119-7
Show More Cited By

View Options

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