INSTITUT DE LA FRANCOPHONIE POUR L’INFORMATIQUE

RAPPORT DE STAGE

IMPLICITATION DE SURFACES RATIONNELLES
Présenté pour l’obtention
Du
« Diplôme d’Etudes Professionnelles Approfondies »

Préparé sous la direction de
Bernard MOURRAIN, Chef du projet GALAAD - INRIA

Présenté et soutenu publiquement
Par
Van Thoi TRAN

Novembre 2004


Remerciements

J’adresse toute ma gratitude à mon responsable de stage, Monsieur
Bernard Mourrain, pour sa disponibilité, son soutien constant et son aide
précieuse durant ce stage.
Je voudrais également remercier chaleureusement Laurent Busé
pour l’aide permanente qu’il m’a prodigué. Je dois encore remercier
Grégory Gatellier pour sa collaboration serrée tout au long de mon stage.
Merci également à Olivier Ruatta pour ses conseils utiles qu’il m’a donnés.
J’ai le plaisir de remercier Aurélie Richard, Monique Teillaud et Vu
Van Thinh pour leur accueil, leur disponibilité et leur gentillesse pendant
mon séjour en France.

J’exprime mon entière reconnaissance envers ma famille et mes amis
pour leurs soutiens, leurs aides et leurs encouragements.


Implicitation de surfaces rationnelles

Table des matières

Table des matières

Table des matières ............................................................................................................................................3
Résumé ..............................................................................................................................................................5
Abstract .............................................................................................................................................................6
Liste des figures ................................................................................................................................................7
Chapitre 1 :

INTRODUCTION ...............................................................................................................8

1.1

Problématique .................................................................................................................................8

1.2

Motivation .......................................................................................................................................9

1.3

Environnement de stage ................................................................................................................10


Chapitre 2 :
2.1

RESULTATS PRELIMINAIRES ....................................................................................11

Surface rationnelle et équation implicite.......................................................................................11

2.2
Méthodes d’implicitation...............................................................................................................12
2.2.1
Implicitation exacte ..................................................................................................................12
2.2.2
Implicitation approchée ............................................................................................................13
Chapitre 3 :

METHODES D’IMPLICITATION .................................................................................14

3.1
Elimination de variables avec le résultant ....................................................................................14
3.1.1
Construction de Macaulay ........................................................................................................14
3.1.2
Lien avec le problème d’implicitation ......................................................................................18
3.1.3
Remarques ................................................................................................................................20
3.2
Implicitation et Bézoutiens ............................................................................................................20
3.2.1
Bézoutiens ................................................................................................................................21
3.2.2

Application à l’implicitation.....................................................................................................23
3.3
Problème d’approximation............................................................................................................26
3.3.1
Principe de la méthode..............................................................................................................26
3.3.2
Mesure de l’erreur ....................................................................................................................30
Chapitre 4 :

IMPLEMENTATION .......................................................................................................33

4.1
Mise en œuvre................................................................................................................................33
4.1.1
Partie d’implicitation ................................................................................................................33
4.1.2
Partie de test .............................................................................................................................34
4.1.3
Partie de connexion ..................................................................................................................34
4.1.4
Partie de visualisation ...............................................................................................................34

Van Thoi TRAN

-3-


Implicitation de surfaces rationnelles

Table des matières


4.2
Expériences numériques................................................................................................................35
4.2.1
Méthodes exactes......................................................................................................................35
4.2.2
Méthode approchée...................................................................................................................38
Chapitre 5 :

CONCLUSION ..................................................................................................................42

Annexe .............................................................................................................................................................43
Références .......................................................................................................................................................49

Van Thoi TRAN

-4-


Implicitation de surfaces rationnelles

Résumé

Résumé

Le problème d'implicitation de courbes ou de surfaces rationnelles consiste
en la détermination de l'équation implicite de telles courbes ou surfaces. Calculer
une équation implicite est un problème important en CAO (Conception Assistée par
Ordinateur) et dans beaucoup de problèmes de géométrie combinatoire. Alors
plusieurs méthodes sont connues pour résoudre ce problème.

Dans ce rapport, on va faire un tour d'horizon de différentes méthodes
d’implicitation de surfaces rationnelles : résultant, Bézoutiens et complexes
d'approximation. L’implémentation de ces méthodes est contribuée à la bibliothèque
C++ SYNAPS orientée vers le calcul symbolique/numérique.

Mots clés : implicitation, théorie de résultants, construction de Macaulay,
bézoutiens, implicitation approchée.

Van Thoi TRAN

-5-


Implicitation de surfaces rationnelles

Abstract

Abstract

The implicitization problem for rational curves or surfaces consists of the
determination of implicit equation of any curves or surfaces. Calculating an implicit
equation is a significant problem in CAD (Computer-Aided Design) and in many
problems of combinative geometric. Then several methods are known to solve this
problem.
In this report, we will make a review of various implicitization methods for
rational surfaces : resultant, Bezoutiens and approximation complexes. The
implementation of these methods is contributed to the library C++ SYNAPS
directed towards symbolic/numeric calculation.

