×

zbMATH — the first resource for mathematics

A Gröbner free alternative for polynomial system solving. (English) Zbl 1003.12005
Let \(f_1,\dots, f_n\), \(g\in \mathbb{Q}[x_1,\dots, x_n]\) such that \(f_1=\cdots= f_n= 0\), \(g\neq 0\) has only finitely many solutions over \(\mathbb{C}\). The aim is to compute a representation of the solution set in the form \[ q(T)=0, \qquad \left\{ \begin{matrix} x_1= v_1(T)\\ \vdots\\ x_n= v_n(T) \end{matrix}\right., \tag{1} \] where \(q\) is a univariate polynomial over \(\mathbb{Q}\) and \(v_i\), \(1\leq i\leq n\), are univariate rational functions over \(\mathbb{Q}\). The algorithm presented is incremental in \(n\) such that the \(i\)th step solves \(f_1=\cdots= f_i= 0\) for \(x_{n-i+1},\dots, x_n\). For each \(i\), the algorithm uses Newton-Hensel lifting of \(x_{n-i}\) followed by intersection with the solution set of \(f_{i+1}=0\).
Representation (1) is related to one first used by Kronecker at the end of the 19th century, which has been widely used to obtain complexity results in the zero-dimensional case. In practice, the representation is normally computed from a Gröbner basis. Kronecker’s approach was rediscovered in 1995 and improved by M. Giusti, J. Heintz, J. E. Morais and L. M. Pardo, C. R. Acad. Sci., Paris, Sér. I 325, 1223-1228 (1997; Zbl 0893.68144)]. The present algorithm avoids the use of straight-line programs and needs only polynomials in at most two variables; geometrically it computes the intersection of two curves.
Kronecker’s representation of geometric resolutions leads to lower total degree complexity in the positive-dimensional case. The use of a global Newton iterator avoids the computation of geometric resolutions of intermediate varieties. Kronecker’s simple technique to intersect a variety by a hypersurface avoids primitive element computations in two variables. The cost of integer manipulation is minimized by extensive use of modular arithmetic.
The main complexity result is contained in the following theorem, in which \[ M(n)= O(n\log^2(n) \log\log(n)) \] and \(\Omega<4\): Let \(\mathbb{K}\) be a field of characteristic zero, and let \(f_1,\dots, f_n\), \(g\in \mathbb{K}[x_1,\dots, x_n]\) be polynomials of degree at most \(d\) given by a straight-line program of size at most \(L\), such that \(f_1,\dots, f_n\) defines a reduced regular sequence in the open subset \(\{g\neq 0\}\). The geometric resolution of the variety \({\mathcal V}(f_1,\dots, f_n)\setminus{\mathcal V}(g)\) can be computed with \(O(n(nL+ n^\Omega) (M(d\delta))^2)\) arithmetic operations in \(\mathbb{K}\), where \(\delta= \max(\deg({\mathcal V}_1),\dots, \deg({\mathcal V}_{n-1}))\). There is a probabilistic algorithm performing this computation. Its probability of returning correct results relies on choices of elements of \(\mathbb{K}\). Choices for which the result is not correct are enclosed in strict algebraic subsets.
The algorithm presented does not greatly improve the worst-case complexity for dense polynomials. It works best when the complexity of evaluation of the input polynomials is small or the hypersurface \(g=0\) contains several components of each \({\mathcal V}_i\), i.e. \(\delta\ll d^n\). If \(\mathbb{K}= \mathbb{Q}\) then the bit-complexity for computation modulo a “lucky prime” is \[ O((nL+ n^\Omega) M(\deg(q)) M(\eta)), \] where \(\eta\) is the bit-size of the integers in the polynomials involved. This modular solution is then lifted to give a resolution in \(\mathbb{Q}\).
The algorithm has been implemented in Magma as a package called Kronecker. Roughly speaking, its performance is between that of Gröbner basis computations using grevlex and lex orderings. The theory and algorithms are presented in detail, and precise running time comparisons are given for polynomial systems with a range of numbers of variables and heights (coefficient sizes).

