research-article

A Gröbner Free Alternative for Polynomial System Solving

Authors:

Grégoire Lecerf,

Bruno SalvyAuthors Info & Claims

Journal of Complexity, Volume 17, Issue 1

Pages 154 - 211

https://doi.org/10.1006/jcom.2000.0571

Published: 01 March 2001 Publication History

Abstract

Given a system of polynomial equations and inequations with coefficients in the field of rational numbers, we show how to compute a geometric resolution of the set of common roots of the system over the field of complex numbers. A geometric resolution consists of a primitive element of the algebraic extension defined by the set of roots, its minimal polynomial, and the parametrizations of the coordinates. Such a representation of the solutions has a long history which goes back to Leopold Kronecker and has been revisited many times in computer algebra. We introduce a new generation of probabilistic algorithms where all the computations use only univariate or bivariate polynomials. We give a new codification of the set of solutions of a positive dimensional algebraic variety relying on a new global version of Newton's iterator. Roughly speaking the complexity of our algorithm is polynomial in some kind of degree of the system, in its height, and linear in the complexity of evaluation of the system. We present our implementation in the Magma system which is called Kronecker in homage to his method for solving systems of polynomial equations. We show that the theoretical complexity of our algorithm is well reflected in practice and we exhibit some cases for which our program is more efficient than the other available software.

References

[1]

Magma, http://www.maths.usyd.edu.au:8000/u/magma/.

[2]

Medicis, http://www.medicis.polytechnique.fr/.

[3]

J. Abdeljaoued, Université de Franche¿Comté, Besançon, 1997.

[4]

A.V. Aho, J.E. Hopcroft, J.D. Ullman, Addison¿Wesley, Reading, 1974.

[5]

M. Almeida, L. D'Alfonso, P. Solernó, On the degrees of bases of free modules over a polynomial ring, Math. Z (1998) 1-24.

[6]

M.E. Alonso, E. Becker, M.-F. Roy, T. Wörmann, Zeroes, multiplicities and idempotents for zerodimensional systems, Birkhäuser, Basel, 1996.

[7]

I. Armendáriz, P. Solernó, On the computation of the radical of polynomial complete intersection ideals, in: Lecture Notes in Comput. Sci, 948, Springer-Verlag, New York/Berlin, 1995, pp. 106-119.

[8]

W. Baur, V. Strassen, The complexity of partial derivatives, Theoret. Comput. Sci, 22 (1983) 317-330.

[9]

S.J. Berkowitz, On computing the determinant in small parallel time using a small number of processors, Inform. Proc. Lett, 18 (1984) 147-150.

Digital Library

[10]

D. Bini, V. Pan, Birkhäuser, Boston/Basel/Berlin, 1994.

[11]

A. Borodin, J. Munro, Elsevier, Amsterdam, 1972.

[12]

W. Bosma, J. Cannon, C. Playoust, The Magma algebra system I: The user language, J. Symbolic Comput, 24 (1997).

[13]

J. Bunch, J. Hopcroft, Triangular factorization and inversion by fast matrix multiplication, Math. Comp, 28 (1974) 231-236.

[14]

P. Bürgisser, M. Clausen, M.A. Shokrolahi, Springer-Verlag, New York/Berlin, 1997.

[15]

L. Caniglia, A. Galligo, J. Heintz, 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 (1988) 255-258.

[16]

J. Cannon, C. Playoust, Magma: A new computer algebra system, Euromath Bull, 2 (1996) 113-144.

[17]

J. Canny, Some algebraic and geometric problems in PSPACE, in Proceedings, 20 ACM STOC, 1988, pp. 460-467.

[18]

D. Castro, M. Giusti, J. Heintz, G. Matera, L.M. Pardo, 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]

S. Collart, M. Kalkbrener, D. Mall, Converting bases with the Gröbner walk, J. Symbolic Comput, 24 (1997) 465-469.

Digital Library

[21]

D. Coppersmith and S. Winograd, Matrix multiplications via arithmetic progression, in 19th ACM STOC, 1987, pp. 1-6.

Digital Library

[22]

L. Csanky, Fast parallel matrix inversion algorithms, SIAM J. Comput, 5 (1976) 618-623.

