×

Thirty years of polynomial system solving, and now? (English) Zbl 1158.13314

Summary: In this introductory paper to the special issue, I describe first my personal view of the history of Polynomial System Solving during my career. Then I describe the main challenges which are now opened by the availability of efficient zero-dimensional solvers.

MSC:

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68W30 Symbolic computation and algebraic computation
14Q99 Computational aspects in algebraic geometry
14P99 Real algebraic and real-analytic geometry

Software:

FGb; RAGlib; ISOLATE
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Backelin, J., Fröberg, R., 1991. How we proved that there are exactly 924 cyclic 7-roots. In: ISSAC’91: Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, pp. 103-111; Backelin, J., Fröberg, R., 1991. How we proved that there are exactly 924 cyclic 7-roots. In: ISSAC’91: Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, pp. 103-111 · Zbl 0925.13012
[2] Corvez, S.; Rouillier, F., Using computer algebra tools to classify serial manipulators, (Winkler, F., actes de Automated Deduction in Geometry. actes de Automated Deduction in Geometry, Lecture Notes in Artificial Intelligence, vol. 2930 (2003)), 31-43 · Zbl 1202.68489
[3] Davenport, J.H., 1987. Looking at a set of equations. Tech. Rep., Bath Computer Science; Davenport, J.H., 1987. Looking at a set of equations. Tech. Rep., Bath Computer Science
[4] Everett, H., Lazard, D., Lazard, S., Safey El Din, M., 2007. The Voronoi diagram of three lines in \(\mathbb{R}^3\); Everett, H., Lazard, D., Lazard, S., Safey El Din, M., 2007. The Voronoi diagram of three lines in \(\mathbb{R}^3\) · Zbl 1221.68268
[5] Faugère, J.-C.; Gianni, P.; Lazard, D.; Mora, F., Efficient computation of zero-dimensional Gröbner bases by change of ordering, Journal of Symbolic Computation, 16, 4, 329-344 (1993) · Zbl 0805.13007
[6] Faugère, J.-C., A new efficient algorithm for computing Grobner bases (F4), Journal of Pure and Applied Algebra, 139, 61-88 (1999) · Zbl 0930.68174
[7] Faugère, J.-C., A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), (Proceedings of the International Symposium on Symbolic and Algebraic Computation (2002), ACM Press), 75-83 · Zbl 1072.68664
[8] Giovini, A.; Mora, F.; Niesi, G.; Robbiano, L.; Traverso, C., One sugar cube, please or selection strategies in the Buchberger algorithm, (ISSAC ’91: Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation (1991), ACM Press), 49-54 · Zbl 0933.68161
[9] Gu, N.; Lazard, D.; Rouillier, F.; Xiang, Y., Using computer algebra to certify the global convergence of a numerical optimization process, Mathematics in Computer Science, 1, 2, 291-304 (2007) · Zbl 1134.94314
[10] Kalkbrener, M., A generalized Euclidean algorithm for computing triangular representations of algebraic varieties, Journal of Symbolic Computation, 15, 2, 143-167 (1993) · Zbl 0783.14039
[11] Lazard, D., Algèbre linéaire sur \(K [X_1, \ldots, X_n]\), et élimination, Bulletin de la Sociéte Mathématique de France, 105, 2, 165-190 (1977) · Zbl 0447.13008
[12] Lazard, D., Résolution des systèmes d’équations algébriques, Theoretical Computer Science, 15, 1, 77-110 (1981) · Zbl 0459.68013
[13] Lazard, D., Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations, (Computer algebra (London, 1983). Computer algebra (London, 1983), Lecture Notes in Comput. Sci., vol. 162 (1983), Springer: Springer Berlin), 146-156 · Zbl 0539.13002
[14] Lazard, D., Solving zero-dimensional algebraic systems, Journal of Symbolic Computation, 13, 2, 117-131 (1992) · Zbl 0753.13012
[15] Lazard, D., On the representation of rigid-body motions and its application to generalized platform manipulators, (Angeles, J.; Hommel, G.; Kovács, P., Computational Kinematics. Computational Kinematics, Solid Mechanics and its Applications, No. 29 (1993), Kluwer), 175-181 · Zbl 0873.70006
[16] Lazard, D., Injectivity of real rational mappings: The case of a mixture of two Gaussian laws, Mathematics in Computers in Simulation, 67, 1, 67-84 (2004) · Zbl 1091.68125
[17] Lazard, D.; Rouillier, F., Solving parametric polynomial systems, Journal of Symbolic Computation, 42, 636-667 (2007) · Zbl 1156.14044
[18] (Ng, E. W., Proceedings of the EUROSAM 79, Symposium on Symbolic and Algebraic Manipulation. Proceedings of the EUROSAM 79, Symposium on Symbolic and Algebraic Manipulation, Marseille, June 26-28, 1979. Proceedings of the EUROSAM 79, Symposium on Symbolic and Algebraic Manipulation. Proceedings of the EUROSAM 79, Symposium on Symbolic and Algebraic Manipulation, Marseille, June 26-28, 1979, Lecture Notes in Computer Science, vol. 72 (1979), Springer: Springer Berlin, Heidelberg, New York, London, UK) · Zbl 0398.00018
[19] Quillen, D., Projective modules over polynomial rings, Inventiones Mathematicae, 36, 167-171 (1976) · Zbl 0337.13011
[20] Rouillier, F., Solving zero-dimensional systems through the rational univariate representation, Journal of Applicable Algebra in Engineering, Communication and Computing, 9, 5, 433-461 (1999) · Zbl 0932.12008
[21] Rouillier, F.; Zimmermann, P., Efficient isolation of polynomial real roots, Journal of Computational and Applied Mathematics, 162, 1, 33-50 (2003) · Zbl 1040.65041
[22] Safey El Din, M., Testing sign conditions on a multivariate polynomial and applications, Mathematics in Computer Science, 1, 1, 177-207 (2007) · Zbl 1126.14068
[23] Suslin, A. A., Projective modules over polynomial rings are free, Rossiĭskaya Akademiya Nauk. Doklady Akademic Nauk. SSSR, 229, 5, 1063-1066 (1976), (in Russian) · Zbl 0354.13010
[24] Trinks, W., Über B. Buchbergers Verfahren, Systeme algebraischer Gleichungen zu lösen, Journal of Number Theory, 10, 4, 475-488 (1978) · Zbl 0404.13004
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.