×

Solving parametric polynomial systems. (English) Zbl 1156.14044

The authors present a new algorithm for solving constructible or semi-algebraic systems in the indeterminates \([U,X]\) where \(U=[U_1,\dots ,U_d]\) is the set of parameters and \(X=[X_{d+1},\dots,X_n]\) the set of unknowns. To this end, they study the characterization of open subsets in the parameter space over which the number of solutions is constant. What they define as the “discriminant variety with respect to a given projection of a basic constructible set” describes well the points where the projection is not regular. They show that this object is optimal in some sense and, in most cases, easy to compute. In the complex case, they develop an algorithm that avoids costly computations and works on a large class of systems, the so-called “well-behaved systems”, that includes most systems coming from applications. A more complicated picture arises in the real case, where they make use of other tools to compute and study this variety. In both cases, the algorithms are efficient and provide improvements in the solving of nontrivial systems.

MSC:

14P99 Real algebraic and real-analytic geometry
68W30 Symbolic computation and algebraic computation
55R80 Discriminantal varieties and configuration spaces in algebraic topology

Software:

RAGlib; dpgb
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aubry, P.; Lazard, D.; Moreno-Maza, M., On the theories of triangular sets, Polynomial Elimination. Polynomial Elimination, Journal of Symbolic Computation, 28, 1, 105-124 (1999) · Zbl 0943.12003
[2] Becker, T.; Weispfenning, V., Gröbner bases: A computational approach to commutative algebra, (Graduate Texts in Mathematics: Readings in Mathematics (1993), Springer) · Zbl 0772.13010
[3] Collins, G. E., Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Lecture Notes in Computer Science, 33, 515-532 (1975)
[4] Corvez, S., 2005. Etude de systèmes polynomiaux: Contributions à la classification d’une famille de manipulateurs et au calculs des intersections de courbes A-splines. Ph.D. Thesis, Université de Rennes 1; Corvez, S., 2005. Etude de systèmes polynomiaux: Contributions à la classification d’une famille de manipulateurs et au calculs des intersections de courbes A-splines. Ph.D. Thesis, Université de Rennes 1
[5] Corvez, S.; Rouillier, F., Using computer algebra tools to classify serial manipulators, (Automated Deduction in Geometry. Automated Deduction in Geometry, Lecture Notes in Artificial Intelligence, vol. 2930 (2003), Springer), 31-43 · Zbl 1202.68489
[6] Cox, D.; Little, J.; O’Shea, D., Ideals, varieties, and algorithms: An introduction to computational algebraic geometry and commutative algebra, (Undergraduate Texts in Mathematics (1992), Springer) · Zbl 0861.13012
[7] Eisenbud, D.; Huneke, C.; Vasconcelos, W., Direct methods for primary decomposition, Inventiones Mathematicae, 110, 207-235 (1992) · Zbl 0770.13018
[8] Gianni, P.; Trager, B.; Zacharias, G., Gröbner bases and primary decomposition of polynomial ideals, Journal of Symbolic Computation, 6, 2, 149-168 (1988) · Zbl 0667.13008
[9] Grigoriev, D., Vorobjov, N., 2000. Bounds on numbers of vectors of multiplicities for polynomials which are easy to compute. In: ISSAC: Proceedings of the ACM SIGSAM International Symposium on Symbolic and Algebraic Computation; Grigoriev, D., Vorobjov, N., 2000. Bounds on numbers of vectors of multiplicities for polynomials which are easy to compute. In: ISSAC: Proceedings of the ACM SIGSAM International Symposium on Symbolic and Algebraic Computation · Zbl 1326.68354
[10] Lazard, D., On the specification for solvers of polynomial systems, (5th Asian Symposium on Computers Mathematics. 5th Asian Symposium on Computers Mathematics, ASCM 2001. 5th Asian Symposium on Computers Mathematics. 5th Asian Symposium on Computers Mathematics, ASCM 2001, Lecture Notes Series in Computing, vol. 9 (2001), World Scientific), 66-75 · Zbl 1009.65028
[11] Lazard, D., Injectivity of real rational mappings: The case of a mixture of two Gaussian laws, Mathematics and Computers in Simulation, 67, 1-2, 67-84 (2004) · Zbl 1091.68125
[12] Lazard, D., Computing with parameterized varieties, (Mathematics and Visualization (2006), Springer), 53-69 · Zbl 1110.13018
[13] Matsumura, H., (Commutative Theory Ring. Commutative Theory Ring, Cambridge Studies in Advanced Mathematics, vol. 8 (1989), Cambridge University Press), Translated from Japanese by M. Reid · Zbl 0666.13002
[14] Manubens, M.; Montes, A., Improving the DISPGB algorithm using the discriminant ideal, Journal of Symbolic Computation, 41, 11, 1245-1263 (2006), (special issue on the occasion of Volker Weispfennig’s 60th Birthday) · Zbl 1121.13031
[15] Moroz, G., 2006. Complexity of the resolution of parametric systems of equations and inequations. In: proceedings of the ISSAC’06 conference, pp. 246-253. Best student paper award; Moroz, G., 2006. Complexity of the resolution of parametric systems of equations and inequations. In: proceedings of the ISSAC’06 conference, pp. 246-253. Best student paper award · Zbl 1356.14050
[16] Mumford, D., Algebraic Geometry I, Complex Projective Varieties (1976), Springer · Zbl 0356.14002
[17] Mumford, D., The red book of varieties and schemes, (Lecture Notes in Mathematics, vol. 1358 (1988)) · Zbl 0658.14001
[18] Safey El Din, M.; Schost, E., Polar varieties and computation of one point in each connected component of a smooth real algebraic set, (Sendra, J. R., International Symposium on Symbolic and Algebraic Computation 2003. International Symposium on Symbolic and Algebraic Computation 2003, ISSAC’2003, Philadelphia, USA (August 2003), ACM Press), 224-231 · Zbl 1072.68693
[19] Safey El Din, M.; Schost, E., Properness defects of projection functions and computation of at least one point in each connected component of a real algebraic set, Journal of Discrete and Computational Geometry, 32, 3, 417-430 (September 2004)
[20] Schost, E., Computing parametric geometric resolutions, Applicable Algebra in Engineering, Communication and Computing, 13, 5, 349-393 (2003) · Zbl 1058.68123
[21] Wang, D., Elimination Methods (2001), Springer · Zbl 0964.13014
[22] Weispfenning, V., Comprehensive Gröbner bases, Journal of Symbolic Computation, 14, 1-29 (1992) · Zbl 0784.13013
[23] Weispfenning, V., Solving Parametric Polynomial Equations and Inequalities by Symbolic Algorithms (1995), World Scientific
[24] Yang, L., Zeng, Z., 2000. Equi-Cevaline points on triangles. In: World Scientific (Ed.), Proceedings of the Fourth Asian Symposium. In: Computer Mathematics, pp. 130-137; Yang, L., Zeng, Z., 2000. Equi-Cevaline points on triangles. In: World Scientific (Ed.), Proceedings of the Fourth Asian Symposium. In: Computer Mathematics, pp. 130-137 · Zbl 0981.65031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.