Digital Library

[23]

J. Davenport, Y. Siret, E. Tournier, Masson, Paris, 1987.

[24]

J. Dixon, Exact solution of linear equations using p-adic expansions, Numer. Math, 40 (1982) 137-141.

Digital Library

[25]

J.-C. Faugère, and, F. Rouillier, Mupad interface for gb/realsolving, http://www.loria.fr/rouillie/RSDoc/mupdoc/mupdoc.html/, 1998.

[26]

J.-C. Faugère, 1995.

[27]

J.-C. Faugère, 1997.

[28]

J.-C. Faugère, P. Gianni, D. Lazard, T. Mora, Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symbolic Comput, 16 (1993) 329-344.

Digital Library

[29]

C. M. Fiduccia, A rational view of the fast Fourier transform, in, 25th Allerton Conf. Comm, Control and Computing, 1987.

[30]

W. Fulton, Springer-Verlag, New York/Berlin, 1984.

[31]

K.O. Geddes, S.R. Czapor, G. Labahn, Kluwer Academic, Dordrecht, 1994.

[32]

P. Gianni, T. Mora, Algebraic solution of systems of polynomial equations using Gröbner bases, Springer-Verlag, New York/Berlin, 1989.

[33]

M. Giusti, K. Hägele, J. Heintz, J.E. Morais, J.L. Montaña, L.M. Pardo, Lower bounds for Diophantine approximation, 1997.

[34]

M. Giusti, K. Hägele, G. Lecerf, J. Marchand, B. Salvy, Computing the dimension of a projective variety: The projective Noether Maple Package, J. Symbolic Comput, 30 (2000) 291-307.

Digital Library

[35]

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, in: Symposia Matematica, 34, Cambridge Univ. Press, Cambridge, 1993, pp. 216-256.

[36]

M. Giusti, J. Heintz, J.E. Morais, J. Morgenstern, L.M. Pardo, Straight-line programs in geometric elimination theory, J. Pure Appl. Algebra, 124 (1998) 101-146.

[37]

M. Giusti, J. Heintz, J.E. Morais, L.M. Pardo, When polynomial equation systems can be solved fast?, in: Lecture Notes in Comput. Sci, 948, Springer-Verlag, New York/Berlin, 1995, pp. 205-231.

[38]

M. Giusti, J. Heintz, J.E. Morais, L.M. Pardo, Le rôle des structures de données dans les problèmes d'élimination, C.R. Acad. Sci. Paris, 325 (1997) 1223-1228.

[39]

M. Giusti, J. Heintz, J. Sabia, On the efficiency of effective Nullstellensätze, Comput. Complexity, 3 (1993) 56-95.

Digital Library

[40]

K. Hägele, Universidad de Cantabria, Santander, 1998.

[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]

K. Hägele, J.E. Morais, L.M. Pardo, M. Sombra, On the intrinsic complexity of the arithmetic Nullstellensatz, in: Proceedings of TERA '97, Córdoba, September 1997.

[43]

J. Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci, 24 (1983) 239-277.

[44]

J. Heintz, On the computational complexity of polynomials and bilinear mappings: A survey, Springer-Verlag, New York/Berlin, 1989.

[45]

J. Heintz, G. Matera, and, A. Waissbein, On the time-space complexity of geometric elimination procedures, manuscript, Universidad Favaloro, Buenos Aires, Argentina, 1999.

[46]

J. Heintz, M.-F. Roy, P. Solernó, Sur la complexité du principe de Tarski¿Seidenberg, Bull. Soc. Math. France, 118 (1990) 101-126.

[47]

H. Kobayashi, T. Fujise, A. Furukawa, Solving systems of algebraic equations by general elimination method, J. Symbolic Comput, 5 (1988) 303-320.

Digital Library

[48]

J. König, Teubner, Leipzig, 1903.

[49]

T. Krick, L.M. Pardo, Une approche informatique pour l'approximation diophantienne, C.R. Acad. Sci. Paris, 318 (1994) 407-412.

[50]

T. Krick, L.M. Pardo, A computational method for Diophantine approximation, in: Progress in Mathematics, 143, Birkhäuser, Basel, 1996, pp. 193-254.