Keywords : implicitization, resultant theory, Macaulay construction, bezoutiens,

approximative implicitization.

Van Thoi TRAN

-6-


Implicitation de surfaces rationnelles

Liste des figures

Liste des figures
Figure 1 : Graphe de S _________________________________________________________________24
Figure 2 : Affichage de S1 ______________________________________________________________28
Figure 3 : Forme approchée de S1 _______________________________________________________29
Figure 4 : Superposition de S1 et son approximation _______________________________________30
Figure 5 : Une mauvaise approximation de S1 _____________________________________________31
Figure 6 : Approchée à degré 6 _________________________________________________________39
Figure 7 : Approchée à degré 3 _________________________________________________________40
Figure 8 : Mauvaise approximation à degré 6 _____________________________________________41

Van Thoi TRAN

-7-


Implicitation de surfaces rationnelles

INTRODUCTION


Chapitre 1 : INTRODUCTION

1.1

Problématique
Un objet algébrique peut être représenté classiquement par deux manières : la

première est de donner son équation implicite, et la deuxième est d’en donner une
paramétrisation. Ces deux méthodes ont des avantages aussi que des inconvénients.
Par exemple, on a la facilité de représenter une surface sous forme paramétrée, mais
plus difficile de déterminer si un point de l’espace appartient ou non à cette surface.
Par contre, ce problème est très facile de résoudre par une simple substitution si l’on
a l’équation implicite de cette surface. De plus, l’équation implicite peut aider à
tracer une courbe ou une surface au voisinage d'une singularité, à calculer une autointersection d'offsets ou bien encore calculer l'intersection de courbes ou de
surfaces. Cependant, trouver l’équation implicite n’est pas facile !
L’existante de deux mécanismes de représentation ci-dessus se pose le
problème de convertir de l’une vers l’autre. Tout objet algébrique donné par une
paramétrisation rationnelle admet une équation implicite, et le problème qui
consiste à déterminer celle-ci est appelé problème d’implicitation. Le problème
inverse qui consiste à trouver une représentation paramétrique d’un objet algébrique
donné sous forme implicite est donc appelé problème de paramétrisation. Alors
nous ne nous intéressons qu’ici au problème d’implicitation qui est très important
dans CAO (Conception Assistée par Ordinateur) et beaucoup d’autres problèmes de
géométrie combinatoire.

Van Thoi TRAN

-8-



Implicitation de surfaces rationnelles

INTRODUCTION

Le problème d'implicitation dans le cas des courbes est simple et bien connu :
un calcul de résultant multivarié de deux polynômes en une seule variable fournit
toujours la réponse. Par contre, le cas des surfaces est bien plus compliqué.
Plusieurs méthodes sont connues pour résoudre ce problème d'implicitation pour les
surfaces rationnelles. Alors elles le réduisent toutes en un problème d'élimination de
variables.
Ce stage a donc pour but de faire une étude sur quelques méthodes
d’implicitation, de les implémenter et de tester les codes obtenus sur des exemples
concrets venant de CAO.

1.2 Motivation
Ce travail est réalisé dans le cadre du contrat européen GAIA (Application of
approximate algebraic geometry in industrial computed aided design, IST 199929010 ; entre l’INRIA et ses partenaires : Université d’Olso, Université de Nice –
Sophia Antipolis, SINTEF, société Think3), dont l’objectif est de construire une
bibliothèque C++ nommée SYNAPS (SYmbolic and Numeric APplicationS)1. Cette
bibliothèque, développée pour les systèmes d’UNIX, fournira une plateforme
logique intégrée les fonctionnalités de plusieurs logiciels de calcul scientifique
existants [12] dans cet environnement.
Jusqu’à présent, on a implémenté dans SYNAPS les modules suivants :
• Input/Output : les entrées/sorties standardisées en format de Maple,
LaTeX et VRML (connexion avec POV-Ray).
• Arithmetic : une extension des classes arithmétiques basée sur les
librairies GMP et MPFR.
• Linear algebra : les bases de l’algèbre linéaire : vecteur, matrice,…
• Resultant : les bases de résultants univariés et multivariés.
1


Environnement de calcul symbolique / numérique. Site Web />
Van Thoi TRAN

-9-


Implicitation de surfaces rationnelles

INTRODUCTION

• Solvers : les méthodes de résolution pour les systèmes d’équations
polynômiales.
• Geometry : les classes géométriques de bases : représentation de courbes
et surfaces algébriques, les calculs de l’intersection et de la topologie, …
La contribution de ce stage au SYNAPS est visée à la partie d’implicitation
de courbes et de surfaces paramétriques. Il s’agit d’un module nommé Implicit pour
les calculs de l’équation implicite d’une représentation paramétrique.

