×

zbMATH — the first resource for mathematics

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:
dpgb; RAGlib
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aubry, P.; Lazard, D.; Moreno-Maza, M., On the theories of triangular sets, 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, () · 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
[5] Corvez, S.; Rouillier, F., Using computer algebra tools to classify serial manipulators, (), 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, () · 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 · Zbl 1326.68354
[10] Lazard, D., On the specification for solvers of polynomial systems, (), 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, (), 53-69 · Zbl 1110.13018
[13] Matsumura, H., (), Translated from Japanese by M. Reid
[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 · 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, () · 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, (), 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 · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.