Proposition de stage
INRIA Sophia-Antipolis, projet SAGA
Plusieurs sous-problèmes qui apparaissent dans l'étude et la résolution de systèmes polynomiaux s'expriment comme de problèmes d'optimisation avec des contraintes linéaires et une fonction linéaire à optimiser. Souvent, il s'agit de points critiques dans le calcul. Le sujet de ce stage serait l'identification de la structure de ces problèmes d'optimisation (ou programmation) linéaire afin de rendre leur solution plus efficace et exploiter la puissance de l'optimisation linéaire. Le but est de bien choisir et utiliser des logiciels existants qui sont performants pour le type de problèmes rencontrés, en les adaptant aux besoins spécifiques de nos programmes.
Plus précisément, dans certains cas, il faut optimiser une série de programmes linéaires qui partagent plusieurs (ou la plupart des) contraintes. Parfois, les mêmes contraintes doivent être résolus pour des fonctions d'optimisation différentes. C'est le cas dans le calcul de racines réelles par la méthode d'intervalles. Pour des systèmes ayant une partie linéaire et une partie non linéaire: en bornant la partie non linéaire a l'aide de l'analyse par intervalles on se ramène a la résolution d'un système compose d'équations linéaires et d'inégalités. Ce type de problème a un intérêt pour les applications et permet d'améliorer considérablement l'efficacité de la résolution. Les programmes développés dans le cadre de ce stage seront intégrés dans la bibliothèque ALIAS en cours de développement dans le projet SAGA et serviront a traiter des applications comme l'analyse des mécanismes de suspension automobile.
Au cours du calcul du volume
mixte et
stable,
qui donnent le nombre générique de racines communes, la résolution
de programmes linéaires prend 80% du temps. Ici encore, les programmes
linéaires partagent plusieurs contraintes ou possèdent d'autres
caractéristiques spéciales, comme par exemple, le grand nombre
de variables par rapport au nombre d'égalités et d'inégalités.
Une autre propriété est
le fait que dans plusieurs occasions l'optimisation n'est pas nécessaire
et la réponse sur la faisabilité des contraintes suffit.
C'est le cas avec la construction de la matrice du résultant creux
qui passe par l'énumération de
points
entiers.
Stations de travail SUN ou DEC, langage
C ou C++.