1.3 Environnement de stage
Le projet GALAAD (Géométrie, Algèbre et Algorithmes), créé le 15 2001
février, est un projet commun entre l’INRIA Sophia Antipolis et le laboratoire J.A.
Dieudonné – UMR du CNRS Nº 6621, l’Université de Nice, Sophia Antipolis. Le
programme de recherche de cette équipe s’articule autour de la géométrie
algébrique effective et de ses applications. Son objectif est de développer des
méthodes algorithmiques permettant de résoudre efficacement et de manière fiable
les problèmes géométriques et algébriques rencontrés dans les domaines tels que la
CAO, la robotique, la vision par ordinateur, la biologie moléculaire, … Sa démarche
s’appuie sur les axes de recherche suivants :
• La géométrie pour modéliser, comprendre, classifier

• L’algèbre pour calculer, simplifier, résoudre, exploiter les structures
• Le lien symbolique-numérique pour expérimenter, certifier, valider.
Le site Web du groupe : />
Van Thoi TRAN

-10-


Implicitation de surfaces rationnelles

RESULTATS PRELIMINAIRES

Chapitre 2 : RESULTATS PRELIMINAIRES

2.1 Surface rationnelle et équation implicite
Généralement, une surface rationnelle est donnée par une paramétrisation,
c’est-à-dire par des équations :
q1 ( x1 , x 2 ) q 2 ( x1 , x 2 ) q3 ( x1 , x 2 )
,
,
q0 ( x1 , x 2 ) q0 ( x1 , x 2 ) q0 ( x1 , x 2 )

où q 0 ( x1 , x 2 ) , q1 ( x1 , x2 ) , q 2 ( x1 , x 2 ) , q3 ( x1 , x 2 ) sont quatre polynômes en deux
variables. En homogénéisant ces quatre polynômes, on obtient une application
rationnelle :
θ:

Ρ2
→
Ρ3

( x 0 : x1 : x 2 ) a ( p 0 : p1 : p 2 : p 3 )

donnée par quatre polynômes homogènes p 0 , p1 , p 2 , p3 de même degré d (le plus
grand des degrés des polynômes q 0 , q1 , q 2 , q3 ). Le problème d’implicitation est alors
de calculer explicitement l’équation de la plus petite surface algébrique de P3 qui
contient l’image de θ.
On sait résoudre ce problème lorsque θ est une application régulière, dans ce
cas le degré de l’équation implicite est d2. Lorsque θ n’est pas régulière, c’est-à-dire
qu’il existe des points x de P2 tels que pi(x) = 0 pour tout i = 0, 1, 2, 3 (de tels points
sont appelés points bases), le problème d’implicitation est difficile à résoudre, mais

Van Thoi TRAN

-11-


Implicitation de surfaces rationnelles

RESULTATS PRELIMINAIRES

l’on sait que la présence de points bases implique que le degré de l’équation
implicite est inférieur à d2.

2.2 Méthodes d’implicitation
Plusieurs méthodes existantes permettent de trouver l’équation implicite
d’une surface rationnelle. Elles sont classifiées en deux types suivants :

2.2.1 Implicitation exacte
Trois méthodes exactes sont connues pour résoudre le problème
d’implicitation. Ces trois méthodes réduisent ce problème en un problème

d’élimination de variables [3].
La première méthode est basée sur des calculs de bases de Gröbner. En
l’absence de points bases, un calcul de base de Gröbner de l’idéal I engendré par les
polynômes p 0 , p1 , p 2 , p3 nous donne l’équation implicite. En la présence de points
bases, l’équation implicite n’appartient pas à l’idéal I, mais au saturé de l’idéal I par
l’idéal définissant les points bases. Ainsi, dans ce cas, on a besoin de calculer un
idéal saturé et une base de Gröbner. Cette méthode peut être très lente en pratique
mais elle a l’avantage de toujours fournir l’équation implicite.
La deuxième méthode pour calculer équation implicite consiste en le calcul
d’un résultant multivarié classique des polynômes p1 − Xp 0 , p 2 − Yp0 , p3 − Zp 0 .
Cette méthode échoue en la présence de points bases. Par conséquent, des
techniques de perturbations sont utilisées pour calculer l’équation implicite en la
présence de points bases. Alors, l’équation implicite est contenue dans le terme de
plus bas degré du résultant du système perturbé (développé en la variable de
perturbation), et il faut faire un calcul de plus grand commun diviseur (PGCD) de
d+1 polynômes pour l’extraire. Malgré cela, cette solution a une très grande
complexité en pratique.

Van Thoi TRAN

-12-


Implicitation de surfaces rationnelles

RESULTATS PRELIMINAIRES

La troisième méthode d’implicitation exacte, appelée surfaces mobiles, est
introduite par Tom Sederberg. Cette méthode est basée sur l’étude des syzygies de
l’idéal I défini par les polynômes p 0 , p1 , p 2 , p3 et exprime l’équation comme le

