Après une analyse de la géométrie des solutions, vient une étape de résolution. Nous pouvons distinguer deux types de méthodes, celles travaillant avec les relations (ou les polynômes de l'idéal) et celles manipulant les générateurs (une partie génératrice de ). Par la première approche, utilisant les calculs de bases de Gröbner, on construit un ensemble de polynômes, qui permet de calculer directement la forme normale d'un élément du quotient . Puis le calcul de forme normale d'une liste d'éléments conduit à un polynôme en une variable dont les racines permettent de retrouver les solutions du système initial.
Nous nous pencherons, sur le deuxième type de méthodes qui, nous le pensons est amené a se développer. Cette approche utilise des formulations matricielles, intervenant dans le calcul de résultants, et réduit la recherche des solutions à un calcul de valeurs propres. Cependant, ces techniques ne s'appliquaient jusqu'à présent que dans des cas génériques. L'idée sous-jacente dans cette méthode est de considérer les éléments du quotient , non plus comme des classes d'équivalence, mais comme des opérateurs de multiplication. Une des propriétés fondamentales de ces endomorphismes nous permet d'associer les racines du système aux vecteurs propres communs à tous ces endomorphismes.
Poursuivant l'étude des intersections complètes, basée sur les propriétés des Bézoutiens, nous nous sommes ainsi intéressés à des méthodes permettant de construire les matrices de ces endomorphismes. Nous avons donc étudié les propriétés des matrices de Bézoutien ou de résultants (formule de Macaulay [ M1], des résultants creux [ G]), dans les situations << non-génériques >>. Pour traiter ces cas singuliers, nous proposons de remplacer les manipulations directes sur des générateurs de l'idéal (comme celles effectuées dans un calcul de base de Gröbner), par des transformations des faisceaux de matrices associés à ces polynômes. Cette approche a l'avantage de pouvoir s'appliquer avec des coefficients << approchés >> et bénéficie d'une étude antérieure assez poussée (en particulier sur l'analyse d'erreurs) et d'implémentations efficaces. En effet, la nécessité de pouvoir traiter de manière stable des systèmes polynomiaux avec des coefficients approchés apparaît dans beaucoup d'applications, où les contraintes algébriques sont entachées de bruits (vision, robotique, ...). Dans un travail récent [BMresol97], nous décrivons différentes réductions permettant de transformer, même dans les cas non-génériques, la résolution d'équations non-linéaires en un problème de valeurs et vecteurs propres non-singulier. Une des particularités de cette méthode est que les monômes intervenant dans ces calculs sont connus dès le départ, et les transformations ne font que réduire le nombre de monômes utilisés, contrairement aux bases de Gröbner.
Ces liens entre l'algèbre des polynômes et le calcul numérique étaient jusqu'à présent peu explorés, les calculs comme ceux des bases de Gröbner se faisant sur les nombres rationnels. Ce domaine connaît actuellement une grande activité et nous pensons que l'approche matricielle ci-dessus ouvre de nouveaux champs d'investigations, que ce soit pour la recherche d'algorithmes corrects et rapides pour des problèmes approchés ou pour des applications en robotique, vision, chimie ...Ce type de méthodes a, par exemple, été utilisé pour résoudre numériquement le problème du robot parallèle pour certaines configurations (voir [MB93issac]). Dans [EmMo96RRcyhx], nous comparons différentes formulations matricielles, pour un problème de configuration globale d'une molécule à 6 atomes quand on connaît les longueurs des liaisons et les angles consécutifs entre ces liaisons. Une bibliothèque de programmes de manipulations de faisceaux de matrices, expérimentant les idées précédentes, est en cours d'implémentation (voir [ALP]).
Cette étude nous a conduit à la théorie des matrices structurées. En effet, les matrices issues de problèmes polynomiaux comme les matrices de résultants ou les Bézoutiens, ont une structure qui généralise celle des matrices de Toeplitz ou de Hankel. Les lignes et colonnes sont naturellement indexées par des monômes ou points de . Les matrices de résultants, dont les coefficients ne dépendent que de la différence des indices, généralisent les structures de Toeplitz, au cas multivariable. Les matrices de résidus (où est le résidu et une base de ) ont une structure qui généralise celle des matrices de Hankel dont les coefficients ne dépendent que de la somme des indices. Les matrices de Bézoutien, quant-à-elles, sont les inverses des matrices de résidus. Dans [MoPa96] et [MoPa97], nous avons ainsi dégagé de nouvelles classes de matrices structurées et donné quelques propriétés de ces structures, concernant en particulier les rangs de déplacement. Parmi ces propriétés, notons que la multiplication d'une telle matrice par un vecteur peut se faire de manière rapide (presque linéaire en le nombre de coefficients distincts dans sa représentation). Ceci nous a conduit à un algorithme sélectionnant les racines de systèmes polynomiaux (d'un certain type), nous permettant de réduire la complexité asymptotique d'un ordre de grandeur. Ici encore, le travail est très récent et nous pensons qu'il va conduire à des développements algorithmiques intéressants, à la frontière entre deux domaines ayant jusqu'à présent peu d'interconnexions. En effet, dans le cas d'une variable, les algorithmes optimaux de résolution d'équations polynomiales sont basés sur des méthodes très rapides d'inversion de matrices de Toeplitz ou Hankel, qui utilisent fortement les propriétés des Bézoutiens (voir [ BP]). Dans le cas de plusieurs variables, ces algorithmes ne sont pas encore connus et tout un champ d'investigations reste à explorer, afin par exemple d'obtenir un calcul rapide de forme normale dans ou une multiplication rapide dans le quotient, nous fournissant des algorithmes de résolution numérique optimaux.