×

Kronecker’s and Newton’s approaches to solving: a first comparison. (English) Zbl 1013.68296

Summary: These pages are a first attempt to compare the efficiency of symbolic and numerical analysis procedures that solve systems of multivariate polynomial equations. In particular, we compare Kronecker’s solution (from the symbolic approach) with approximate zero theory (introduced by S. Smale as a foundation of numerical analysis). For this purpose we show upper and lower bounds of the bit length of approximate zeros. We also introduce efficient procedures that transform local Kronecker solutions into approximate zeros and conversely. As an application of our study we exhibit an efficient procedure to compute splitting field and Lagrange resolvent of univariate polynomial equations. We remark that this procedure is obtained by a convenient combination of both approaches (numeric and symbolic) to multivariate polynomial solving.

MSC:

68W30 Symbolic computation and algebraic computation
68Q25 Analysis of algorithms and problem complexity
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W05 Nonnumerical algorithms
65H05 Numerical computation of solutions to single equations
12Y05 Computational aspects of field theory and polynomials (MSC2010)

Software:

ECPP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adleman, L. M.; Huang, M.-D. A., Primality Testing and Abelian Varieties over Finite Fields (1992), Springer-Verlag: Springer-Verlag Berlin · Zbl 0744.11065
[2] Artin, E., Algebraic Numbers and Algebraic Functions, I (1951), New York UniversityInstitute for Mathematics and Mechanics: New York UniversityInstitute for Mathematics and Mechanics New York · Zbl 0054.02101
[3] Atkin, A. O.L.; Morain, F., Elliptic curves and primality proving, Math. Comp., 61, 29-68 (1993) · Zbl 0792.11056
[4] Balcázar, J. L.; Dı́az, J.; Gabarró, J., Structural Complexity, I. Structural Complexity, I, EATCS, 11 (1988), Springer-Verlag: Springer-Verlag New York/Berlin
[5] Bernstein, D. N., The number of roots of a system of equations, Funktsional Anal. i Prilozhen., 9, 1-4 (1975)
[6] Blum, L.; Cucker, F.; Shub, M.; Smale, S., Algebraic settings for the problem “\(p\)≠np?”, The Mathematics of Numerical Analysis, Park City, UT, 1995 (1996), Amer. Math. Soc: Amer. Math. Soc Providence, p. 125-144 · Zbl 0856.68068
[7] Blum, L.; Cucker, F.; Shub, M.; Smale, S., Complexity and Real Computation (1988), Springer-Verlag: Springer-Verlag New York
[8] Bombieri, E.; Van der Poorten, A. J.; Vaaler, J. D., Effective measures of irrationality for cubic extensions of number fields, Ann. Scuola Norm. Sup. Pisa Cl. Sci. (4), 23, 211-248 (1996) · Zbl 0879.11035
[9] J.-B. Bost, H. Gillet, and, C. Soulé, Heights of projective varieties and positive green forms, manuscript, I.H.E.S, 1993.; J.-B. Bost, H. Gillet, and, C. Soulé, Heights of projective varieties and positive green forms, manuscript, I.H.E.S, 1993.
[10] Camion, P. F., Factorisation des polynômes de \(\textbf{f}_q[X]\), Rev. CETHEDEC Cahier, 2, 5-21 (1982)
[11] Camion, P. F., Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials, IEEE Trans. Inform. Theory, 29, 378-385 (1983) · Zbl 0513.12015
[12] Cantor, D. G.; Zassenhaus, H., A new algorithm for factoring polynomials over finite fields, Math. Comp., 36, 587-592 (1981) · Zbl 0493.12024
[13] Cassels, J. W.S., An Introduction to the Geometry of Numbers (1997), Springer-Verlag: Springer-Verlag Berlin · Zbl 0866.11041
[14] D. Castro, M. Giusti, J. Heintz, G. Matera, and, L. M. Pardo, Data structures and smooth interpolation procedures in elimination theory, manuscript, 1999.; D. Castro, M. Giusti, J. Heintz, G. Matera, and, L. M. Pardo, Data structures and smooth interpolation procedures in elimination theory, manuscript, 1999.
[15] Ciarlet, P. G., Introduction à l’analyse numérique matricielle et à l’optimisation (1982), Masson: Masson Paris · Zbl 0488.65001
[16] J. P. Dedieu, and, M. Shub, Newton’s method for overdetermined systems of equations, Math. Comp, in press.; J. P. Dedieu, and, M. Shub, Newton’s method for overdetermined systems of equations, Math. Comp, in press. · Zbl 0949.65061
[17] Dedieu, J. P., Approximate solutions of numerical problems, condition number analysis and condition number theorem, The Mathematics of Numerical Analysis, Park City, UT, 1995 (1996), Amer. Math. Soc: Amer. Math. Soc Providence, p. 263-283 · Zbl 0856.65067
[18] Dedieu, J. P., Condition number analysis for sparse polynomial systems, Foundations of Computational Mathematics, Rio de Janeiro, 1997 (1997), Springer-Verlag: Springer-Verlag Berlin, p. 75-101 · Zbl 0869.65036
[19] Dedieu, J. P., Condition operators, condition numbers, and condition number theory for the generalized eigenvalue problem, Linear Algebra Appl., 263, 1-24 (1997) · Zbl 0920.15001
[20] Dedieu, J. P., Estimations for the separation number of a polynomial system, J. Symbolic Comput., 24, 683-693 (1997) · Zbl 0910.65031
[21] J. P. Dedieu, and, M. Shub, On simple double zeros and badly conditioned zeros of analytic functions of \(n\); J. P. Dedieu, and, M. Shub, On simple double zeros and badly conditioned zeros of analytic functions of \(n\) · Zbl 0965.65071
[22] Dedieu, J. P.; Smale, S., Some lower bounds for the complexity of continuation methods, J. Complexity, 14, 454-465 (1998) · Zbl 0918.65038
[23] Demazure, M., Catastrophes et Bifurcations (1989), Ellipses-X École Polytechnique · Zbl 0907.58002
[24] Dixon, J., Exact solution of linear equations using p-adic expansions, Numer. Math., 40, 137-141 (1982) · Zbl 0492.65016
[25] Ducos, L., Effectivité en Théorie de Galois, Sous-resultants (1997), Université de Poitiers
[26] Eckardt, C.; Young, G., The approximation of one matrix by another of lower rank, Psychometrika, 1, 211-218 (1936) · JFM 62.1075.02
[27] Fitchas, N.; Giusti, M.; Smietanski, F., Sur la complexité du théorème des zéros, (Guddat, J., Approximation and Optimization in the Caribbean II, Proceedings 2nd Int. Conf. on Non-Linear Optimization and Approximation. Approximation and Optimization in the Caribbean II, Proceedings 2nd Int. Conf. on Non-Linear Optimization and Approximation, Approximation and Optimization, 8 (1995), Peter Lange Verlag: Peter Lange Verlag Frankfurt am Main), 247-329 · Zbl 0868.12008
[28] Fulton, W., Intersection Theory. Intersection Theory, Ergebnisse der Mathematik, 3 (1984), Springer-Verlag: Springer-Verlag New York/Berlin · Zbl 0541.14005
[29] Giusti, M.; Hägele, K.; Heintz, J.; Morais, J. E.; Montaña, J. L.; Pardo, L. M., Lower bounds for diophantine approximation, J. Pure Appl. Algebra, 117, 118, 277-317 (1997) · Zbl 0871.68101
[30] Giusti, M.; Heintz, J., Algorithmes—disons rapides—pour la décomposition d’une variété algébrique en composantes irréductibles et équidimensionelles, (Mora, T.; Traverso, C., Proceedings of MEGA’90. Proceedings of MEGA’90, Progress in Mathematics, 94 (1991), Birkhäuser: Birkhäuser Basel), 169-194 · Zbl 0755.14018
[31] 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, (Eisenbud, D.; Robbiano, L., Computational Algebraic Geometry and Commutative Algebra. Computational Algebraic Geometry and Commutative Algebra, Symposia Matematica, 34 (1993), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 216-256 · Zbl 0829.14029
[32] 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
[33] Giusti, M.; Heintz, J.; Morais, J. E.; Pardo, L. M., When polynomial equation systems can be solved fast?, (Cohen, G.; Giusti, H.; Mora, T., Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings AAECC-11. Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings AAECC-11, Lecture Notes in Comput. Sci., 948 (1995), Springer-Verlag: Springer-Verlag New York/Berlin), 205-231 · Zbl 0902.12005
[34] 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
[35] M. Giusti, and, E. Schost, Solving some over-determined systems, in, Proc. ISSAC, 1999, in press.; M. Giusti, and, E. Schost, Solving some over-determined systems, in, Proc. ISSAC, 1999, in press.
[36] Hägele, K., Intrinsic Height Estimates for the Nullstellensatz (1998), Universidad de Cantabria: Universidad de Cantabria Santander
[37] 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.; 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.
[38] Hägele, K.; Morais, J. E.; Pardo, L. M.; Sombra, M., On the intrinsic complexity of arithmetic nullstellensatz, J. Pure Appl. Algebra, 146, 103-183 (2000) · Zbl 0971.14042
[39] Heintz, J., Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci., 24, 239-277 (1983) · Zbl 0546.03017
[40] 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. Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings of AAECC-5, Lecture Notes in Comput. Sci., 356 (1989), Springer-Verlag: Springer-Verlag New York/Berlin, p. 269-300
[41] Heintz, J.; Schnorr, C. P., Testing polynomials which are easy to compute, Logic and Algorithmic. Logic and Algorithmic, Monographie de l’Enseignement Mathématique, 30 (1982), p. 237-254 · Zbl 0483.68043
[42] Ibarra, O. H.; Moran, S., Equivalence of straight-line programs, J. Assoc. Comput. Mach., 30, 217-228 (1983) · Zbl 0497.68013
[43] Kaltofen, E., Polynomial factorization 1982-1986, Computers in Mathematics, Stanford, CA, 1986 (1990), Dekker: Dekker New York, p. 285-309 · Zbl 0773.11078
[44] Kaltofen, E., Polynomial factorization 1987-1991, (Simon, I., Proceedings of the 1st Latin American Symposium on Theoretical Informatics LATIN ’92, São P.o, Brazil, April 1992. Proceedings of the 1st Latin American Symposium on Theoretical Informatics LATIN ’92, São P.o, Brazil, April 1992, Lecture Notes in Comput. Sci., 583 (1992), Springer-Verlag: Springer-Verlag New York/Berlin), 294-313
[45] Kannan, R.; Lenstra, A. K.; Lovasz, L., Polynomial factorization and non-randomness of bits of algebraic and some transcendental numbers, Proceedings of the 16th Ann. ACM Symposium on Theory of Computing, Washington, DC (1984), ACM Press: ACM Press New York, p. 191-200
[46] Kannan, R.; Lenstra, A. K.; Lovász, L., Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers, Math. Comp., 50, 235-250 (1988) · Zbl 0654.12001
[47] Kim, M.-H., Computational Complexity of the Euler Type Algorithms for the Roots of Complex Polynomials (1985), The City University of New York
[48] Kim, M.-H., On approximate zeros and rootfinding algorithms for a complex polynomial, Math. Comp., 51, 707-719 (1988) · Zbl 0699.30031
[49] Kim, M.-H., Topological complexity of a root finding algorithm, J. Complexity, 5, 331-344 (1989) · Zbl 0689.65030
[50] König, J., Einleitung in die allgemeine Theorie der algebraischen Grözen (1903), Teubner: Teubner Leipzig · JFM 34.0093.02
[51] Krick, T.; Pardo, L. M., Une approche informatique pour l’approximation diophantienne, C.R. Acad. Sci. Paris, 318, 407-412 (1994) · Zbl 0814.14050
[52] Krick, T.; Pardo, L. M., A computational method for diophantine approximation, (González-Vega, L.; Recio, T., Algorithms in Algebraic Geometry and Applications, Proceedings of MEGA’94. Algorithms in Algebraic Geometry and Applications, Proceedings of MEGA’94, Progress in Mathematics, 143 (1996), Birkhäuser: Birkhäuser Basel), 193-254 · Zbl 0878.11043
[53] Kronecker, L., Grundzüge einer arithmetischen theorie de algebraischen grössen, J. Reine Angew. Math., 92, 1-122 (1882) · JFM 14.0038.02
[54] Kushnirenko, A. G., Newton polytopes and the bezout theorem, Funktsional. Anal. i Prilozhen., 10 (1976) · Zbl 0341.32001
[55] Landau, S., Factoring polynomials over algebraic number fields, SIAM J. Comput., 14, 184-195 (1985) · Zbl 0565.12002
[56] Landau, S.; Miller, G. L., Solvability by radicals is in polynomial time, J. Comput. System Sci., 30, 179-208 (1985) · Zbl 0586.12002
[57] Lang, S., Fundamentals of Diophantine Geometry (1983), Springer-Verlag: Springer-Verlag New York/Berlin · Zbl 0528.14013
[58] Lang, S., Survey of Diophantine Geometry (1997), Springer-Verlag: Springer-Verlag New York/Berlin
[59] Lenstra, A. K., Factoring polynomials over algebraic number fields, Computer Algebra, London, 1983 (1983), Springer-Verlag: Springer-Verlag Berlin, p. 245-254 · Zbl 0539.68030
[60] Lenstra, A. K., Polynomial factorization by root approximation, (Fitch, J., Proceedings of the 3rd International Symposium on Symbolic and Algebraic Computation EUROSAM 84, Cambridge, England, July 9-11, 1984. Proceedings of the 3rd International Symposium on Symbolic and Algebraic Computation EUROSAM 84, Cambridge, England, July 9-11, 1984, Lecture Notes in Comput. Sci., 174 (1984), Springer-Verlag: Springer-Verlag New York/Berlin), 272-276
[61] Lenstra, A. K.; Lenstra, H. W.; Lovasz, L., Technical Report (1982)
[62] Lenstra, A. K.; Lenstra, H. W.; Lovász, L., Factoring polynomials with rational coefficients, Math. Ann., 261, 513-534 (1982) · Zbl 0488.12001
[63] Macauley, F. S., The Algebraic Theory of Modular Systems (1916), Cambridge Univ. Press: Cambridge Univ. Press Cambridge
[64] Malajovich, G., On the Complexity of Path-Following Newton Algorithms for Solving Systems of Polynomial Equations with Integer Coefficients (1993), University of California at Berkeley
[65] Malajovich, G., On generalized newton algorithms: quadratic convergence, path-following and error analysis, Theoret. Comput. Sci., 133, 65-84 (1994) · Zbl 0811.65039
[66] G. Malajovich, Worst possible condition number of polynomial systems, preprint, 1995.; G. Malajovich, Worst possible condition number of polynomial systems, preprint, 1995.
[67] McCarthy, P. J., Algebraic Extensions of Fields (1976), Chelsea: Chelsea New York · Zbl 0143.05802
[68] Mignotte, M., Mathématiques pour le calcul formel (1989), Presses Universitaires de France: Presses Universitaires de France Paris · Zbl 0679.12001
[69] Montaña, J. L.; Morais, J. E.; Pardo, L. M., Lower bounds for arithmetic networks. II. Sum of betti numbers, Appl. Algebra Engrg. Comm. Comput., 7, 41-51 (1996) · Zbl 0844.68069
[70] Montaña, J. L.; Pardo, L. M., Lower bounds for arithmetic networks, Appl. Algebra Engrg. Comm. Comput., 4, 1-24 (1993) · Zbl 0769.68055
[71] Montaña, J. L.; Pardo, L. M.; Recio, T., The non-scalar model of complexity in computational geometry, (Traverso, C.; Mora, T., Effective Methods in Algebraic Geometry, Proceedings of MEGA’90. Effective Methods in Algebraic Geometry, Proceedings of MEGA’90, Progress in Mathematics, 94 (1991), Birkhäuser: Birkhäuser Basel), 347-361 · Zbl 0762.14027
[72] F. Morain, Distributed primality proving and the primality of \((2^3\); F. Morain, Distributed primality proving and the primality of \((2^3\) · Zbl 0779.11063
[73] Morain, F., Elliptic curves, primality proving and some titanic primes, Astérisque, 198-200, 245-251 (1992) · Zbl 0760.11041
[74] Morais, J. E., Resolución eficaz de sistemas de ecuaciones polinomiales (1997), Universidad de Cantabria: Universidad de Cantabria Santander
[75] Pardo, L. M., How lower and upper complexity bounds meet in elimination theory, (Cohen, G.; Giusti, H.; Mora, T., Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Paris, 1995. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Paris, 1995, Lecture Notes in Computer Science, 948 (1995), Springer-Verlag: Springer-Verlag Berlin), 33-69 · Zbl 0899.68054
[76] Philippon, P., Sur des hauteurs alternatives, I, Math. Ann., 289, 255-283 (1991) · Zbl 0726.14017
[77] Philippon, P., Sur des hauteurs alternatives, II, Ann. Inst. Fourier (Grenoble), 44, 1043-1065 (1994) · Zbl 0878.11024
[78] Philippon, P., Sur des hauteurs alternatives, III, J. Math. Pures Appl., 74, 345-365 (1995) · Zbl 0878.11025
[79] Pohst, M.; Zassenhaus, H., Algorithmic Algebraic Number Theory (1989), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0685.12001
[80] Renegar, J., On the worst-case arithmetic complexity of approximating zeros of polynomials, J. Complexity, 3, 90-113 (1987) · Zbl 0642.65031
[81] Rose, H. E., A Course in Number Theory (1994), Clarendon, Oxford Univ. Press: Clarendon, Oxford Univ. Press New York · Zbl 0818.11001
[82] J. Kilian and S. Goldwasser, Almost all primes can be quickly certified, in 18th Annual ACM Symp. on Theory of Computing, 1986, pp. 316-329.; J. Kilian and S. Goldwasser, Almost all primes can be quickly certified, in 18th Annual ACM Symp. on Theory of Computing, 1986, pp. 316-329.
[83] Schmidt, W. M., Diophantine Approximation (1980), Springer-Verlag: Springer-Verlag Berlin · Zbl 0529.10032
[84] Schönhage, A., preliminary report (1981)
[85] A. Schönhage, Equation solving in terms of computational complexity, in, Proceedings of the International Congress of Mathematicians, 1986, Vol, 3, p, 40.; A. Schönhage, Equation solving in terms of computational complexity, in, Proceedings of the International Congress of Mathematicians, 1986, Vol, 3, p, 40.
[86] Schwartz, J. T., Probabilistic algorithms for verification of polynomial identities, ISSAC ’79: Proceedings of Int’l. Symp. on Symbolic and Algebraic Computation. ISSAC ’79: Proceedings of Int’l. Symp. on Symbolic and Algebraic Computation, Lecture Notes in Computer Science, 72 (1979), Springer-Verlag: Springer-Verlag New York/Berlin · Zbl 0452.68050
[87] Shub, M.; Smale, S., Computational complexity: On the geometry of polynomials and a theory of cost, I, Ann. Sci. École Norm. Sup., 18, 107-142 (1985) · Zbl 0603.65027
[88] Shub, M.; Smale, S., Computational complexity: On the geometry of polynomials and a theory of cost, II, SIAM J. Comput., 15, 145-161 (1986) · Zbl 0625.65036
[89] Shub, M.; Smale, S., Complexity of Bézout’s theorem. I. Geometric aspects, J. Amer. Math. Soc., 6, 459-501 (1993) · Zbl 0821.65035
[90] Shub, M.; Smale, S., Complexity of Bézout’s theorem. II. Volumes and probabilities, Proceedings Effective Methods in Algebraic Geometry. Proceedings Effective Methods in Algebraic Geometry, Progress in Mathematics, 109 (1993), Birkhäuser: Birkhäuser Basel, p. 267-285 · Zbl 0851.65031
[91] Shub, M.; Smale, S., Complexity of Bézout’s theorem. III. Condition number and packing, J. Complexity, 9, 4-14 (1993) · Zbl 0846.65018
[92] M. Shub, and, S. Smale, Complexity of Bézout’s theorem. IV. Probability of success, extensions, SIAM J. Numer. Anal, in press.; M. Shub, and, S. Smale, Complexity of Bézout’s theorem. IV. Probability of success, extensions, SIAM J. Numer. Anal, in press. · Zbl 0843.65035
[93] Shub, M.; Smale, S., Complexity of Bézout’s theorem. V. Polynomial time, Theoret. Comput. Sci., 133, 141-164 (1994) · Zbl 0846.65022
[94] Shub, M.; Smale, S., Complexity of Bezout’s theorem. IV. Probability of success and extensions, SIAM J. Numer. Anal., 33, 128-148 (1996) · Zbl 0843.65035
[95] Smale, S., The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. (N.S.), 4, 1-36 (1981) · Zbl 0456.12012
[96] Smale, S., On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc., 13, 87-121 (1985) · Zbl 0592.65032
[97] S. Smale, Algorithms for solving equations, in Proceedings of the International Congress of Mathematicians, Berkeley, CA, 1986, pp. 172-195.; S. Smale, Algorithms for solving equations, in Proceedings of the International Congress of Mathematicians, Berkeley, CA, 1986, pp. 172-195.
[98] Smale, S., Newton’s method estimates from data at one point, The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics, Laramie, WY, 1985 (1986), Springer-Verlag: Springer-Verlag New York, p. 185-196
[99] Sombra, M., Estimaciones para el teorema de ceros de Hilbert (1998), Universidad de Buenos Aires
[100] Strassen, V., Algebraic complexity theory, Handbook of Theoretical Computer Science (1990), Elsevier: Elsevier Amsterdam, p. 634-671
[101] Sturmfels, B., Gröbner Bases and Convex Polytopes. Gröbner Bases and Convex Polytopes, University Lecture Series, 8 (1996), Amer. Math. Soc: Amer. Math. Soc Providence · Zbl 0856.13020
[102] Tyler, S., The Lagrange Spectrum in Projective Space over a Local Field (1994), University of Texas at Austin
[103] Vogel, W., Results on Bézout’s Theorem (1984), Springer-VerlagTata Institute of Fundamental Research: Springer-VerlagTata Institute of Fundamental Research New York/Berlin
[104] Yakoubsohn, J. C., Une constante universelle pour la convergence de la méthode de Newton, C.R. Acad. Sci. Paris Sér. I Math., 320, 385-390 (1995) · Zbl 0830.65042
[105] Yakoubsohn, J. C., A universal constant for the convergence of Newton’s method and an application to the classical homotopy method, Numer. Algorithms, 9, 223-244 (1995) · Zbl 0835.65075
[106] Zariski, O., Algebraic Surfaces (1995), Springer-Verlag: Springer-Verlag New York/Berlin · Zbl 0010.37103
[107] Zariski, O.; Samuel, P., Commutative Algebra (1958), Van Nostrand: Van Nostrand Princeton · Zbl 0121.27801
[108] Zippel, R., Probabilistic algorithms for sparse polynomials, Proceedings EUROSAM’79. Proceedings EUROSAM’79, Lecture Notes in Comput. Sci., 72 (1979), Springer-Verlag: Springer-Verlag New York/Berlin, p. 216-226
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.