déterminant d’une certaine matrice. La formulation de l’équation implicite sous une
forme déterminantale peut s’avérer très utile en pratique. Cependant, la validité
d’une telle méthode est prouvée uniquement en l’absence de points bases et dans le
cas de surface bi-homogènes.

2.2.2 Implicitation approchée
On s’intéresse non seulement de chercher l’équation implicite exacte d’une
surface rationnelle mais aussi celle approchée en minimisant quelques critères. Une
représentation implicite approchée de la surface rationnelle pourra être trouvée en
effectuant les algorithmes d’approximation en des points à virgules flottantes [7].
Malheureusement, on n’a pas encore trouvé de bonne approche.

Van Thoi TRAN

-13-


Implicitation de surfaces rationnelles

METHODES D’IMPLICITATION

Chapitre 3 : METHODES D’IMPLICITATION

Dans ce chapitre, on va faire un tour d’horizon quelques méthodes
d’implicitation de surfaces rationnelles. Alors je me concentre ici sur les méthodes
basées sur le résultant, sur le bézoutien et sur une approximation complexe pour une
région finie de la surface. La première est une méthode classique qui nous donnera
une idée générale des méthodes d’implicitation tandis que la deuxième est
considérée comme une solution la plus efficace des approches exactes. La dernière
est ainsi représentant de la famille des méthodes approchées qui possèdent très peu

de recherche jusqu’à présent.

3.1 Elimination de variables avec le résultant
Le résultant est considéré comme l’outil standard pour résoudre le problème
d’implicitation de la surface rationnelle. L’équation implicite est ainsi exprimée par
le résultant multivarié calculé à partir du déterminant d’une matrice spécifique qui
est généralement grosse. Cette matrice se nomme matrice de Macaulay.

3.1.1 Construction de Macaulay
On commence par la construction de la matrice de Macaulay qui sert à
calculer le résultant sur Pn de n+1 polynômes f0 ,… , fn non-homogènes en n
variables (x1,…,xn). Les degrés de ces polynômes sont respectivement d0,…,dn.

Van Thoi TRAN

-14-


Implicitation de surfaces rationnelles

METHODES D’IMPLICITATION

Soit v = ∑i =0 d i − n , on appelle XF l’ensemble des monômes en x de degrés
n

⎛ v + n⎞

⎟⎟ .
≤ v. Le nombre de monômes dans XF est N F = ⎜⎜
⎝ n ⎠


Parmi ces monômes, considérons ceux qui sont divisibles par x nd , on les
n

note X E . Parmi les monômes de XF qui ne sont pas divisibles par x nd , considérons
n

n

ensuite ceux qui sont divisibles par x nd−1 , on les note alors X E . Construisons
n −1

n −1

maintenant X E

n−2

en considérant parmi ceux qui restent, ceux divisibles par x nd− 2 et
n−2

ainsi de suite jusqu’à x1d .
1

L’ensemble des monômes de XF qui ne sont divisibles ni par x1d ,…, ni par
1

x nd n est noté X E0 . Cet ensemble est donc :

{


}

X E0 = x1α1 K x nα n ;0 ≤ α i ≤ d i − 1

Par construction, les ensembles X E sont disjoints et leur union est XF.
i

En posant E 0 = X E et Ei = X E / xi d (i = 1,…, n), la matrice de Macaulay
0

i

i

définie subséquemment l’application :
S:

E0 × K E n →
(q 0 , K, q n ) a

XF
n
∑i =0 qi f i

(1)

On obtient la matrice M en considérant l’image par S d’un monôme
F


x β i ∈ E i et en la décomposant en fonction des monômes de X . Le coefficient dans la

ligne correspondant au monôme x α de XF et dans la colonne correspondant au
monôme x β ∈ E i est le coefficient de x α dans x β f i . Cette matrice est ainsi indexée
i

i

par les monômes de XF pour les lignes et par les monômes de

U

n

i =0

Ei pour les

⎛v + n⎞

⎟⎟ qui est le
colonnes. De plus, M est une matrice carrée de la taille N F = ⎜⎜
⎝ n ⎠

nombre de monômes dans XF.

Van Thoi TRAN

-15-



Implicitation de surfaces rationnelles

METHODES D’IMPLICITATION

Pour le détail, on va voir l’exemple suivant [2] :

Exemple 1.

‰

Soit un système de 3 polynômes en les variables
(x1,x2) :
fo
f1

= c0,0
= c1,0

+ c0,1x1
+ c1,1x1

+ c0,2x 2
+ c1,2x 2

+ c0,3x12
+ c1,3x12

+ c0,4x1x 2
+ c1,4x1x 2


+ c0,5x 22
+ c0,5x 22

f2

= c2,0

+ c2,1x1

+ c2,2x 2

+ c2,3x12

+ c2,4x1x 2

+ c2,5x 22

Les degrés de ces monômes sont successivement d0 =
d1

