×

Straight-line programs in geometric elimination theory. (English) Zbl 0944.12004

This paper provides the full proofs for M. Giusti, J. Heintz, J. E. Morais and L. M. Pardo [Lect. Notes Comput. Sci. 948, 205-231 (1995; Zbl 0902.12005)]. In comparison with the latter it is expanded in particular what concerns the compression of straight line programs; along many pages however it runs almost word for word as in the cited preliminary conference version.

MSC:

12Y05 Computational aspects of field theory and polynomials (MSC2010)
65H10 Numerical computation of solutions to systems of equations
14Q15 Computational aspects of higher-dimensional varieties
68W30 Symbolic computation and algebraic computation

Citations:

Zbl 0902.12005
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[2] Baur, W.; Strassen, V., The complexity of partial derivatives, Theoret. Comput. Sci., 22, 317-330 (1982) · Zbl 0498.68028
[3] Berenstein, C.; Yger, A., Effective Bézout identities ℚ[\(X_l\),…,\(X_n\)], Acta Math., 166, 69-120 (1991) · Zbl 0724.32002
[4] Berenstein, C.; Yger, A., Une formule de Jacobi et ses conséquences, Ann Sci. E.N.S., \(4^{ieme}\) série, 24, 363-377 (1991) · Zbl 0742.32004
[5] Berkowitz, S. J., On computing the determinant in small parallel time using a small number of processors, (Inf. Proc Lett., 18 (1984)), 147-150 · Zbl 0541.68019
[6] Briançon, J., Sur le degré des relations entre polynômes, C.R. Acad. Sci. Paris Sér. I Math., 297, 553-556 (1982) · Zbl 0586.13016
[7] Brownawell, D. W., Bounds for the degree in the Nullstellensatz, Ann. Math., 126, 577-591 (1987) · Zbl 0641.14001
[8] Caniglia, L.; Galligo, A.; Heintz, J., Borne simplement 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. Sér. I Math., 307, 255-258 (1988) · Zbl 0686.14001
[9] Caniglia, L.; Galligo, A.; Heintz, J., Some new effectivity bounds in computational geometry, (Mora, T., Proc. AAECC-6. Proc. AAECC-6, Lecture Notes in Computer Science, Vol. 357 (1989), Springer: Springer Berlin), 131-152 · Zbl 0685.68044
[10] Canny, J., Some algebraic and geometric problems in PSPACE, (Proc. 20th Ann. ACM Symp. Theory of computing (1988)), 460-467
[12] Chistov, A. L.; Grigor’ev, D. Yu., Subexponential time solving systems of algebraic equations (1983), LOMI Preprints E-9-83, E-10-83, Leningrad
[13] Cucker, F.; Karpinski, M.; Koiran, P.; Lickteig, T.; Werther, K., On real Turing machines that toss coins (1995), University Bonn: University Bonn Berlin, manuscript · Zbl 0938.68648
[14] Débes, P., On the irreducibility of the polynomials \(P\)(\(t^m\), Y), J. Number Theory, 42, 2, 141-157 (1992) · Zbl 0770.12005
[15] De Millo, R. A.; Lipton, R. J., A probabilistic remark on algebraic program testing, Inform. Process. Lett., Vol. 7, 4, 193-195 (1978) · Zbl 0397.68011
[16] Dickenstein, A.; Fitchas, N.; Giusti, M.; Sessa, C., The membership problem of unmixed ideals is solvable in single exponential time, Discrete Appl. Math., 33, 73-94 (1991) · Zbl 0747.13018
[17] Dubé, T. W., A combinatorial proof of effective Nullstellensatz, J. Symbol. Comput., 15, 277-296 (1993) · Zbl 0783.13023
[18] Duval, D., Évaluation dynamique et clôture algébrique en axiom, J. Pure Appl. Algebra, 99, 267-295 (1995) · Zbl 0851.11075
[19] Fitchas, N.; Giusti, M.; Smietanski, F., Sur la complexité du théorème des zéros, (Florenzano, M.; etal., Approximation and Optimization in the Caribbean II, Proc. 2nd Internat. Conf. on Approximation and Optimization. Approximation and Optimization in the Caribbean II, Proc. 2nd Internat. Conf. on Approximation and Optimization, La Habana, 1993. Approximation and Optimization in the Caribbean II, Proc. 2nd Internat. Conf. on Approximation and Optimization. Approximation and Optimization in the Caribbean II, Proc. 2nd Internat. Conf. on Approximation and Optimization, La Habana, 1993, Approximation and Optimization (1995), Peter Lang Verlag), 274-329 · Zbl 0868.12008
[20] Fried, M., On the Sprinduk-Weissauer approach to universal Hilbert subsets, Israel J. Math., 51, 4, 347-363 (1985) · Zbl 0579.12002
[21] Fulton, W., Intersection Theory, (Ergebnisse der Mathematik, Band 2 (1984), Springer: Springer Frankfurt), 3 Folge · Zbl 0541.14005
[22] Garcia, C. B.; Zangwill, W. I., Pathways to Solutions, (Fixed Points and Equilibria (1981), Prentice-Hall: Prentice-Hall Berlin) · Zbl 0512.90070
[23] von zur Gathen, J., Parallel arithmetic computations: a survey, (Proc. 13th Conf. MFCS. Proc. 13th Conf. MFCS, Lecture Notes in Computer Science, Vol. 233 (1986), Springer: Springer Englewood Cliffs, NJ), 93-112 · Zbl 0616.68037
[24] 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, Proc. Cortona Conf. on Computational Algebraic Geometry and Commutative Algebra, Symposia Matematica, Vol. XXXIV (1993), Cambridge Univ. Press: Cambridge Univ. Press Berlin), Istituto Nazionale di Alta Matematica · Zbl 0829.14029
[25] Giusti, M.; Heintz, J.; Morais, J. E.; Pardo, L. M., When polynomial equation systems can be “solved” fast?, (Cohen, G.; Giusti, M.; Mora, T., Proc. 11th Internat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11. Proc. 11th Internat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11, Paris 1995. Proc. 11th Internat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11. Proc. 11th Internat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11, Paris 1995, Lecture Notes in Computer Science, Vol. 948 (1995), Springer: Springer Cambridge), 205-231 · Zbl 0902.12005
[26] Giusti, M.; Heintz, J.; Sabia, J., On the efficiency of effective Nullstellensätze, Comput. Complexity, 3, 56-95 (1993) · Zbl 0824.68051
[27] González Vega, L.; Trujilo, G., Using symmetric functions to describe the solution of a zero-dimensional ideal, (Cohen, G.; Giusti, M.; Mora, T., Proc. 11th Internat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-1 I. Proc. 11th Internat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-1 I, Paris 1995. Proc. 11th Internat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-1 I. Proc. 11th Internat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-1 I, Paris 1995, Lecture Notes in Computer Science, Vol. 948 (1995), Springer: Springer Berlin), 232-247 · Zbl 0894.12005
[28] Haegele, K.; Montaña, J. L., Polynomial random test for the equivalence problem of integers given by arithmetic circuits (1995), Universidad de Cantabria: Universidad de Cantabria Berlin, manuscript
[29] Heintz, J., Fast quantifier elimination over algebraically closed fields, Theoret. Comput. Sci., 24, 239-277 (1983) · Zbl 0546.03017
[30] Heintz, J., On the computational complexity of polynomials and bilinear mappings, (Huguet, L.; Poli, A., Proc., 5th Internat. Conf. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes AAECC-5. Proc., 5th Internat. Conf. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes AAECC-5, Menorca 1987. Proc., 5th Internat. Conf. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes AAECC-5. Proc., 5th Internat. Conf. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes AAECC-5, Menorca 1987, Lecture Notes in Computer Science, Vol. 356 (1989), Springer), 269-300
[31] Heintz, J.; Morgenstem, J., On the intrinsic complexity of elimination theory, J. Complexity, 9, 471-498 (1993) · Zbl 0835.68054
[32] Heintz, J.; Schnorr, C. P., Logic and Algorithmic, (An Internat. Symp. held in Honour of Ernst Specker. An Internat. Symp. held in Honour of Ernst Specker, Monographie No. 30 (1982), de l’Enseignement de Mathématiques: de l’Enseignement de Mathématiques Berlin), 237-254
[33] Heintz, J.; Sieveking, M., Absolute primality of polynomials is decidable in random polynomial time in the number of the variables, (Proc. 8th Internat. Colloq. on Automata, Languages and Programming ICALP 81. Proc. 8th Internat. Colloq. on Automata, Languages and Programming ICALP 81, Lecture Notes in Computer Science, Vol. 115 (1981), Springer: Springer Genève), 16-28 · Zbl 0462.68025
[34] Ibarra, O.; Moran, H., Probabilistic algorithms for deciding equivalence of straight-line programs, J. ACM, 30, 1, 217-228 (1983) · Zbl 0497.68013
[35] Iversen, B., Generic Local Structures of the Morphisms in Commutative Algebra, (Lecture Notes in Math., Vol. 310 (1973), Springer: Springer Berlin) · Zbl 0247.13001
[36] Ja’Ja’, J., An Introduction to Parallel Algorithms (1992), Addison-Wesley: Addison-Wesley Berlin
[37] Kaltofen, E., Greatest common divisors of polynomials given by straight line programs, J. ACM, 35, 1, 234-264 (1988) · Zbl 0642.68058
[38] Kaltofen, E., Factorization of polynomials given by striaght-line programs, (Micali, S., Randomness in Computation, Advances in Computing Research, 5 (1989), JAI Press Inc.: JAI Press Inc. Reading, MA), 375-412
[39] Kollár, J., Sharp effective Nullstellensatz, J. AMS, 1, 963-975 (1988) · Zbl 0682.14001
[40] Krick, T.; Pardo, L. M., Une approche informatique pour l’approximation diophantienne, C.R. Acad. Sci. Paris, Sér., 318, 407-412 (1994) · Zbl 0814.14050
[42] Kunz, E., Kähler Differentials, (Advanced Lectures in Mathematics (1986), Vieweg Verlag: Vieweg Verlag Greenwich, CT) · Zbl 0587.13014
[43] Lakshman, Y. N.; Lazard, D., On the complexity of zero-dimensional algebraic systems, (Traverso, C., Proc. MEGA’90, Progress in Mathematics, Vol. 94 (1991), Birkhäuser: Birkhäuser Braunschweig), 217-225 · Zbl 0733.13015
[44] Lazard, D., Résolution des systèmes d’équations algébriques, Theoret. Comput. Sci., 15, 77-110 (1981) · Zbl 0459.68013
[45] Lenstra, A. K.; Lenstra, H. W.; Lovász, L., Factoring polynomials with rational coefficients, Math. Ann., 261, 515-534 (1982) · Zbl 0488.12001
[46] Macaulay, F. S., The Algebraic Theory of Modular Systems (1916), Cambridge Univ. Press: Cambridge Univ. Press Boston · Zbl 0802.13001
[47] Moeller, M., Systems of algebraic equations solved by means of endomorphisms, (Cohen, G.; Mora, T.; Moreno, O., Proc. 10th Internat. Conf. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes AAECC-10. Proc. 10th Internat. Conf. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes AAECC-10, Puerto Rico 1993. Proc. 10th Internat. Conf. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes AAECC-10. Proc. 10th Internat. Conf. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes AAECC-10, Puerto Rico 1993, Lecture Notes in Computer Science (1993), Springer: Springer Cambridge)
[48] Montaña, J. L.; Pardo, L. M., Lower bounds for arithmetic networks, AAECC, 4, 1-24 (1993) · Zbl 0769.68055
[49] Morgenstern, J., How to compute fast a function and all its derivatives, (Prepublication No. 49 (1984), Université de Nice: Université de Nice Berlin) · Zbl 0558.68033
[50] Pardo, L. M., How lower and upper complexity bounds meet in elimination theory, (Proc. 11th Intemat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11. Proc. 11th Intemat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11, Paris 1995. Proc. 11th Intemat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11. Proc. 11th Intemat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11, Paris 1995, Lecture Notes in Computer Science, Vol. 948 (1995), Springer), 33-69 · Zbl 0899.68054
[51] Philippon, P., Dénominateurs dans le théorème des zéros de Hilbert, Acta Arith., 58, 1-25 (1991) · Zbl 0679.13010
[52] Sabia, J.; Solemó, P., Bounds for traces in complete intersections and degrees in the Nullstellensatz, AAECC, 6, 353-376 (1995) · Zbl 0844.14018
[53] Sabia, J.; Solermó, P., On intrinsic bounds in the Nullstellensatz (1995), Univ. de Buenos Aires: Univ. de Buenos Aires Berlin, manuscript
[54] Schönhage, A., On the power of random acces machines, (Proc. 6th Internat. Conf. on Automata, Languages and Programming (1979), ICALP), 520-529
[55] Schwartz, J. T., Fast probabilistic algorithms for verification of polynomial identities, J. ACM, 27, 701-717 (1980) · Zbl 0452.68050
[56] Shub, M.; Smale, S., Complexity of Bezout’s theorem V: polynomial time, Theoret. Comput. Sci., 133, 141-164 (1994) · Zbl 0846.65022
[57] Shub, M.; Smale, S., On the intractability of Hilbert’s Nullstellensatz and an algebraic version of NP ≠ P?, IBM Research Report (1994), Yorktown Heights
[58] Sprinduk, V. G., Diophantine equations involving unknown primes, Tmdy MIANSSR, 158, 180-196 (1981)
[59] Strassen, V., Vermeidung von Divisionen, Crelle J. Reine Angew. Math., 264, 184-202 (1973) · Zbl 0294.65021
[60] Strassen, V., Die Berechungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoffizienten, Numer. Math., 20, 238-251 (1973) · Zbl 0251.65036
[61] Strassen, V., Algebraic complexity theory, (Handbook of Theoretical Computer Science, Vol. 11 (1990), Elsevier: Elsevier Graz), 634-671
[63] Zariski, P.; Samuel, O., Commutative Algebra II, (Graduate Texts in Mathematics, Vol. 29 (1960), Springer: Springer Amsterdam) · Zbl 0121.27901
[64] Zippel, R. E., Probabilistic algorithms for sparse polynomials, (Lecture Notes in Computer Science, Vol. 72 (1979), Springer: Springer Berlin), 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. 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.