Bases standard, élimination et complexité
Giusti, Marc1
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
Giusti, Marc 1

1 Laboratoire GAGE, GDR de Calcul Formel MEDICIS, Centre de Mathématiques, École Polytechnique, 91128 Palaiseau cedex 
@incollection{XUPS_1997____1_0,
     author = {Giusti, Marc},
     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 = {http://www.numdam.org/articles/10.5802/xups.1997-01/}
}
TY  - JOUR
AU  - Giusti, Marc
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  - http://www.numdam.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 Giusti, Marc
%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 http://www.numdam.org/articles/10.5802/xups.1997-01/
%R 10.5802/xups.1997-01
%G fr
%F XUPS_1997____1_0
Giusti, Marc. Bases standard, élimination et complexité. Journées mathématiques X-UPS, Calcul formel (1997), pp. 1-30. doi : 10.5802/xups.1997-01. http://www.numdam.org/articles/10.5802/xups.1997-01/

[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 ,⋯,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

Cité par Sources :