=

d2

=

2.

Alors


v =

∑

2

i =0

di − 2 = 2 + 2 + 2 − 2 = 4 .

Le

⎛4 + 2⎞

⎟⎟ = 15 . Les
nombre de monômes dans XF est donc N F = ⎜⎜
⎝ 2 ⎠

monômes de XF classés par degré total sont :
{1, x1, x 2, x12, x1x 2, x 22, x13, x12x 2, x1x 22, x 23, x14, x13x 2, x12x 22, x1x 23, x 24}

On construit les bases locales :
X E2
X E1

= {x 22, x1x 22, x 23, x1x 23, x12x 22, x 24}
= {x12, x13, x12x 2, x13x 2, x14}

X E0


= {1, x1, x 2, x1x 2}

Alors :

Les
2

U

i =0

E2
E1

= {1, x1, x 2, x1x 2, x12, x 22}
= {1, x1, x 2, x1x 2, x12}

E0

= {1, x1, x 2, x1x 2}

indices

par

colonnes

sont


les

monômes

de

Ei :

Van Thoi TRAN

-16-


Implicitation de surfaces rationnelles

METHODES D’IMPLICITATION

{1, x1, x 2, x1x 2 | 1, x1, x 2, x1x 2, x12 | 1, x1, x 2, x1x 2, x12, x 22}
1442443 144424443 14444244443
E0

E1

E2

Les indices par lignes sont les monômes de XF en
ordre équivalent :
{1, x1, x2, x1x 2 | x12, x13, x12x2, x13x 2, x14 | x22, x1x 22, x23, x1x23, x12x22, x 24}
1442443 144444244444
3 1444444

424444444
3
X E0

X E1

Effectuer

X E2

l’application

(1),

puis

classifier

les

coefficients de ses images dans la matrice M, on obtient
une

matrice

divisée

en

3


blocs

de

tailles

4,

5,

6

dépendant respectivement des coefficients de f0, f1, f2 :
⎡c0,0
⎢
⎢c0,1
⎢c0,2
⎢
⎢c0,4
⎢c0,3
⎢
⎢ 0
⎢ 0
⎢
⎢ 0
⎢ 0
⎢
⎢c0,5
⎢

⎢ 0
⎢ 0
⎢
⎢ 0
⎢ 0
⎢
⎢⎣ 0

0

0

c0,0 0
0 c0,0

0 c1,0

0

0

0 c1,1 c1,0 0
0 c1,2 0 c1,0

0
0
0

c0,2 c0,1 c0,0 c1,4 c1,2 c1,1 c1,0
c0,1

c0,3

0
0

0 c1,3 c1,1
0 0 c1,3

c0,4 c0,3 c0,1
0
0

0
0

0

c0,2

c0,3
0

0
0
0

0
0

c1,4 c1,3 c1,1


0 c1,5

c0,5 c0,4 c0,2
0
0

0

0
0

0
0

0
0

0

c1,2

0 c2,0 0
0 c2,1 c2,0

c1,3 c1,4 0
0 c1,3 0
0
0 c2,5


0

0

0

0

0

0

0

0

0

c1,4 c1,5
0

0
0

0

0

0


0
0

0
c2,2

c2,3 c2,4
0
0

c2,3
0

c2,5

0

0
0

0
0

0
0

0

0


0

0

c0,4

0

0

0
0

0

0

0

c1,5 0
0 c1,5

0

0

c2,5 c2,4 c2,2

0


0
0

0

0 c2,0
c1,0 c2,3 c2,1 0
0 c2,1
c1,1 0 c2,3 0
c1,2 0 c2,4 c2,3 c2,1 c2,2

0

0
0

0

0 c2,2 0 c2,0 0
0 c2,4 c2,2 c2,1 c2,0

c1,5 c1,4 c1,2

c0,5 0
0 c0,5

0

0


c2,5 0
c2,4 c2,5
0

0

0 ⎤
⎥
0 ⎥
0 ⎥
⎥
0 ⎥
0 ⎥
⎥
c2,0 ⎥
0 ⎥
⎥
0 ⎥
0 ⎥⎥
c2,0 ⎥
⎥
c2,1 ⎥
c2,2 ⎥
⎥
c2,4 ⎥
c2,3 ⎥
⎥
c2,5 ⎥⎦

Nous remarquons qu’aucun terme de la diagonal de la

matrice M n’est nul.

Van Thoi TRAN

-17-


Implicitation de surfaces rationnelles

METHODES D’IMPLICITATION

3.1.2 Lien avec le problème d’implicitation
Alors comment peut-on obtenir l’équation implicite d’une surface en utilisant
la matrice de Macaulay ? D’abord, on prend la paramétrisation de surface S sous
forme :
p1 (t 0 , t1 ) p 2 (t 0 , t1 ) p3 (t 0 , t1 )
,
,
p0 (t 0 , t1 ) p0 (t 0 , t1 ) p 0 (t 0 , t1 )