[51]

L. Kronecker, Grundzüge einer arithmetischen Theorie der algebraischen Grössen, J. Reine Angew. Math, 92 (1882) 1-122.

[52]

E. Kruppa, Zur Ermittlung eines Objektes aus zwei Perspektiven mit innerer Orientierung, Sitz.-Ber. Akad. Wiss. Wien. Math. Naturw. Kl (1913).

[53]

E. Kunz, Birkhäuser, Basel, 1985.

[54]

Y.N. Lakshman, D. Lazard, On the complexity of zero-dimensional algebraic systems, Birkhäuser, Basel, 1991.

[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]

U.J.J. Leverrier, 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 (1840) 220-254.

[57]

T. Lickteig and M.-F. Roy, Sylvester-Habicht sequences and fast Cauchy index computation, in Calcolo 33, 1996, pp. 337-371.

[58]

F.S. Macaulay, Cambridge Univ. Press, Cambridge, 1916.

[59]

G. Matera, Universidad de Buenos Aires, 1997.

[60]

S. Maybank, O. Faugeras, A theory of self-calibration of a moving camera, Internat. J. Comput. Vision, 8 (1992) 123-151.

Digital Library

[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]

J.E. Morais, Universidad de Cantabria, Santander, 1997.

[63]

H.J. Nussbaumer, Fast polynomial transform algorithms for digital convolutions, IEEE Trans. Acoustic Speech Signal Proc, 28 (1980) 205-215.

[64]

L.M. Pardo, How lower and upper complexity bounds meet in elimination theory, in: Lecture Notes in Computer Science, 948, Springer-Verlag, Berlin, 1995, pp. 33-69.

[65]

J. Renegar, On the computational complexity and geometry of the first-order theory of the reals, Part I, J. Symbolic Comput, 13 (1992) 255-299.

Digital Library

[66]

F. Rouillier, Université de Rennes I, May 1996.

[67]

F. Rouillier, Solving zero-dimensional systems through the rational univariate representation, Appl. Algebra Engrg. Comm. Comput, 9 (1999) 433-461.

[68]

J. Sabia, P. Solernó, Bounds for traces in complete intersections and degrees in the Nullstellensatz, Appl. Algebra Engrg. Comm. Comput, 6 (1996) 353-376.

Digital Library

[69]

A. Schönhage, Schnelle Berechnung von Kettenbruchentwicklungen, Acta Inform, 1 (1971) 139-144.

Digital Library

[70]

A. Schönhage, V. Strassen, Schnelle Multiplikation großer Zahlen, Computing, 7 (1971) 281-292.

[71]

A. Schönhage, V. Strassen, Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2, Acta Inform, 7 (1977) 395-398.

Digital Library

[72]

J.T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assos. Comput. Mach, 27 (1980) 701-717.

Digital Library

[73]

M. Sieveking, An algorithm for division of power series, Computing, 10 (1972) 153-156.

[74]

S. Smale, The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc, 4 (1981) 1-36.

[75]

S. Smale, Algorithms for solving equations, in Proceedings of the International Congress of Mathematics, Berkeley, CA, 1986, pp. 172-195.

[76]

H.-J. Stoß, On the representation of rational functions of bounded complexity, Theoret. Comput. Sci, 64 (1989) 1-13.

Digital Library

[77]

V. Strassen, Berechnung und Programm, I, II, Acta Inform.11972, 320-355, 21973, 64-79.

[78]

V. Strassen, Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numer. Math, 20 (1973) 238-251.

Digital Library

[79]

TERA Development Group, A (hopefully) efficient polynomial equation system solver, manuscript, [email protected], 1998.

[80]

, Wiley, Chichester/New York, 1996.

[81]

W. Vogel, Springer-VerlagTata Institute of Fundamental Research, New York/Berlin, 1984.

[82]

J. von zur Gathen, Parallel arithmetic computations: A survey, in: Lecture Notes in Comput. Sci, 233, Springer-Verlag, New York/Berlin, 1986, pp. 93-112.

[83]

P. Wadler, Deforestation: Transforming programs to eliminate trees, Theoret. Comput. Sci, 73 (1990) 231-248.

