Abstract
Let be a polynomial of degree D. Computing the set of generalized critical values of the mapping
(i.e.
) is an important step in algorithms computing sampling points in semi-algebraic sets defined by a single inequality.
A previous algorithm allows us to compute the set of generalized critical values of \(\widetilde{f}\). This one is based on the computation of the critical locus of a projection on a plane P. This plane P must be chosen such that some global properness properties of some projections are satisfied. These properties, which are generically satisfied, are difficult to check in practice. Moreover, choosing randomly the plane P induces a growth of the coefficients appearing in the computations.
We provide here a new certified algorithm computing the set of generalized critical values of \(\widetilde{f}\). This one is still based on the computation of the critical locus on a plane P. The certification process consists here in checking that this critical locus has dimension 1 (which is easy to check in practice), without any assumption of global properness. Moreover, this allows us to limit the growth of coefficients appearing in the computations by choosing a plane P defined by sparse equations. Additionally, we prove that the degree of this critical curve is bounded by \((D-1)^{n-1}-\mathfrak{d}\) where \(\mathfrak{d}\) is the sum of the degrees of the positive dimensional components of the ideal \(\langle \frac{\partial f}{\partial X_1}, \ldots,\frac{\partial f}{\partial X_n}\rangle\).
We also provide complexity estimates on the number of arithmetic operations performed by a probabilistic version of our algorithm.
Practical experiments at the end of the paper show the relevance and the importance of these results which improve significantly in practice previous contributions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alcazar, J.G., Schicho, J., Sendra, J.R.: A delineability-based method for computing critical sets of algebraic surfaces. J. Symb. Comput. 42(6), 678–691 (2007)
Bank, B., Giusti, M., Heintz, J., Pardo, L.-M.: Generalized polar varieties and efficient real elimination procedure. Kybernetika 40(5), 519–550 (2004)
Basu, S., Pollack, R., Roy, M.-F.: Algorithms in real algebraic geometry. Springer, Heidelberg (2003)
Benedetti, R., Risler, J.-J.: Real algebraic and semi-algebraic sets. Actualités Mathématiques, Hermann (1990)
Collins, G.E.: Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In: Brakhage, H. (ed.) GI Fachtagung 1975. LNCS, vol. 33, pp. 515–532. Springer, Heidelberg (1975)
Corvez, S., Rouillier, F.: Using computer algebra tools to classify serial manipulators. In: Winkler, F. (ed.) ADG 2002. LNCS (LNAI), vol. 2930, pp. 31–43. Springer, Heidelberg (2004)
Everett, H., Lazard, D., Lazard, S., Safey El Din, M.: The topology of the Voronoi diagram of three lines in
. In: Proceedings of Symposium on Computational Geometry. ACM Press, South-Korea (2007)
Faugère, J.-C.: Gb/FGb, http://fgbrs.lip6.fr
Fulton, W.: Intersection Theory. Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 2. Springer, Heidelberg (1984)
Gao, X.-S., Hou, X.-R., Tang, J., Cheng, H.-F.: Complete Solution Classification for the Perspective-Three-Point Problem. IEEE Trans. Pattern Anal. Mach. Intell. 25(8), 930–943 (2003)
Giusti, M., Heintz, J., Morais, J.-E., Morgenstern, J., Pardo, L.-M.: Straight-line programs in geometric elimination theory. Journal of Pure and Applied Algebra 124, 101–146 (1998)
Giusti, M., Lecerf, G., Salvy, B.: A Gröbner free alternative for polynomial system solving. Journal of Complexity 17(1), 154–211 (2001)
Grigoriev, D., Vorobjov, N.: Solving systems of polynomials inequalities in subexponential time. Journal of Symbolic Computation 5, 37–64 (1988)
Jelonek, Z., Kurdyka, K.: On asymptotic critical values of a complex polynomial. Journal für die Reine und Angewandte Mathematik 565, 1–11 (2003)
Lazard, D.: Quantifier elimination: optimal solution for two classical examples. Journal of Symbolic Computation 5(1-2), 261–266 (1988)
Lazard, D., Rouillier, F.: Solving parametric polynomial systems. Journal of Symbolic Computation 42, 636–667 (2007)
Lecerf, G.: Kronecker magma package for solving polynomial systems, http://www.math.uvsq.fr/~lecerf/software/
Lax, A., Lax, P.: On sums of squares. Linear Algebra App. 20, 71–75 (1978)
Lecerf, G.: Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers. Journal of Complexity 19(4), 564–596 (2003)
Kurdyka, K., Orro, P., Simon, S.: Semi-algebraic Sard’s theorem for generalized critical values. Journal of differential geometry 56, 67–92 (2000)
Rouillier, F.: RS, RealSolving, http://fgbrs.lip6.fr
Rouillier, F.: Solving zero-dimensional systems through the Rational Univariate Representation. AAECC Journal 9(5), 433–461 (1999)
Rouillier, F., Zimmermann, P.: Efficient isolation of polynomial real roots. Journal of Computational and Applied Mathematics 162(1), 33–50 (2003)
Safey El Din, M.: RAGLib (Real Algebraic Geometry Library) (September 2007), http://www-spiral.lip6.fr/~safey/RAGLib
Safey El Din, M., Schost, É.: 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, pp. 224–231. ACM Press, New York (2003)
Safey El Din, M., Schost, É.: Properness defects of projections and computation of one point in each connected component of a real algebraic set. Discrete and Computational Geometry 32(3), 417–430 (2004)
Safey El Din, M.: Generalized critical values and solving polynomial inequalities. In: Proceedings of International Conference on Polynomial Systems (2004)
Safey El Din, M.: Testing sign conditions on a multivariate polynomial and applications. Mathematics in Computer Science, Special issue on Algorithms and Complexity 1(1), 177–207 (2007)
Schost, E.: Computing Parametric Geometric Resolutions. Journal of Applicable Algebra in Engineering, Communication and Computing 13(5), 349–393 (2003)
Schweighofer, M.: Global optimization of polynomials using gradient tentacles and sums of squares. SIAM Journal on Optimization 17(3), 920–942 (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Safey El Din, M. (2008). Practical and Theoretical Issues for the Computation of Generalized Critical Values of a Polynomial Mapping. In: Kapur, D. (eds) Computer Mathematics. ASCM 2007. Lecture Notes in Computer Science(), vol 5081. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87827-8_4
Download citation
DOI: https://doi.org/10.1007/978-3-540-87827-8_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87826-1
Online ISBN: 978-3-540-87827-8
eBook Packages: Computer ScienceComputer Science (R0)