Il faut ici remarquer que la méthode basée sur le résultant multivarié n’est
applicable que dans le cas où il n’existerait pas de point base. Alors p0 (t0 , t1 ) ≠ 0
pour tous (t 0 , t1 ) ∈ Κ 2 − W avec K corps, W = {(t 0 , t1 ) ∈ K 2 / p (t 0 , t1 ) = 0} . On pose :
f1 (t 0 , t1 ) =
f 2 (t 0 , t1 ) =
f 3 (t 0 , t1 ) =

p 0 (t 0 , t1 ) x −
p 0 (t 0 , t1 ) y −
p 0 (t 0 , t1 ) z −


p1 (t 0 , t1 )
p 2 (t 0 , t1 )
p 3 (t 0 , t1 )

En appliquant la construction de la matrice de Macaulay sur les polynômes
f1, f2, f3 en les variables (t0, t1), on obtient la matrice M dont le déterminant est un
multiple non-nul du résultant Res( f , f
1

2 , f3 )

[2] :

D M = Res ( f1 , f 2 , f 3 ) ( x, y , z ) ⋅ DS M

où Res ( f , f
1

2 , f3 )

(2)

( x, y , z ) désigne une puissance de l’équation implicite de S et D S M est

le déterminant d’une sous-matrice carrée SM de la matrice M.
Cette sous-matrice SM est construite en :
1. Cherchant dans XF l’ensemble XE’ des monômes m’ satisfaisant : m’ est
divisible à la fois par deux monômes xi d et x j d (1≤ i ≠ j≤ n ), ou m’ est
i


j

divisible par le monôme xi d (1≤ i ≤ n ) et dm’ ≤ v-d0 avec dm’ degré total
i

du monôme m’.

Van Thoi TRAN

-18-


Implicitation de surfaces rationnelles

METHODES D’IMPLICITATION

2. Associant les monômes dans XE’ avec les monômes dans XF par ligne, et
avec les monômes X E (1≤ i ≤ n ) par colonne.
i

Le paragraphe ci-dessous nous montre un exemple de trouver ce mineur SM.

‰

Exemple 2.
On revient à l’exemple 1. L’ensemble XF est :
{1, x1, x 2, x12, x1x 2, x 22, x13, x12x 2, x1x 22, x 23, x14, x13x 2, x12x 22, x1x 23, x 24}

Les monômes considérés dans XE’ :

{x12, x 22, x12x 22}

En associant avec les coefficients de M :
⎡c0,0
⎢
⎢c0,1
⎢c0,2
⎢
⎢c0,4
⎢c0,3
⎢
⎢ 0
⎢ 0
⎢
⎢ 0
⎢ 0
⎢
⎢c0,5
⎢
⎢ 0
⎢ 0
⎢
⎢ 0
⎢ 0
⎢
⎢⎣ 0

0

0


c0,0 0
0 c0,0

0

c1,0

0
0

c1,1
c1,2

c0,2 c0,1 c0,0 c1,4
c0,1
c0,3

0
0

0

c0,3
0

0
0

0

0

0

c0,2

0 c 1,5

0
0
0

c1,2 c1,1 c1,0
0
0

0
0

c1,4 c1,3 c1,1
0
0

0
0

0

c1,2


0 c2,0
0 c2,1

0

0

0

0

c2,0

0

0

0

0 c2,2
0 c2,4

0 c2,0 0
c2,2 c2,1 c2,0

c 2,0

c1,3 c1,4 0
0 c1,3 0
0

0 c 2,5

0

c0,4

0

0

0

0

0

0

0

0

0

c1,4 c1,5
0

0

c2,4


0
0

0
c2,2

0
0

c2,3
0

0

0

0
0

0
0

0
0

c2,5
c2,4

0

c 2,5

0

0

0

0

0

0

0

c2,3

c2,5

0
0

0
0

0

0


c1,5 0
0 c1,5

0
0

0

0

0

c0,5 0
0 c0,5

c2,1
c2,2

c2,5 c2,4 c2,2

0

0

0
0

0
c1,0 c 2,3 c2,1 0
0

c1,1 0 c2,3 0
c1,2 0 c2,4 c2,3 c2,1

c1,5 c1,4 c1,2

c0,5 c0,4 c0,2
0
0

0

c1,0 0
0 c1,0

0 c 1,3 c1,1
0 c1,3
0

c0,4 c0,3 c0,1
0
0

0

0 ⎤
⎥
0 ⎥
0 ⎥
⎥
0 ⎥

0 ⎥
⎥
c2,0 ⎥
0 ⎥
⎥
0 ⎥
0 ⎥⎥
c2,0 ⎥
⎥
c2,1 ⎥
c2,2 ⎥
⎥
c2,4 ⎥
c2,3 ⎥
⎥
c2,5 ⎥⎦

L’extrait des coefficients soulignés nous donne la
sous-matrice SM :

