Bases standard, élimination et complexité
Marc Giusti1
1 Laboratoire GAGE, GDR de Calcul Formel MEDICIS, Centre de Mathématiques, École Polytechnique, 91128 Palaiseau cedex
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].

Publié le :
DOI : 10.5802/xups.1997-01
Marc Giusti 1

1 Laboratoire GAGE, GDR de Calcul Formel MEDICIS, Centre de Mathématiques, École Polytechnique, 91128 Palaiseau cedex 
@incollection{XUPS_1997____1_0,
     author = {Marc Giusti},
     title = {Bases standard, \'elimination~et~complexit\'e},
     booktitle = {Calcul formel},
     series = {Journ\'ees math\'ematiques X-UPS},
     pages = {1--30},
     publisher = {Les \'Editions de l{\textquoteright}\'Ecole polytechnique},
     year = {1997},
     doi = {10.5802/xups.1997-01},
     language = {fr},
     url = {https://proceedings.centre-mersenne.org/articles/10.5802/xups.1997-01/}
}
TY  - JOUR
AU  - Marc Giusti
TI  - Bases standard, élimination et complexité
JO  - Journées mathématiques X-UPS
PY  - 1997
SP  - 1
EP  - 30
PB  - Les Éditions de l’École polytechnique
UR  - https://proceedings.centre-mersenne.org/articles/10.5802/xups.1997-01/
DO  - 10.5802/xups.1997-01
LA  - fr
ID  - XUPS_1997____1_0
ER  - 
%0 Journal Article
%A Marc Giusti
%T Bases standard, élimination et complexité
%J Journées mathématiques X-UPS
%D 1997
%P 1-30
%I Les Éditions de l’École polytechnique
%U https://proceedings.centre-mersenne.org/articles/10.5802/xups.1997-01/
%R 10.5802/xups.1997-01
%G fr
%F XUPS_1997____1_0
Marc Giusti. Bases standard, élimination et complexité. Journées mathématiques X-UPS, Calcul formel (1997), pp. 1-30. doi : 10.5802/xups.1997-01. https://proceedings.centre-mersenne.org/articles/10.5802/xups.1997-01/

[Ber84] Stuart J. Berkowitz 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] Joël Briançon 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] B. Buchberger Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, Ph.D. Dissertation, U. Innsbruck, Austria (1965)

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

[Dem87] M. Demazure 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] Alicia Dickenstein; Noaï Fitchas; Marc Giusti; Carmen Sessa 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] Noaï Fitchas; André Galligo; Jacques Morgenstern 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] Marc Giusti; Joos Heintz 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] Marc Giusti; Joos Heintz 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] Marc Giusti Combinatorial dimension theory of algebraic varieties, J. Symbolic Comput., Volume 6 (1988) no. 2-3, pp. 249-265 | DOI | MR | Zbl

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

[Hei89] Joos Heintz 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] Heisuke Hironaka 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] J.-P. Henry; M. Merle Conditions de régularité et éclatements, Ann. Inst. Fourier (Grenoble), Volume 37 (1987) no. 3, pp. 159-190 | DOI | Numdam | Zbl

[HS81] Joos Heintz; Malte Sieveking 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] Joos Heintz; C.-P. Schnorr Testing polynomials which are easy to compute, Logic and algorithmic (Zurich, 1980) (Monograph. Enseign. Math.), Volume 30, 1982, pp. 237-254 | MR | Zbl

[Kal88] Erich Kaltofen 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] Daniel Lazard Algèbre linéaire sur K[X 1 ,⋯,X n ], et élimination, Bull. Soc. Math. France, Volume 105 (1977) no. 2, pp. 165-190 | DOI | Numdam | Zbl

[LL91] Y. N. Lakshman; Daniel Lazard 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] F. S. Macaulay 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] Ernst W. Mayr; Albert R. Meyer 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] K. Mulmuley 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] Daniel Richardson Some undecidable problems involving elementary functions of a real variable, J. Symbolic Logic, Volume 33 (1968), pp. 514-520 | DOI | MR | Zbl

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

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

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

[vzG86] Joachim von zur Gathen 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

Cité par Sources :