Digital Library

[84]

V. Weispfenning, T. Becker, Springer-Verlag, New York/Berlin, 1993.

[85]

R. Zippel, Probabilistic algorithms for sparse polynomials, Springer-Verlag, New York, 1979.

[86]

R. Zippel, Kluwer Academic, Dordrecht, 1993.

Cited By

Berthomieu JMohr R(2024)Computing Generic Fibers of Polynomial Ideals with FGLM and Hensel LiftingProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669703(307-315)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669703
Duff TLeykin ARodriguez J(2024)u-generation: solving systems of polynomials equation-by-equationNumerical Algorithms10.1007/s11075-023-01590-195:2(813-838)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s11075-023-01590-1
Labahn GRiener CSafey El Din MSchost EVu T(2023)Faster real root decision algorithm for symmetric polynomialsProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597097(452-460)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597097
Show More Cited By

Index Terms

A Gröbner Free Alternative for Polynomial System Solving
1. Mathematics of computing
  1. Discrete mathematics
  2. Mathematical analysis
    1. Nonlinear equations
    2. Numerical analysis
      1. Computations on polynomials
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

On the Complexity Exponent of Polynomial System Solving
Abstract
We present a probabilistic Las Vegas algorithm for solving sufficiently generic square polynomial systems over finite fields. We achieve a nearly quadratic running time in the number of solutions, for densely represented input polynomials. We also ...
Rational Univariate Reduction via toric resultants

We describe algorithms for solving a given system of multivariate polynomial equations via the Rational Univariate Reduction (RUR). We compute the RUR from the toric resultant of the input system. Our algorithms derandomize several of the choices made ...
Computing polynomial resultants: Bezout's determinant vs. Collins' reduced P.R.S. algorithm

Algorithms for computing the resultant of two polynomials in several variables, a key repetitive step of computation in solving systems of polynomial equations by elimination, are studied. Determining the best algorithm for computer implementation ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Complexity

Journal of Complexity Volume 17, Issue 1

March 1, 2001

303 pages

ISSN:0885-064X

Editor:
Joseph F. Traub
Columbia University, New York, NY

Issue’s Table of Contents

Copyright © Academic Press.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 March 2001

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

94
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Berthomieu JMohr R(2024)Computing Generic Fibers of Polynomial Ideals with FGLM and Hensel LiftingProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669703(307-315)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669703
Duff TLeykin ARodriguez J(2024)u-generation: solving systems of polynomials equation-by-equationNumerical Algorithms10.1007/s11075-023-01590-195:2(813-838)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s11075-023-01590-1
Labahn GRiener CSafey El Din MSchost EVu T(2023)Faster real root decision algorithm for symmetric polynomialsProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597097(452-460)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597097
Schost ÉSt-Pierre C(2023)p-adic algorithm for bivariate Gröbner basesProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597086(508-516)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597086
Mora T(2023)Further perspectives on eliminationApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-023-00618-234:5(745-749)Online publication date: 20-Jul-2023
https://dl.acm.org/doi/10.1007/s00200-023-00618-2
Vu TMaza MZhi L(2022)Computing Critical Points for Algebraic Systems Defined by Hyperoctahedral Invariant PolynomialsProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3536181(167-175)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3536181
Bender MMaza MZhi L(2022)Solving Sparse Polynomial Systems using Gröbner Bases and ResultantsProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3535498(21-30)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3535498
Bostan AChyzak FNotarantonio HSafey El Din MMaza MZhi L(2022)Algorithms for Discrete Differential Equations of Order 1Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3535471(101-110)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3535471
Ollivier F(2022)Jacobi’s Bound: Jacobi’s results translated in Kőnig’s, Egerváry’s and Ritt’s mathematical languagesApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-022-00547-634:5(793-885)Online publication date: 25-Mar-2022
https://dl.acm.org/doi/10.1007/s00200-022-00547-6
Lairez PSafey El Din MChyzak FLabahn G(2021)Computing the Dimension of Real Algebraic SetsProceedings of the 2021 International Symposium on Symbolic and Algebraic Computation10.1145/3452143.3465551(257-264)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3452143.3465551
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents