×

zbMATH — the first resource for mathematics

On the complexity exponent of polynomial system solving. (English) Zbl 1457.14002
The authors present a probabilistic Las Vegas algorithm for solving sufficiently generic square polynomial systems over finite fields. For \(\mathbb{K}\) an effective field, consider a homogeneous system of polynomial equations \(f_1=\dots =f_n=0\), where \(f_i\in \mathbb{K}[x_0,\dots ,x_n]\), deg\(f_i\geq 2\), and the exact resolution of such a system through the computation of a parametrization of its zero set by a so-called primitive element. The algorithm requires \(f_1, \dots, f_n\) to be a regular sequence and the intermediate ideals \(I_i:=(f_1,\dots ,f_i)\), \(1\leq i\leq n\), to be absolutely radical, that is radical over the algebraic closure of \(\mathbb{K}\). The authors achieve a nearly quadratic running time in the number of solutions, for densely represented input polynomials, and prove a nearly linear bit complexity bound for polynomial systems with rational coefficients.
The results are obtained using the combination of the Kronecker solver and a new improved algorithm for fast multivariate modular composition.
MSC:
14-04 Software, source code, etc. for problems pertaining to algebraic geometry
14Q20 Effectivity, complexity and computational aspects of algebraic geometry
14B05 Singularities in algebraic geometry
68W30 Symbolic computation and algebraic computation
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] M. Agrawal, N. Kayal, and N. Saxena. PRIMES is in P. Ann. Math., pages 781-793, 2004. · Zbl 1071.11070
[2] Bank, B.; Giusti, M.; Heintz, J.; Lecerf, G.; Matera, G.; Solernó, P., Degeneracy loci and polynomial equation solving, Found. Comput. Math., 15, 1, 159-184 (2015) · Zbl 1341.14022
[3] M. Bardet. Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie. PhD thesis, Université Pierre et Marie Curie - Paris VI, 2004. https://tel.archives-ouvertes.fr/tel-00449609.
[4] Bardet, M.; Faugère, J-C; Salvy, B., On the complexity of the \(F_5\) Gröbner basis algorithm, J. Symbolic Comput., 70, 49-70 (2015) · Zbl 1328.68319
[5] Berkowitz, SJ, On computing the determinant in small parallel time using a small number of processors, Inform. Process. Lett., 18, 147-150 (1984) · Zbl 0541.68019
[6] J. Berthomieu, J. van der Hoeven, and G. Lecerf. Relaxed algorithms for p-adic numbers. J. Théor. Nombres Bordeaux, 23(3), 2011. · Zbl 1247.11152
[7] Berthomieu, J.; Lecerf, G.; Quintin, G., Polynomial root finding over local rings and application to error correcting codes, Appl. Alg. Eng. Comm. Comp., 24, 6, 413-443 (2013) · Zbl 1309.13034
[8] A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B. Salvy, and É Schost. Algorithmes Efficaces en Calcul Formel. Frédéric Chyzak (self-published), Palaiseau, 2017. Electronic version available from https://hal.archives-ouvertes.fr/AECF.
[9] Bostan, A.; Flajolet, Ph; Salvy, B.; Schost, É., Fast computation of special resultants, J. Symbolic Comput., 41, 1, 1-29 (2006) · Zbl 1121.13037
[10] Bostan, A.; Schost, É., Polynomial evaluation and interpolation on special sets of points, J. Complexity, 21, 4, 420-446 (2005) · Zbl 1101.68039
[11] Brent, RP; Kung, HT, Fast algorithms for manipulating formal power series, J. ACM, 25, 4, 581-595 (1978) · Zbl 0388.68052
[12] Brownawell, WD, Bounds for the degrees in the Nullstellensatz, Annal. of Math., 126, 3, 577-591 (1987) · Zbl 0641.14001
[13] P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic complexity theory, volume 315 of Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, 1997. · Zbl 1087.68568
[14] J. F. Canny, E. Kaltofen, and L. Yagati. Solving systems of nonlinear polynomial equations faster. In Proceedings of the ACM-SIGSAM 1989 International Symposium on Symbolic and Algebraic Computation, ISSAC ’89, pages 121-128. New York, NY, USA, 1989. ACM.
[15] Cantor, DG; Kaltofen, E., On fast multiplication of polynomials over arbitrary algebras, Acta Infor., 28, 693-701 (1991) · Zbl 0766.68055
[16] Couveignes, J-M; Lercier, R., Fast construction of irreducible polynomials over finite fields, Israel J. Math., 194, 1, 77-105 (2013) · Zbl 1287.11141
[17] D’Andrea, C.; Ostafe, A.; Shparlinski, IE; Sombra, M., Reduction modulo primes of systems of polynomial equations and algebraic dynamical systems, Trans. Amer. Math. Soc., 371, 2, 1169-1198 (2019) · Zbl 1403.37101
[18] Durvye, C.; Lecerf, G., A concise proof of the Kronecker polynomial system solver from scratch, Expo. Math., 26, 2, 101-139 (2008) · Zbl 1134.14317
[19] J.-C. Faugère, P. Gaudry, L. Huot, and G. Renault. Sub-cubic change of ordering for Gröbner basis: a probabilistic approach. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC ’14, pages 170-177. New York, NY, USA, 2014. ACM. · Zbl 1325.68277
[20] Faugère, J-C; Gianni, P.; Lazard, D.; Mora, T., Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symbolic Comput., 16, 4, 329-344 (1993) · Zbl 0805.13007
[21] von Gathen, J. zur; Gerhard, J., Modern computer algebra (2013), New York: Cambridge University Press, New York · Zbl 1277.68002
[22] Giménez, N.; Matera, G., On the bit complexity of polynomial system solving, J. Complexity, 51, 20-67 (2019) · Zbl 1432.13020
[23] M. Giusti. Some effectivity problems in polynomial ideal theory. In J. Fitch, editor, EUROSAM 84: International Symposium on Symbolic and Algebraic Computation Cambridge, England, July 9-11, 1984, pages 159-171. Berlin, Heidelberg, 1984. Springer Berlin Heidelberg. · Zbl 0585.13010
[24] Giusti, M.; Hägele, K.; Heintz, J.; Montaña, JL; Morais, JE; Pardo, LM, Lower bounds for Diophantine approximations, J. Pure Appl. Algebra, 117, 118, 277-317 (1997) · Zbl 0871.68101
[25] Giusti, M.; Heintz, J.; Morais, JE; Morgenstern, J.; Pardo, LM, Straight-line programs in geometric elimination theory, J. Pure Appl. Algebra, 124, 1-3, 101-146 (1998) · Zbl 0944.12004
[26] M. Giusti, J. Heintz, J. E. Morais, and L. M. Pardo. When polynomial equation systems can be “solved” fast? In Applied algebra, algebraic algorithms and error-correcting codes (Paris, 1995), volume 948 of Lecture Notes in Comput. Sci., pages 205-231. Springer-Verlag, 1995. · Zbl 0902.12005
[27] Giusti, M.; Lecerf, G.; Salvy, B., A Gröbner free alternative for polynomial system solving, J. complexity, 17, 1, 154-211 (2001) · Zbl 1003.12005
[28] Grenet, B.; van der Hoeven, J.; Lecerf, G., Deterministic root finding over finite fields using Graeffe transforms, Appl. Alg. Eng. Comm. Comp., 27, 3, 237-257 (2016) · Zbl 1346.13056
[29] Harvey, D.; van der Hoeven, J., Faster polynomial multiplication over finite fields using cyclotomic coefficient rings, J. Complexity, 54, 101404 (2019) · Zbl 1423.12010
[30] D. Harvey and J. van der Hoeven. Integer multiplication in time \(O (n \log n)\). Technical Report, HAL, 2019. http://hal.archives-ouvertes.fr/hal-02070778. · Zbl 1394.68182
[31] D. Harvey and J. van der Hoeven. Polynomial multiplication over finite fields in time \(O (n \log n)\). Technical Report, HAL, 2019. http://hal.archives-ouvertes.fr/hal-02070816. · Zbl 1423.12010
[32] Heintz, J., Definability and fast quantifier elimination in algebraically closed fields, Theor. Comput. Sci., 24, 3, 239-277 (1983) · Zbl 0546.03017
[33] J. van der Hoeven and G. Lecerf. Modular composition via complex roots. Technical Report, CNRS & École polytechnique, 2017. http://hal.archives-ouvertes.fr/hal-01455731. · Zbl 1457.68331
[34] van der Hoeven, J.; Lecerf, G., Modular composition via factorization, J. Complexity, 48, 36-68 (2018) · Zbl 1430.12003
[35] van der Hoeven, J.; Lecerf, G., Accelerated tower arithmetic, J. Complexity, 55, 101402 (2019) · Zbl 07134888
[36] van der Hoeven, J.; Lecerf, G., Fast multivariate multi-point evaluation revisited, J. Complexity, 56, 101405 (2020) · Zbl 07146814
[37] J. van der Hoeven, G. Lecerf, B. Mourrain et al. Mathemagix. From 2002. http://www.mathemagix.org.
[38] Huang, Xiaohan; Pan, V. Y., Fast rectangular matrix multiplication and applications, J. Complexity, 14, 2, 257-299 (1998) · Zbl 0919.65030
[39] Jeronimo, G.; Sabia, J., Effective equidimensional decomposition of affine varieties, J. Pure Appl. Algebra, 169, 2-3, 229-248 (2002) · Zbl 1055.14061
[40] E. Kaltofen and V. Shoup. Fast polynomial factorization over high algebraic extensions of finite fields. In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, ISSAC ’97, pages 184-188. New York, NY, USA, 1997. ACM. · Zbl 0920.11082
[41] K. S. Kedlaya and C. Umans. Fast modular composition in any characteristic. In FOCS’08: IEEE Conference on Foundations of Computer Science, pages 146-155. Washington, DC, USA, 2008. IEEE Computer Society.
[42] Kedlaya, KS; Umans, C., Fast polynomial factorization and modular composition, SIAM J. Comput., 40, 6, 1767-1802 (2011) · Zbl 1333.11117
[43] Krick, T.; Pardo, LM; Sombra, M., Sharp estimates for the arithmetic Nullstellensatz, Duke Math. J., 109, 3, 521-598 (2001) · Zbl 1010.11035
[44] Kronecker, L., Grundzüge einer arithmetischen Theorie der algebraischen Grössen, J.reine angew. Math., 92, 1-122 (1882) · JFM 14.0038.02
[45] Y. N. Lakshman. On the complexity of computing a Gröbner basis for the radical of a zero dimensional ideal. In Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing, STOC ’90, pages 555-563. New York, NY, USA, 1990. ACM.
[46] Lakshman, YN; Mora, T.; Traverso, C., A single exponential bound on the complexity of computing Gröbner bases of zero dimensional ideals, Effective Methods in Algebraic Geometry, 227-234 (1991), Boston, MA: Birkhäuser Boston, Boston, MA
[47] Lakshman, YN; Lazard, D.; Mora, T.; Traverso, C., On the complexity of zero-dimensional algebraic systems, Effective Methods in Algebraic Geometry, 217-225 (1991), Boston, MA: Birkhäuser Boston, Boston, MA
[48] D. Lazard. Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations. In J. A. Hulzen, editor, Computer Algebra: EUROCAL’83, European Computer Algebra Conference London, England, March 28-30, 1983 Proceedings, pages 146-156. Springer Berlin Heidelberg, 1983. · Zbl 0539.13002
[49] F. Le Gall. Powers of tensors and fast matrix multiplication. In K. Nabeshima, editor, ISSAC’14: International Symposium on Symbolic and Algebraic Computation, pages 296-303. New York, NY, USA, 2014. ACM. · Zbl 1325.65061
[50] 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
[51] Lecerf, G., On the complexity of the Lickteig-Roy subresultant algorithm, J. Symbolic Comput., 92, 243-268 (2019) · Zbl 1409.13051
[52] Lelong, P., Mesure de Mahler et calcul de constantes universelles pour les polynomes de \(N\) variables, Math. Ann., 299, 1, 673-695 (1994) · Zbl 0816.31006
[53] H. Matsumura. Commutative ring theory, volume 8 of Cambridge Studies in Advanced Mathematics. Cambridge university press, 1989. · Zbl 0666.13002
[54] McKinnon, D., An arithmetic analogue of Bezout’s theorem, Compos. Math., 126, 2, 147-155 (2001) · Zbl 1017.14008
[55] J. M. McNamee and V. Y. Pan. Numerical Methods for Roots of Polynomials, Part II, volume 16 of Studies in Computational Mathematics. Elsevier, 2013.
[56] Mourrain, B.; Pan, VY; Ruatta, O., Accelerated solution of multivariate polynomial systems of equations, SIAM J. Comput., 32, 2, 435-454 (2003) · Zbl 1030.65051
[57] B. Mourrain and Ph. Trébuchet. Solving projective complete intersection faster. In Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation, ISSAC ’00, pages 234-241. New York, NY, USA, 2000. ACM. · Zbl 1326.68363
[58] B. Mourrain and Ph. Trébuchet. Generalized normal forms and polynomial system solving. In Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation, ISSAC ’05, pages 253-260. New York, NY, USA, 2005. ACM. · Zbl 1360.68947
[59] B. Mourrain and Ph. Trébuchet. Border basis representation of a general quotient algebra. In Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation, ISSAC ’12, pages 265-272. New York, NY, USA, 2012. ACM. · Zbl 1323.68618
[60] A. K. Narayanan. Fast computation of isomorphisms between finite fields using elliptic curves. In L. Budaghyan and F. Rodríguez-Henríquez, editors, Arithmetic of Finite Fields. 7th International Workshop, WAIFI 2018, Bergen, Norway, June 14-16, 2018, Revised Selected Papers, volume 11321 of Lecture Notes in Comput. Sci., pages 74-91. Springer, Cham, 2018. · Zbl 1446.11212
[61] C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. · Zbl 0833.68049
[62] Philippon, P., Sur des hauteurs alternatives. I., Math. Ann., 289, 1, 255-283 (1991) · Zbl 0726.14017
[63] Poteaux, A.; Schost, É., On the complexity of computing with zero-dimensional triangular sets, J. Symbolic Comput., 50, 110-138 (2013) · Zbl 1332.68300
[64] Schönhage, A., Schnelle Berechnung von Kettenbruchentwicklungen, Acta Informatica, 1, 2, 139-144 (1971) · Zbl 0223.68008
[65] Schönhage, A.; Grotefeld, AFW; Vetter, E., Fast algorithms: A multitape Turing machine implementation (1994), Mannheim: B. I. Wissenschaftsverlag, Mannheim · Zbl 0853.68108
[66] Schwartz, JT, Fast probabilistic algorithms for verification of polynomial identities, J. ACM, 27, 4, 701-717 (1980) · Zbl 0452.68050
[67] Shoup, V., New algorithms for finding irreducible polynomials over finite fields, Math. Comp., 54, 189, 435-447 (1990) · Zbl 0712.11077
[68] P. S. Wang. A p-adic algorithm for univariate partial fractions. In Proceedings of the Fourth ACM Symposium on Symbolic and Algebraic Computation, SYMSAC ’81, pages 212-217. New York, NY, USA, 1981. ACM.
[69] R. Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings EUROSAM’ 79, number 72 in Lect. Notes Comput. Sci., pages 216-226. Springer-Verlag, 1979. · Zbl 0418.68040
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.