×

zbMATH — the first resource for mathematics

A concise proof of the Kronecker polynomial system solver from scratch. (English) Zbl 1134.14317
Summary: Nowadays polynomial system solvers are involved in sophisticated computations in algebraic geometry as well as in practical engineering. The most popular algorithms are based on Gröbner bases, resultants, Macaulay matrices, or triangular decompositions. In all these algorithms, multivariate polynomials are expanded in a monomial basis, and the computations mainly reduce to linear algebra. The major drawback of these techniques is the exponential explosion of the size of the polynomials needed to represent highly positive dimensional solution sets. Alternatively, the “Kronecker solver” uses data structures to represent the input polynomials as the functions that compute their values at any given point. In this paper, we present the first self-contained and student friendly version of the Kronecker solver, with a substantially simplified proof of correctness. In addition, we enhance the solver in order to compute the multiplicities of the zeros without any extra cost.

MSC:
14Q15 Computational aspects of higher-dimensional varieties
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68W30 Symbolic computation and algebraic computation
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] M.-E. Alonso, E. Becker, M.-F. Roy, T. Wörmann, Zeros, multiplicities, and idempotents for zero-dimensional systems, Algorithms in Algebraic Geometry and Applications. Proceedings of MEGA’94, Progress in Mathematics, vol. 143, Birkhäuser, 1996, pp. 1-15. · Zbl 0879.14033
[2] Bank, B.; Giusti, M.; Heintz, J.; Mbakop, G.M., Polar varieties, real equation solving, and data structures: the hypersurface case, J. complexity, 13, 1, 5-27, (1997) · Zbl 0872.68066
[3] Bank, B.; Giusti, M.; Heintz, J.; Mbakop, G.M., Polar varieties and efficient real elimination, Math. Z., 238, 1, 115-144, (2001) · Zbl 1073.14554
[4] Bank, B.; Giusti, M.; Heintz, J.; Pardo, L.M., Generalized polar varieties and an efficient real elimination procedure, Kybernetika (Prague), 40, 5, 519-550, (2004) · Zbl 1249.14019
[5] Becker, T.; Weispfenning, V., Gröbner bases. A computational approach to commutative algebra, graduate texts in mathematics, vol. 141, (1993), Springer Berlin
[6] Bompadre, A.; Matera, G.; Wachenchauzer, R.; Waissbein, A., Polynomial equation solving by lifting procedures for ramified fibers, Theoret. comput. sci., 315, 2-3, 334-369, (2004) · Zbl 1060.65054
[7] A. Bostan, G. Lecerf, B. Salvy, É. Schost, B. Wiebelt, Complexity issues in bivariate polynomial factorization, Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, ACM, 2004, pp. 42-49. · Zbl 1134.68595
[8] Bruno, N.; Heintz, J.; Matera, G.; Wachenchauzer, R., Functional programming concepts and straight-line programs in computer algebra, Math. comput. simulation, 60, 6, 423-473, (2002) · Zbl 1005.68187
[9] Bürgisser, P.; Clausen, M.; Shokrollahi, M.A., Algebraic complexity theory, (1997), Springer Berlin · Zbl 1087.68568
[10] Cafure, A.; Matera, G., Fast computation of a rational point of a variety over a finite field, Math. comp., 75, 256, 2049-2085, (2006) · Zbl 1122.11040
[11] Cafure, A.; Matera, G., Improved explicit estimates on the number of solutions of equations over a finite field, Finite fields appl., 12, 2, 155-185, (2006) · Zbl 1163.11329
[12] L. Caniglia, A. Galligo, J. Heintz, Some new effectivity bounds in computational geometry, Applied algebra, algebraic algorithms and error-correcting codes (Rome, 1988), Lecture Notes in Computer Science, vol. 357, Springer, Berlin, 1989, pp. 131-151.
[13] Castaño, B.; Heintz, J.; Llovet, J.; Martínez, R., On the data structure straight-line program and its implementation in symbolic computation, Math. comput. simulation, 51, 5, 497-528, (2000)
[14] Castro, D.; Giusti, M.; Heintz, J.; Matera, G.; Pardo, L.M., The hardness of polynomial equation solving, Found. comput. math., 3, 4, 347-420, (2003) · Zbl 1049.68070
[15] Castro, D.; Montaña, J.L.; Pardo, L.M.; San Martín, J., The distribution of condition numbers of rational data of bounded bit length, Found. comput. math., 2, 1, 1-52, (2002) · Zbl 1011.65017
[16] Castro, D.; Pardo, L.M.; Hägele, K.; Morais, J.E., Kronecker’s and Newton’s approaches to solving: a first comparison, J. complexity, 17, 1, 212-303, (2001) · Zbl 1013.68296
[17] Castro, D.; Pardo, L.M.; San Martín, J., Systems of rational polynomial equations have polynomial size approximate zeros on the average, J. complexity, 19, 2, 161-209, (2003) · Zbl 1018.14020
[18] Chèze, G.; Lecerf, G., Lifting and recombination techniques for absolute factorization, J. complexity, 23, 3, 380-420, (2007) · Zbl 1130.12007
[19] D.A. Cox, J. Little, D. O’Shea, Ideals varieties and algorithms. An introduction to computational algebraic geometry and commutative algebra, second ed., Undergraduate Texts in Mathematics, Springer, Berlin, 1997.
[20] D.A. Cox, J. Little, D. O’Shea, Using algebraic geometry, second ed., Graduate Texts in Mathematics, Springer, Berlin, 2005.
[21] De Leo, M.; Dratman, E.; Matera, G., Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study, J. complexity, 21, 4, 502-531, (2005) · Zbl 1098.65052
[22] M. Demazure, Réécriture et bases standard, Notes informelles de calcul formel. Centre de Mathématiques, École polytechnique, Palaiseau, France, 1985, http://www.stix.polytechnique.fr/publications/1984-1994.html.
[23] Eisenbud, D., Commutative algebra. with a view toward algebraic geometry, graduate texts in mathematics, (1995), Springer Berlin
[24] N. Fitchas, M. Giusti, F. Smietanski, Sur la complexité du théorème des zéros, Approximation and optimization in the Caribbean, II (Havana, 1993), Approximation and Optimization, vol. 8, Lang, Frankfurt am Main, 1995, pp. 274-329. · Zbl 0868.12008
[25] von zur Gathen, J.; Gerhard, J., Modern computer algebra, (2003), Cambridge University Press · Zbl 1055.68168
[26] Gaudry, P.; Schost, É., Modular equations for hyperelliptic curves, Math. comp., 74, 249, 429-454, (2005) · Zbl 1086.11028
[27] Giusti, M.; Hägele, K.; Heintz, J.; Montaña, J.L.; Morais, J.E.; Pardo, L.M., Lower bounds for Diophantine approximations, J. pure appl. algebra, 117/118, 277-317, (1997) · Zbl 0871.68101
[28] Giusti, M.; Hägele, K.; Lecerf, G.; Marchand, J.; Salvy, B., The projective Noether Maple package: computing the dimension of a projective variety, J. symbolic comput., 30, 3, 291-307, (2000) · Zbl 0963.68235
[29] M. Giusti, J. Heintz, La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial, Computational algebraic geometry and commutative algebra (Cortona, 1991), Symposium on Mathematics, XXXIV, Cambridge University Press, 1993, pp. 216-256.
[30] M. Giusti, J. Heintz, Kronecker’s smart, little black boxes, Foundations of Computational Mathematics (Oxford, 1999), London Mathematical Society Lecture Note Series, vol. 284, Cambridge University Press, 2001, pp. 69-104. · Zbl 0978.65043
[31] Giusti, M.; Heintz, J.; Morais, J.E.; Morgenstern, J.; Pardo, L.M., Straight-line programs in geometric elimination theory, J. pure appl. algebra, 124, 1-3, 101-146, (1998) · Zbl 0944.12004
[32] M. Giusti, J. Heintz, J.E. Morais, L.M. Pardo, When polynomial equation systems can be “solved” fast?, Applied algebra, algebraic algorithms and error-correcting codes (Paris, 1995), Lecture Notes in Computer Science, vol. 948, Springer, Berlin, 1995, pp. 205-231. · Zbl 0902.12005
[33] Giusti, M.; Heintz, J.; Morais, J.E.; Pardo, L.M., Le rôle des structures de données dans LES problèmes d’élimination, C. R. acad. sci. Paris Sér. I math., 325, 11, 1223-1228, (1997) · Zbl 0893.68144
[34] Giusti, M.; Heintz, J.; Sabia, J., On the efficiency of effective nullstellensätze, Comput. complexity, 3, 1, 56-95, (1993) · Zbl 0824.68051
[35] Giusti, M.; Lecerf, G.; Salvy, B., A Gröbner free alternative for polynomial system solving, J. complex., 17, 1, 154-211, (2001) · Zbl 1003.12005
[36] M. Giusti, É. Schost, Solving some overdetermined polynomial systems. Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, ACM, 1999, pp. 1-8.
[37] Greuel, G.-M.; Pfister, G., A singular introduction to commutative algebra, (2002), Springer Berlin
[38] K. Hägele, Intrinsic height estimates for the Nullstellensatz, Ph.D. Thesis, Universidad de Cantabria, Santander, Spain, 1998.
[39] Hägele, K.; Morais, J.E.; Pardo, L.M.; Sombra, M., On the intrinsic complexity of the arithmetic nullstellensatz, J. pure appl. algebra, 146, 2, 103-183, (2000) · Zbl 0971.14042
[40] Heintz, J.; Krick, T.; Puddu, S.; Sabia, J.; Waissbein, A., Deformation techniques for efficient polynomial equation solving, J. complexity, 16, 1, 70-109, (2000) · Zbl 1041.65044
[41] Heintz, J.; Matera, G.; Pardo, L.M.; Wachenchauzer, R., The intrinsic complexity of parametric elimination methods, Electronic J. of SADIO, 1, 1, 37-51, (1998) · Zbl 0915.68073
[42] Heintz, J.; Matera, G.; Waissbein, A., On the time-space complexity of geometric elimination procedures, Appl. algebra engrg. comm. comput., 11, 4, 239-296, (2001) · Zbl 0977.68101
[43] Horn, R.A.; Johnson, C.R., Topics in matrix analysis, (1994), Cambridge University Press, Corrected reprint of the 1991 original · Zbl 0801.15001
[44] Jeronimo, G.; Krick, T.; Sabia, J.; Sombra, M., The computational complexity of the Chow form, Found. comput. math., 4, 1, 41-117, (2004) · Zbl 1058.14075
[45] G. Jeronimo, G. Matera, P. Solerno, A. Waissbein, Deformation techniques for sparse systems, arXiv:math/0608714v1, 2006. · Zbl 1167.14039
[46] Jeronimo, G.; Puddu, S.; Sabia, J., Computing Chow forms and some applications, J. algorithms, 41, 1, 52-68, (2001) · Zbl 1002.68061
[47] Jeronimo, G.; Sabia, J., Probabilistic equidimensional decomposition, C. R. acad. sci. Paris Sér. I math., 331, 6, 485-490, (2000) · Zbl 0964.65054
[48] Jeronimo, G.; Sabia, J., Effective equidimensional decomposition of affine varieties, J. pure appl. algebra, 169, 2-3, 229-248, (2002) · Zbl 1055.14061
[49] T. Krick, L.M. Pardo, A computational method for diophantine approximation, Algorithms in algebraic geometry and applications (Santander, 1994), Progress in Mathematics, vol. 143, Birkhäuser, 1996, pp. 193-253. · Zbl 0878.11043
[50] Kronecker, L., Grundzüge einer arithmetischen theorie der algebraischen grössen, J. reine angew. math., 92, 1-122, (1882) · JFM 14.0038.02
[51] S. Lang, Algebra, third ed., Graduate Texts in Mathematics, vol. 211, Springer, Berlin, 2002.
[52] G. Lecerf, Kronecker, a Magma Package for Polynomial System Solving, http://www.math.uvsq.fr/∼lecerf.
[53] G. Lecerf, Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions, Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation, ACM, 2000, pp. 209-216. · Zbl 1326.68360
[54] G. Lecerf, Une alternative aux méthodes de réécriture pour la résolution des systèmes algébriques, Ph.D. Thesis, École polytechnique, Palaiseau, France, 2001.
[55] Lecerf, G., Quadratic Newton iteration for systems with multiplicity, Found. comput. math., 2, 3, 247-293, (2002) · Zbl 1030.65050
[56] Lecerf, G., Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers, J. complexity, 19, 4, 564-596, (2003) · Zbl 1230.68222
[57] Lecerf, G., Sharp precision in hensel lifting for bivariate polynomial factorization, Math. comp., 75, 921-933, (2006) · Zbl 1125.12003
[58] Lecerf, G., Improved dense multivariate polynomial factorization algorithms, J. symbolic comput., 42, 4, 477-494, (2007) · Zbl 1127.13021
[59] L. Lehmann, Polar varieties, real elimination and wavelet design, 2004, Talk given at Dagstuhl Seminar 04061 on Real Computation and Complexity.
[60] Mallat, S., Foveal detection and approximation for singularities, Appl. comput. harmon. anal., 14, 2, 133-180, (2003) · Zbl 1042.42034
[61] Matera, G., Probabilistic algorithms for geometric elimination, Appl. algebra engrg. comm. comput., 9, 6, 463-520, (1999) · Zbl 0934.68122
[62] Mora, T., Solving polynomial equation systems. I the Kronecker-duval philosophy, encyclopedia of mathematics and its applications, vol. 88, (2003), Cambridge University Press
[63] J.E. Morais, Resolución eficaz de sistemas de ecuaciones polinomiales, Ph.D. Thesis, Universidad de Cantabria, Santander, Spain, 1997.
[64] L.M. Pardo, How lower and upper complexity bounds meet in elimination theory, Applied algebra, algebraic algorithms and error-correcting codes (Paris, 1995), Lecture Notes in Computer Science, vol. 948, Springer, Berlin, 1995, pp. 33-69. · Zbl 0899.68054
[65] Pardo, L.M.; San Martin, J., Deformation techniques to solve generalised pham systems, Theoret. comput. sci., 315, 2-3, 593-625, (2004) · Zbl 1053.65038
[66] Rouillier, F., Solving zero-dimensional systems through the rational univariate representation, Appl. algebra engrg. comm. comput., 6, 353-376, (1996)
[67] M. Safey El Din, Finding sampling points on real hypersurfaces is easier in singular situations, Proceedings of Effective Methods in Algebraic Geometry, 2005.
[68] Safey El Din, M.; Schost, É., Properness defects of projections and computation of at least one point in each connected component of a real algebraic set, Discrete comput. geom., 32, 3, 417-430, (2004) · Zbl 1067.14057
[69] Schost, É., Computing parametric geometric resolutions, Appl. algebra engrg. comm. comput., 13, 5, 349-393, (2003) · Zbl 1058.68123
[70] Shafarevich, I.R., Basic algebraic geometry. 1 varieties in projective space, (1994), Springer Berlin · Zbl 0797.14001
[71] A.J. Sommese, J. Verschelde, C.W. Wampler, Solving polynomial systems equation by equation in the IMA volume on algorithms in algebraic geometry, Springer, New York, to appear. · Zbl 1136.65052
[72] Wang, D., Elimination practice. software tools and applications, (2004), Imperial College Press London · Zbl 1099.13047
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.