×

zbMATH — the first resource for mathematics

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
PDF BibTeX Cite
Full Text: DOI arXiv
References:
[1] M.E. Alonso, E. Becker, M.-F. Roy and T. Wörmann, Zeroes, multiplicites and idempotents for zerodimensional systems, Proc. MEGA’94, Birkhäuser Progress in Mathematics, to appear.
[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},…,xn], 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, (), 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, (), 131-152
[10] Canny, J., Some algebraic and geometric problems in PSPACE, (), 460-467
[11] A.L. Chistov, Polynomial-time computation of the dimension of components of algebraic varieties in zero-characteristic, preprint, Université Paris Val de Marne. · Zbl 0893.14020
[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 Berlin, manuscript · Zbl 0938.68648
[14] Débes, P., On the irreducibility of the polynomials P(tm, 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, (), 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, (), 3 Folge · Zbl 0541.14005
[22] Garcia, C.B.; Zangwill, W.I., Pathways to solutions, () · Zbl 0512.90070
[23] von zur Gathen, J., Parallel arithmetic computations: a survey, (), 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, (), 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?, (), 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, (), 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 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, (), 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.; Heintz, J.; Schnorr, C.P., Logic and algorithmic, (), 237-254, also in
[33] Heintz, J.; Sieveking, M., Absolute primality of polynomials is decidable in random polynomial time in the number of the variables, (), 16-28
[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, () · Zbl 0247.13001
[36] Ja’Ja’, J., An introduction to parallel algorithms, (1992), 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, (), 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
[41] T. Krick and L.M. Pardo, A computational method of diophantine approximation, Proc. MEGA’94 Birkhäuser Progress in Mathematics, to appear. · Zbl 0878.11043
[42] Kunz, E., Kähler differentials, () · Zbl 0587.13014
[43] Lakshman, Y.N.; Lazard, D., On the complexity of zero-dimensional algebraic systems, (), 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 Boston · Zbl 0802.13001
[47] Moeller, M., Systems of algebraic equations solved by means of endomorphisms, ()
[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, () · Zbl 0558.68033
[50] Pardo, L.M., How lower and upper complexity bounds meet in elimination theory, (), 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 Berlin, manuscript
[54] Schönhage, A., On the power of random acces machines, (), 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, (), 634-671
[62] M. Yasumoto, Nonstandard arithmetic and Hilbert’s irreducible sequences, manuscript. · Zbl 0642.12007
[63] Zariski, P.; Samuel, O., Commutative algebra II, () · Zbl 0121.27901
[64] Zippel, R.E., Probabilistic algorithms for sparse polynomials, (), 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.