MSC:
12Y05 Computational aspects of field theory and polynomials (MSC2010)
68W30 Symbolic computation and algebraic computation
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
14Q99 Computational aspects in algebraic geometry
68W40 Analysis of algorithms
PDF BibTeX Cite
Full Text: DOI
References:
[1] Magma, http://www.maths.usyd.edu.au:8000/u/magma/. · Zbl 1151.11064
[2] Medicis, http://www.medicis.polytechnique.fr/.
[3] Abdeljaoued, J., Algorithmes rapides pour le calcul du polynôme caractéristique, (1997), Université de Franche-Comté Besançon
[4] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading · Zbl 0207.01701
[5] Almeida, M.; D’Alfonso, L.; Solernó, P., On the degrees of bases of free modules over a polynomial ring, Math. Z, 1-24, (1998)
[6] Alonso, M.E.; Becker, E.; Roy, M.-F.; Wörmann, T., Zeroes, multiplicities and idempotents for zerodimensional systems, Algorithms in algebraic geometry and applications, Proceedings of MEGA ’94, Progress in mathematics, 142, (1996), Birkhäuser Basel, p. 1-15
[7] Armendáriz, I.; Solernó, P., On the computation of the radical of polynomial complete intersection ideals, (), 106-119 · Zbl 0896.13022
[8] Baur, W.; Strassen, V., The complexity of partial derivatives, Theoret. comput. sci, 22, 317-330, (1983) · Zbl 0498.68028
[9] Berkowitz, S.J., On computing the determinant in small parallel time using a small number of processors, Inform. proc. lett, 18, 147-150, (1984) · Zbl 0541.68019
[10] Bini, D.; Pan, V., Polynomial and matrix computations, Progress in theoretical computer science, (1994), Birkhäuser Boston/Basel/Berlin
[11] Borodin, A.; Munro, J., The computational complexity of algebraic and numeric problems, (1972), Elsevier Amsterdam
[12] Bosma, W.; Cannon, J.; Playoust, C., The magma algebra system I: the user language, J. symbolic comput, 24, (1997) · Zbl 0898.68039
[13] Bunch, J.; Hopcroft, J., Triangular factorization and inversion by fast matrix multiplication, Math. comp, 28, 231-236, (1974) · Zbl 0276.15006
[14] Bürgisser, P.; Clausen, M.; Shokrolahi, M.A., Algebraic complexity theory, (1997), Springer-Verlag New York/Berlin
[15] Caniglia, L.; Galligo, A.; Heintz, J., Borne simple exponentielle pour LES degrés dans le théorème des zéros sur un corps de caractéristique quelconque, C.R. acad. sci. Paris, 307, 255-258, (1988) · Zbl 0686.14001
[16] Cannon, J.; Playoust, C., Magma: A new computer algebra system, Euromath bull, 2, 113-144, (1996)
[17] J. Canny, Some algebraic and geometric problems in PSPACE, in Proceedings, 20 ACM STOC, 1988, pp. 460-467.
[18] Castro, D.; Giusti, M.; Heintz, J.; Matera, G.; Pardo, L.M., Data structures and smooth interpolation procedures in elimination theory, Manuscript of facultad de ciencias, (1999)
[19] A. L. Chistov, and, D. Y. Grigoriev, Polynomial-time factoring of multi-variable polynomials over a global field, LOMI preprint, E-5-82, Steklov Institute, Leningrad, 1982.
[20] Collart, S.; Kalkbrener, M.; Mall, D., Converting bases with the Gröbner walk, J. symbolic comput, 24, 465-469, (1997) · Zbl 0908.13020
[21] D. Coppersmith and S. Winograd, Matrix multiplications via arithmetic progression, in 19th ACM STOC, 1987, pp. 1-6.
[22] Csanky, L., Fast parallel matrix inversion algorithms, SIAM J. comput, 5, 618-623, (1976) · Zbl 0353.68063
[23] Davenport, J.; Siret, Y.; Tournier, E., Calcul formel: systèmes et algorithmes de manipulations algébriques, (1987), Masson Paris
[24] Dixon, J., Exact solution of linear equations using p-adic expansions, Numer. math, 40, 137-141, (1982) · Zbl 0492.65016
[25] J.-C. Faugère, and, F. Rouillier, Mupad interface for gb/realsolving, http://www.loria.fr/rouillie/RSDoc/mupdoc/mupdoc.html/, 1998.
[26] Faugère, J.-C., GB reference manual, Litp, (1995)
[27] Faugère, J.-C., GB: state of GB+tutorial, Litp, (1997)
[28] 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, 329-344, (1993) · Zbl 0805.13007
[29] C. M. Fiduccia, A rational view of the fast Fourier transform, in, 25th Allerton Conf. Comm, Control and Computing, 1987.
[30] Fulton, W., Intersection theory, Ergebnisse der Mathematik, 3, (1984), Springer-Verlag New York/Berlin · Zbl 0541.14005
[31] Geddes, K.O.; Czapor, S.R.; Labahn, G., Algorithms for computer algebra, (1994), Kluwer Academic Dordrecht
[32] Gianni, P.; Mora, T., Algebraic solution of systems of polynomial equations using Gröbner bases, Applied algebra, algebraic algorithms and error correcting codes, Proceedings of AAECC-5, Lecture notes in comput. sci, 356, (1989), Springer-Verlag New York/Berlin, p. 247-257
[33] Giusti, M.; Hägele, K.; Heintz, J.; Morais, J.E.; Montaña, J.L.; Pardo, L.M., Lower bounds for Diophantine approximation, Proceedings of MEGA ’96, (1997), p. 277-317 · Zbl 0871.68101
[34] Giusti, M.; Hägele, K.; Lecerf, G.; Marchand, J.; Salvy, B., Computing the dimension of a projective variety: the projective Noether Maple package, J. symbolic comput, 30, 291-307, (2000) · Zbl 0963.68235
[35] Giusti, M.; Heintz, J., La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial, (), 216-256 · Zbl 0829.14029
[36] Giusti, M.; Heintz, J.; Morais, J.E.; Morgenstern, J.; Pardo, L.M., Straight-line programs in geometric elimination theory, J. pure appl. algebra, 124, 101-146, (1998) · Zbl 0944.12004
[37] Giusti, M.; Heintz, J.; Morais, J.E.; Pardo, L.M., When polynomial equation systems can be solved fast?, (), 205-231 · Zbl 0902.12005
[38] 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, 325, 1223-1228, (1997) · Zbl 0893.68144
[39] Giusti, M.; Heintz, J.; Sabia, J., On the efficiency of effective nullstellensätze, Comput. complexity, 3, 56-95, (1993) · Zbl 0824.68051
[40] Hägele, K., Intrinsic height estimates for the nullstellensatz, (1998), Universidad de Cantabria Santander
[41] K. Hägele, and, J. L. Montaña, Polynomial random test for the equivalence problem of integers given by arithmetic circuits, preprint 4/97, Depto. Matemáticas, Universidad de Cantabria, Santander, Spain, January 1997.
[42] Hägele, K.; Morais, J.E.; Pardo, L.M.; Sombra, M., On the intrinsic complexity of the arithmetic nullstellensatz, () · Zbl 0971.14042
[43] Heintz, J., Definability and fast quantifier elimination in algebraically closed fields, Theoret. comput. sci, 24, 239-277, (1983) · Zbl 0546.03017
[44] Heintz, J., On the computational complexity of polynomials and bilinear mappings: A survey, Applied algebra, algebraic algorithms and error correcting codes, Proceedings of AAECC-5, Lecture notes in comput. sci, 356, (1989), Springer-Verlag New York/Berlin, p. 269-300
[45] J. Heintz, G. Matera, and, A. Waissbein, On the time-space complexity of geometric elimination procedures, manuscript, Universidad Favaloro, Buenos Aires, Argentina, 1999. · Zbl 0977.68101
[46] Heintz, J.; Roy, M.-F.; Solernó, P., Sur la complexité du principe de tarski – seidenberg, Bull. soc. math. France, 118, 101-126, (1990) · Zbl 0767.03017
[47] Kobayashi, H.; Fujise, T.; Furukawa, A., Solving systems of algebraic equations by general elimination method, J. symbolic comput, 5, 303-320, (1988) · Zbl 0648.12017
[48] König, J., Einleitung in die allgemeine theorie der algebraischen gröszen, (1903), Teubner Leipzig · JFM 34.0093.02
[49] Krick, T.; Pardo, L.M., Une approche informatique pour l’approximation diophantienne, C.R. acad. sci. Paris, 318, 407-412, (1994) · Zbl 0814.14050
[50] Krick, T.; Pardo, L.M., A computational method for Diophantine approximation, (), 193-254 · Zbl 0878.11043
[51] Kronecker, L., Grundzüge einer arithmetischen theorie der algebraischen grössen, J. reine angew. math, 92, 1-122, (1882) · JFM 14.0038.02
[52] Kruppa, E., Zur ermittlung eines objektes aus zwei perspektiven mit innerer orientierung, Sitz.-ber. akad. wiss. wien. math. naturw. kl, (1913) · JFM 45.0776.04
[53] Kunz, E., Introduction to commutative algebra and algebraic geometry, (1985), Birkhäuser Basel
[54] Lakshman, Y.N.; Lazard, D., On the complexity of zero-dimensional algebraic systems, Effective methods in algebraic geometry, Progress in mathematics, 94, (1991), Birkhäuser Basel, p. 217-225 · Zbl 0733.13015
[55] G. Lecerf, Kronecker, a package for Magma for polynomial system solving, UMS MEDICIS, Laboratoire GAGE, http://www.gage.polytechnique.fr/lecerf/software/kronecker, 1999.
[56] Leverrier, U.J.J., Sur LES variations séculaires des éléments elliptiques des sept planètes principales: mercure, Vénus, la terre, Mars, Jupiter, saturne et uranus, J. math. pures appl, 4, 220-254, (1840)
[57] T. Lickteig and M.-F. Roy, Sylvester-Habicht sequences and fast Cauchy index computation, in Calcolo 33, 1996, pp. 337-371.
[58] Macaulay, F.S., The algebraic theory of modular systems, (1916), Cambridge Univ. Press Cambridge · Zbl 0802.13001
[59] Matera, G., Sobre la complejidad en espacio y tiempo de la eliminación geométrica, (1997), Universidad de Buenos Aires
[60] Maybank, S.; Faugeras, O., A theory of self-calibration of a moving camera, Internat. J. comput. vision, 8, 123-151, (1992)
[61] R. Moenck and A. B. Borodin, Fast computation of GCD’s, in 5th Annual ACM Symposium on Theory of Computing, 1973, pp. 142-151.
[62] Morais, J.E., Resolución eficaz de sistemas de ecuaciones polinomiales, (1997), Universidad de Cantabria Santander
[63] Nussbaumer, H.J., Fast polynomial transform algorithms for digital convolutions, IEEE trans. acoustic speech signal proc, 28, 205-215, (1980) · Zbl 0524.65093
[64] Pardo, L.M., How lower and upper complexity bounds meet in elimination theory, (), 33-69 · Zbl 0899.68054
[65] Renegar, J., On the computational complexity and geometry of the first-order theory of the reals, part I, J. symbolic comput, 13, 255-299, (1992) · Zbl 0763.68042
[66] Rouillier, F., Algorithmes efficaces pour l’étude des zéros réels des systèmes polynomiaux, (May 1996), Université de Rennes I
[67] Rouillier, F., Solving zero-dimensional systems through the rational univariate representation, Appl. algebra engrg. comm. comput, 9, 433-461, (1999) · Zbl 0932.12008
[68] Sabia, J.; Solernó, P., Bounds for traces in complete intersections and degrees in the nullstellensatz, Appl. algebra engrg. comm. comput, 6, 353-376, (1996) · Zbl 0844.14018
[69] Schönhage, A., Schnelle berechnung von kettenbruchentwicklungen, Acta inform, 1, 139-144, (1971) · Zbl 0223.68008
[70] Schönhage, A.; Strassen, V., Schnelle multiplikation großer zahlen, Computing, 7, 281-292, (1971) · Zbl 0223.68007
[71] Schönhage, A.; Strassen, V., Schnelle multiplikation von polynomen über Körpern der charakteristik 2, Acta inform, 7, 395-398, (1977) · Zbl 0362.65011
[72] Schwartz, J.T., Fast probabilistic algorithms for verification of polynomial identities, J. assos. comput. Mach, 27, 701-717, (1980) · Zbl 0452.68050
[73] Sieveking, M., An algorithm for division of power series, Computing, 10, 153-156, (1972) · Zbl 0251.68023
[74] Smale, S., The fundamental theorem of algebra and complexity theory, Bull. amer. math. soc, 4, 1-36, (1981) · Zbl 0456.12012
[75] S. Smale, Algorithms for solving equations, in Proceedings of the International Congress of Mathematics, Berkeley, CA, 1986, pp. 172-195.
[76] Stoß, H.-J., On the representation of rational functions of bounded complexity, Theoret. comput. sci, 64, 1-13, (1989) · Zbl 0679.68099
[77] V. Strassen, Berechnung und Programm, I, II, Acta Inform.11972, 320-355, 21973, 64-79.
[78] Strassen, V., Die berechnungskomplexität von elementarsymmetrischen funktionen und von interpolationskoeffizienten, Numer. math, 20, 238-251, (1973) · Zbl 0251.65036
[79] TERA Development Group, A (hopefully) efficient polynomial equation system solver, manuscript, gmatera@mate.dm.uba.ar, 1998.
[80] Mupad User’s manual—mupad version 1.2.2, (1996), Wiley Chichester/New York · Zbl 0877.68069
[81] Vogel, W., Results on Bézout’s theorem, (1984), Springer-VerlagTata Institute of Fundamental Research New York/Berlin
[82] von zur Gathen, J., Parallel arithmetic computations: A survey, (), 93-112 · Zbl 0616.68037
[83] Wadler, P., Deforestation: transforming programs to eliminate trees, Theoret. comput. sci, 73, 231-248, (1990) · Zbl 0701.68013
[84] Weispfenning, V.; Becker, T., Groebner bases: A computational approach to commutative algebra, Graduate texts in mathematics, 141, (1993), Springer-Verlag New York/Berlin
[85] Zippel, R., Probabilistic algorithms for sparse polynomials, Proceedings EUROSAM ’79, Lecture notes in comput. sci, 72, (1979), Springer-Verlag New York, p. 216-226
[86] Zippel, R., Effective polynomial computation, Ecs 241, (1993), Kluwer Academic Dordrecht
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.