Van Thoi TRAN

-19-


Implicitation de surfaces rationnelles

METHODES D’IMPLICITATION

⎡c1,3 c2,3 c2,0 ⎤

⎥
⎢
⎢c1,5 c2,5 0 ⎥
⎢⎣ 0
0 c2,5 ⎥⎦

Selon (2), on a trouvé Res ( f , f
1

de la surface S. Alors Res ( f , f
1

2 , f3 )

2 , f3 )

( x, y , z ) une puissance de l’équation implicite

( x, y , z ) est de la forme :

Res( f1 , f 2 , f 3 ) ( x, y, z ) = (F ( x, y, z ) )

k

où F désigne exactement l’équation implicite de S, k ∈ N-{0}. Si la paramétrisation
de S est propre (c’est-à-dire elle induit une bijection entre un ouvert dense de
l’espace des paramètres et un ouvert dense de la surface), k est égal à 1.

3.1.3 Remarques
Par construction, la taille de la matrice de Macaulay est strictement égale au

nombre de monômes dans XF et ce nombre-ci augmente très rapidement [2] en
fonction des degrés de la paramétrisation. Cela montre les limites d’application de
cette méthode.
L’autre problème, majeur, est que l’approche de Macaulay échoue toujours
en présence de points bases. C’est pourquoi, la méthode basée sur la matrice
Bézoutienne, que l’on va voir dans le paragraphe suivant, est considérée comme une
bonne solution pour le problème d’implicitation en présence de points bases, et avec
un calcul semble-t-il moins coûteux.

3.2 Implicitation et Bézoutiens
Comme on a vu dans la partie précédente, la méthode basée sur Macaulay est
critique dans le cas de points bases, et le calcul est très coûteux. Alors les
Bézoutiens nous conduisent à une méthode d’implicitation qui fonctionnera quand
même dans le cas de points bases, avec un calcul évidemment réduit.

Van Thoi TRAN

-20-


Implicitation de surfaces rationnelles

METHODES D’IMPLICITATION

3.2.1 Bézoutiens
On va voir d’abord comment se construisent les Bézoutiens des polynômes
f0, …, fn dans K[x]. Considérons l’application polynomiale :
f : Kn
x


→ Kn

a f(x) = ( f 1 (x),K , f n (x))

Etant donnés x = (x1,…, xn) et y = (y1,…, yn), on note :
x(0) = (x1,…, xn) , x(1) = (y1, x2,…, xn),…, x(n) = (y1,…, yn)
Pour tout polynôme f ∈ R, on introduit la i-ème différence divisée de f :
θ j ( fi ) =

f i (x ( j ) ) − f i (x ( j −1) )
yj − xj

avec 1≤ j ≤ n

Alors on a la définition suivante :
Définition 1 : Le Bézoutien de n+1 polynômes f0, f1,…, fn de R est le
polynôme Θ f

0 ,K, f n

de R ⊗ Κ R donné par :

Θ f 0 ,K, f n =

f 0 (x ( 0) ) θ 1 ( f 0 ) L θ n ( f 0 )
M

M

M


f n (x ( 0) ) θ 1 ( f n ) L θ n ( f n )

Θ f 0 ,K, f n est un polynôme en variables x, y de degré au plus

∑

n

i =0

deg( f i ) − n

qui se décompose sous la forme :
Θ f 0 ,K, f n = ∑ θ αβ x α y β ,
α ,β

θ α ,β ∈ Κ

Nous ordonnons les monômes qui existent dans Θ f
bézoutienne de f0,…, fn est la matrice des coefficients Β f

0 ,K, f n

0 ,K, f n

. Alors la matrice

= (θ αβ ) α , β , (également


noté B f lorsque f1,…,fn sont fixes).
0

Van Thoi TRAN

-21-


Implicitation de surfaces rationnelles

METHODES D’IMPLICITATION

L’exemple suivant nous montre une construction du Bézoutien et de la
matrice bézoutienne associée :

‰

Exemple 3.
Soit 2 polynômes en une variable :
f0

= 1 + 2x + x 3

f1

=

− 5 + 3x 2

Par l’introduction de variable y, le Bézoutien de

f0, f1 est :
Θ f0,f1

=

1 + 2x + x 3 2 + x 2 + xy + y 2

− 5 + 3x 2
3x + 3y
2
= 10 + 3x + 3y + 5x + 11xy + 5y 2 − 3x 2y 2

Et la matrice bézoutienne est :
5 ⎤
⎡10 3
⎢
B = ⎢ 3 11 0 ⎥⎥
⎢⎣ 5 0 − 3⎥⎦

Soit maintenant v = (vi )i∈N , w = (w j ) j∈N deux K-bases de R. et soit
Θ f 0 ,K, f n = ∑ λij vi ⊗ w j , λ ij ∈ Κ
i, j

