Bases standard, élimination et complexité

Giusti, Marc

Journées mathématiques X-UPS, Calcul formel (1997), pp. 1-30.

Étant donné un système d’équations linéaires homogènes à $n+1$ variables, les formules de Cramer permettent de paramétrer les solutions en fonction d’un certain nombre de variables que l’on peut choisir arbitrairement.

Nous nous proposons d’établir un résultat analogue pour des systèmes d’équations non linéaires : il s’agit du lemme de normalisation de Noether. Nous allons nous poser à son sujet des questions d’algorithmique et de complexité. Tout ce qui suit provient essentiellement des deux articles [Giu88], [GH93].

[Ber84] Berkowitz, Stuart J. On computing the determinant in small parallel time using a small number of processors, Inform. Process. Lett., Volume 18 (1984) no. 3, pp. 147-150 | DOI | MR | Zbl

[Bri83] Briançon, Joël Sur le degré des relations entre polynômes, C. R. Acad. Sci. Paris Sér. I Math., Volume 297 (1983) no. 10, pp. 553-556 | MR | Zbl

[Buc65] Buchberger, B. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, Ph.D. Dissertation, U. Innsbruck, Austria (1965)

[CLO15] Cox, David A.; Little, John; O’Shea, Donal Ideals, varieties, and algorithms, Undergraduate Texts in Math., Springer, Cham, 2015 (An introduction to computational algebraic geometry and commutative algebra) | DOI

[Dem87] Demazure, M. Le théorème de complexité de Mayr et Meyer, Géométrie algébrique et applications, I (La Rábida, 1984) (Travaux en Cours), Volume 22, Hermann, Paris, 1987, pp. 35-58 | MR | Zbl

[DFGS91] Dickenstein, Alicia; Fitchas, Noaï; Giusti, Marc; Sessa, Carmen The membership problem for unmixed polynomial ideals is solvable in single exponential time, Discrete Appl. Math., Volume 33 (1991) no. 1-3, pp. 73-94 | DOI | MR | Zbl

[FGM90] Fitchas, Noaï; Galligo, André; Morgenstern, Jacques Algorithmes rapides en sequentiel et en parallèle pour l’élimination des quantificateurs en géométrie élémentaire, Séminaire sur les structures algébriques ordonnées, Vol. I (Publ. Math. Univ. Paris VII), Volume 32, Univ. Paris VII, Paris, 1990, pp. 103-145

[GH91] Giusti, Marc; Heintz, Joos Algorithmes — disons rapides — pour la décomposition d’une variété algébrique en composantes irréductibles et équidimensionnelles, Effective methods in algebraic geometry (Castiglioncello, 1990) (Progr. Math.), Volume 94, Birkhäuser Boston, Boston, MA, 1991, pp. 169-194 | DOI | Zbl

[GH93] Giusti, Marc; Heintz, Joos La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial, Computational algebraic geometry and commutative algebra (Cortona, 1991) (Sympos. Math.), Volume XXXIV, Cambridge Univ. Press, Cambridge, 1993, pp. 216-256 | Zbl

[Giu88] Giusti, Marc Combinatorial dimension theory of algebraic varieties, J. Symbolic Comput., Volume 6 (1988) no. 2-3, pp. 249-265 | DOI | MR | Zbl

[Har77] Hartshorne, R. Algebraic geometry, Graduate Texts in Math., 52, Springer-Verlag, 1977 | DOI

[Hei89] Heintz, Joos On the computational complexity of polynomials and bilinear mappings. A survey, Applied algebra, algebraic algorithms and error-correcting codes (Menorca, 1987) (Lecture Notes in Comput. Sci.), Volume 356, Springer, Berlin, 1989, pp. 269-300 | DOI | MR | Zbl

[Hir64] Hironaka, Heisuke Resolution of singularities of an algebraic variety over a field of characteristic zero. I, Ann. of Math. (2), Volume 79 (1964), pp. 109-203 | DOI | MR

[HM87] Henry, J.-P.; Merle, M. Conditions de régularité et éclatements, Ann. Inst. Fourier (Grenoble), Volume 37 (1987) no. 3, pp. 159-190 | DOI | Numdam | Zbl

[HS81] Heintz, Joos; Sieveking, Malte Absolute primality of polynomials is decidable in random polynomial time in the number of variables, Automata, languages and programming (Akko, 1981) (Lecture Notes in Comput. Sci.), Volume 115, Springer, Berlin, 1981, pp. 16-28 | MR | Zbl

[HS82] Heintz, Joos; Schnorr, C.-P. Testing polynomials which are easy to compute, Logic and algorithmic (Zurich, 1980) (Monograph. Enseign. Math.), Volume 30, 1982, pp. 237-254 | MR | Zbl

[Kal88] Kaltofen, Erich Greatest common divisors of polynomials given by straight-line programs, J. Assoc. Comput. Mach., Volume 35 (1988) no. 1, pp. 231-264 | DOI | MR | Zbl

[Laz77] Lazard, Daniel Algèbre linéaire sur $K[X_1,\cdots ,X_n]$, et élimination, Bull. Soc. Math. France, Volume 105 (1977) no. 2, pp. 165-190 | DOI | Numdam | Zbl

[LL91] Lakshman, Y. N.; Lazard, Daniel On the complexity of zero-dimensional algebraic systems, Effective methods in algebraic geometry (Castiglioncello, 1990) (Progr. Math.), Volume 94, Birkhäuser Boston, Boston, MA, 1991, pp. 217-225 | DOI | MR | Zbl

[Mac27] Macaulay, F. S. Some properties of enumeration in the theory of modular systems., Proc. Lond. Math. Soc. (2), Volume 26 (1927), pp. 531-555 | DOI | MR | Zbl

[MM82] Mayr, Ernst W.; Meyer, Albert R. The complexity of the word problems for commutative semigroups and polynomial ideals, Adv. in Math., Volume 46 (1982) no. 3, pp. 305-329 | DOI | MR | Zbl

[Mul87] Mulmuley, K. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field, Combinatorica, Volume 7 (1987) no. 1, pp. 101-104 | DOI | MR | Zbl

[Ric68] Richardson, Daniel Some undecidable problems involving elementary functions of a real variable, J. Symbolic Logic, Volume 33 (1968), pp. 514-520 | DOI | MR | Zbl

[Sto89] Stoss, Hans-Jörg On the representation of rational functions of bounded complexity, Theoret. Comput. Sci., Volume 64 (1989) no. 1, pp. 1-13 | DOI | MR | Zbl

[Str72] Strassen, V. Berechnung und Programm. I, Acta Informat. (1972) no. 1, pp. 320-355 | DOI | MR | Zbl

[Str73] Strassen, Volker Vermeidung von Divisionen, J. Reine Angew. Math., Volume 264 (1973), pp. 184-202 | MR | Zbl

[vzG86] von zur Gathen, Joachim Parallel arithmetic computations : a survey, Mathematical foundations of computer science, 1986 (Bratislava, 1986) (Lecture Notes in Comput. Sci.), Volume 233, Springer, Berlin, 1986, pp. 93-112 | DOI | MR | Zbl