la décomposition du Bézoutien dans ces bases. La matrice des coefficients (λij)i ,j
sera notée par B v,f w,K, f . La proposition suivante prouve que la matrice bézoutienne
0

n

B f 0 , pour tout f0 ∈ R, admet une décomposition diagonale dans une base commune.


Van Thoi TRAN

-22-


Implicitation de surfaces rationnelles

METHODES D’IMPLICITATION

Proposition 1 : Soit I =(f1,…, fn) un idéal de R tel que le K-espace
vectoriel A = R / I soit de dimension finie D. Alors il existe deux bases

(

)(

)

v = (vi )i∈N et w = (w j ) j∈N de R telles que v1 , K , v D , w1 , K , wD soient des

bases de A, vi , wi ∈ Ι pour i >D, et telles que pour tout f0 dans R on ait la
matrice B v,f w,K, f qui soit de la forme :
0

⎛
⎜
⎜
⎜
⎜

⎜
⎜
⎜
⎜
⎝

n

v1 L v D
M f0

0

v D +1 L
⎞ w1
⎟
0
⎟ M
⎟ w
⎟ D
⎟ wD +1
⎟ M
L f0
⎟
⎟
⎠

où M f est la matrice de multiplication par f0 dans la base (v1 , K , v D ) de
0


A.

3.2.2 Application à l’implicitation
Dans cette section, on va voir une application des matrices bézoutiennes à
l’implicitation. Il est connu qu’un mineur maximal d’une matrice bézoutienne
convenable donne un multiple de l’équation implicite d’une hypersurface
rationnelle donnée par une représentation paramétrique.
Considérons l’hypersurface suivante :
⎧ x1
⎪
S:⎨
⎪x
⎩ n

=

p1 (t ) / p 0 (t )
M

=

p n (t ) / p 0 (t )

où p0, …, pn ∈ K[t] = K[t1,…, tn-1].

Van Thoi TRAN

-23-



Implicitation de surfaces rationnelles

METHODES D’IMPLICITATION

On définit fi(t) = p0(t) xi – pi(t), ∀i ∈ {1,…, n} des polynômes de K[x][t].
Ces polynômes définissent un ensemble algébrique dans Kn-1×Kn appelé graphe de
S:

Figure 1 : Graphe de S

On a la proposition suivante [6] :
Proposition 2 : Tout mineur maximal non nul de la matrice bézoutienne
B( f1 ,..., f n ) est un multiple de l’équation implicite de S.

Dans les algorithmes d’implicitation utilisant un mineur maximal de la
matrice bézoutienne, on obtient naturellement un multiple de l’équation implicite
suite à la proposition ci-dessus. C’est pourquoi il faut ajouter une étape de
factorisation après le calcul du mineur maximal de la matrice bézoutienne afin
d’obtenir l’équation implicite exacte que l’on cherche. Néanmoins, cette
Van Thoi TRAN

-24-


Implicitation de surfaces rationnelles

METHODES D’IMPLICITATION

factorisation se révèle parfois être un facteur limitatif de cette approche. Cela nous
conduit donc à une autre analyse un peu plus fine nous permettant d’obtenir cette

équation implicite en n’utilisant uniquement de l’algèbre et une division.
Soit ∆ un mineur maximal rg × rg de la matrice bézoutienne B( f ,..., f ) (avec rg
1

le rang générique de B( f ,..., f
1

n)

n

). Ce mineur se décompose alors sous la forme ∆ =

∆1∆2 où ∆1 est un mineur provenant de l’opérateur de multiplication par f1 et ∆2 est
un mineur provenant de L f . Le mineur ∆2 ∈ K[x] définit une hypersurface Z2 =
1

Z((∆2)) ⊂ Kn. On sait que Z2 ∩ S est de codimension 1 dans S. Cela signifie que
pour z ∈ Kn générique, on a ∆2(z) ≠ 0. Alors on obtient la proposition suivante [6] :
Proposition 3 : Soit ∆ un mineur maximal rg × rg de B( f ,..., f ) et soit ∆ =
1

n

∆1∆2 la décomposition telle que définie précédemment. Alors ∆1 = ∆ /∆2
est un multiple de l’équation implicite de S.
On a également le corollaire :
Corollaire : Soit ∆ un mineur maximal rg × rg de B( f ,..., f
1


n)

et soit ∆ =

∆1∆2 la décomposition telle que définie précédemment. Alors la partie
sans carré de ∆1 = ∆ /∆2 est l’équation implicite de S.
L’algorithme d’implicitation est donc comme suit :
Entrée : Les polynômes p0,…,pn
1. Poser fi = p0xi – pi , 1≤ i ≤ n.
2. Construire la matrice bézoutienne B f .
1

3. Tirer un point générique z1 dans Kn ; calculer les coordonnées
d’un mineur maximal de B f ( z1 ) ; extraire la sous-matrice B #f
1

1

ayant ces coordonnées et en calculer le déterminant ∆ .

Van Thoi TRAN

-25-