La conception et fabrication assistées par ordinateur (CFAO) est incontournable dans la création et l'élaboration d'un produit. De même, l'infographie est couramment employée en effets spéciaux ou réalité virtuelle. Pourtant, chaque domaine utilise ses propres outils pour modéliser des surfaces. Pour répondre aux contraintes de ces deux types d'utilisations, nous proposons une nouvelle modélisation de surfaces polynomiales, interpolantes, globalement lisses (de plan tangent continu) et hiérarchique. Une surface lisse initiale est d'abord construite sur un maillage triangulaire, ce qui permet de traiter toutes les topologies. Des détails sont ensuite progressivement ajoutés par niveaux. Pour ce faire, chaque face est subdivisée en quatre sous-faces par insertion d'un sommet en milieu d'arête. Ce raffinement n'induit pas de modifications significatives sur la surface. Chaque détail est défini localement par rapport au précédent grâce à l'utilisation de repères locaux. Cette hiérarchie permet à l'ensemble des détails fins de suivre continûment le déplacement lors d'une édition de la surface. Deux applications sont ensuite proposées dans cet ouvrage : Tout d'abord, un modeleur 3D respectant la démarche créative des artistes. Celui-ci repose sur le calcul d'une forme globale progressivement affinée pour obtenir l'objet désiré, et offre la possibilité d'éditer les objets de manière intuitive en modifiant très peu de paramètres. Enfin, un outil de reconstruction est présenté pour modéliser des objets existants grâce à notre nouvelle représentation hiérarchique.

L'objectif général de cette thèse est d'appliquer une méthode d'optimisation polynomiale basée sur la théorie des moments à certains problèmes de vision artificielle. Ces problèmes sont en général non convexes et classiquement résolus à l'aide de méthodes d'optimisation locale. Ces techniques ne convergent généralement pas vers le minimum global et nécessitent de fournir une estimée initiale proche de la solution exacte. Les méthodes d'optimisation globale permettent d'éviter ces inconvénients. L'optimisation polynomiale basée sur la théorie des moments présente en outre l'avantage de prendre en compte des contraintes. Dans cette thèse nous étendrons cette méthode aux problèmes de minimisation d'une somme d'un grand nombre de fractions rationnelles. De plus, sous certaines hypothèses de "faible couplage" ou de "parcimonie" des variables du problème, nous montrerons qu'il est possible de considérer un nombre important de variables tout en conservant des temps de calcul raisonnables. Enfin nous appliquerons les méthodes proposées aux problèmes de vision par ordinateur suivants : minimisation des distorsions projectives induites par le processus de rectification d'images, estimation de la matrice fondamentale, reconstruction 3D multi-vues avec et sans distorsions radiales.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

L'objectif de cette thèse porte sur des recherches théoriques et algorithmiques d'optimisation locale et globale via les techniques de programmation DC & DCA, Séparation et Evaluation (SE) ainsi que les techniques de relaxation DC/SDP, pour résoudre plusieurs types de problèmes d'optimisation non convexe (notamment en Optimisation Combinatoire et Optimisation Polynomiale). La thèse comporte quatre parties :La première partie présente les outils fondamentaux et les techniques essentielles en programmation DC & l'Algorithme DC (DCA), ainsi que les techniques de relaxation SDP, et les méthodes de séparation et évaluation (SE).Dans la deuxième partie, nous nous intéressons à la résolution de problèmes de programmation quadratique et linéaire mixte en variables entières. Nous proposons de nouvelles approches locales et globales basées sur DCA, SE et SDP. L'implémentation de logiciel et des simulations numériques sont aussi étudiées.La troisième partie explore des approches de la programmation DC & DCA en les combinant aux techniques SE et SDP pour la résolution locale et globale de programmes polynomiaux. Le programme polynomial avec des fonctions polynomiales homogènes et son application à la gestion de portefeuille avec moments d'ordre supérieur en optimisation financière ont été discutés de manière approfondie dans cette partie.Enfin, nous étudions dans la dernière partie un programme d'optimisation sous contraintes de type matrices semi-définies via nos approches de la programmation DC. Nous nous consacrons à la résolution du problème de réalisabilité des contraintes BMI et QMI en contrôle optimal.L'ensemble de ces travaux a été implémenté avec MATLAB, C/C++ ... nous permettant de confirmer l'utilisation pratique et d'enrichir nos travaux de recherche.

Cette thèse présente une étude des systèmes dynamiques polynomiaux motivée à la fois par le grand spectre d'applications de cetteclasse (modèles de réactions chimiques, modèles de circuits électriques ainsi que les modèles biologiques) et par la difficulté (voire incapacité)de la résolution théorique de tels systèmes. Dans une première partie préliminaire, nous présentons les polynômes multi-variés et nous introduisons les notions de forme polaire d'un polynôme (floraison) et de polynômes de Bernstein qui seront d'un grand intérêt par la suite. Dans une deuxième partie, nous considérons le problème d'optimisation polynomial dit POP. Nous décrivons dans un premier temps les principales méthodes existantes permettant de résoudre ou d'approcher la solution d'un tel problème. Puis, nous présentons deux relaxations linéaires se basant respectivement sur le principe de floraison ainsi que les polynômes de Bernstein permettant d'approcher la valeur optimale du POP. La dernière partie de la thèse sera consacré aux applications de nos deux méthodes de relaxation dans le cadre des systèmes dynamiques polynomiaux. Une première application s'inscrit dans le cadre de l'analyse d'atteignabilité: en effet, on utilisera notre relaxation de Bernsteinpour pouvoir construire un algorithme permettant d'approximer les ensembles atteignables d'un système dynamique polynomial discrétisé. Une deuxième application sera la vérification et le calcul d'invariants pour un système dynamique polynomial. Une troisième application consiste à calculer un contrôleur et un invariant pour un système dynamique polynomial soumis à des perturbations. Dans le contexte de l'invariance, on utilisera la relaxation se basant sur le principe de floraison.Enfin, une dernière application sera d'exploiter les principales propriétés de la forme polaire pour pouvoir étudier des systèmes dynamiques polynomiaux dans des rectangles. / This thesis presents a study of polynomial dynamical systems motivated by both thewide spectrum of applications of this class (chemical reaction models, electrical modelsand biological models) and the difficulty (or inability) of theoretical resolutionof such systems.In a first preliminary part, we present multivariate polynomials and we introducethe notion of polar form of a polynomial (blossoming) and Bernstein polynomialswhich will be of great interest thereafter.In a second part, we consider the polynomial optimization problem said POP.We first describe existing methods allowing us to solve or approximate the solution5TABLE DES MATI`ERES 6of such problems. Then, we present two linear relaxations based respectively on theblossoming principle and the Bernstein polynomials allowing us to approximate theoptimal value of the POP.The last part of the thesis is devoted to applications of the two relaxation methodsin the context of polynomial dynamical systems. A first application is in thecontext of reachability analysis. In fact, we use our Bernstein relaxation in order tobuild an algorithm allowing us to approximate the reachable sets of a discretizedpolynomial dynamical system. A second application deals with the verification andthe computation of invariants for polynomial dynamical systems. A third applicationconsists in calculating a controller and an invariant for a polynomial dynamicalsystem subject to disturbances. For the invariance problem, we use the relaxationbased on the blossoming principle. Finally, the last application consists in exploitingthe main properties of the polar form in order to study polynomial dynamicalsystems in rectangles.

Dans cette thèse, on s'intéresse aux systèmes dynamiques holomorphes dépendants de paramètres. Notre objectif est de contribuer à une théorie de la stabilité et des bifurcations en plusieurs variables complexes, généralisant celle des applications rationnelles fondées sur les travaux de Mané, Sad, Sullivan et Lyubich. Pour une famille d'applications d'allure polynomiale, on prouve l'équivalence de plusieurs notions de stabilité, entre autres une version asymptotique du mouvement holomorphe des cycles répulsifs et d'un sous-ensemble de l'ensemble de Julia de mesure pleine. Cela peut etre considéré comme une généralisation mesurable à plusieurs variables du célèbre lambda-lemme et nous permet de dégager un concept cohérent de stabilité dans ce cadre. Après avoir compris les bifurcations holomorphes, on s'intéresse à la continuité Hausdorff des ensembles de Julia. Nous relions cette propriété à l'existence de disques de Siegel dans l'ensemble de Julia, et donnons un exemple de ce phénomène. Finalement, on étudie la continuité du point de vue de l'implosion parabolique. Nous établissons un théorème de Lavaurs deux-dimensionel, ce qui nous permet d'étudier des phénomènes de discontinuité pour des perturbations d'applications tangentes à l'identité. / In this thesis we study holomorphic dynamical systems depending on parameters. Our main goal is to contribute to the establishment of a theory of stability and bifurcation in several complex variables, generalizing the one for rational maps based on the seminal works of Mané, Sad, Sullivan and Lyubich. For a family of polynomial like maps, we prove the equivalence of several notions of stability, among the others an asymptotic version of the holomorphic motion of the repelling cycles and of a full-measure subset of the Julia set. This can be seen as a measurable several variables generalization of the celebrated lambda-lemma and allows us to give a coherent definition of stability in this setting. Once holomorphic bifurcations are understood, we turn our attention to the Hausdorff continuity of Julia sets. We relate this property to the existence of Siegel discs in the Julia set, and give an example of such phenomenon. Finally, we approach the continuity from the point of view of parabolic implosion and we prove a two-dimensional Lavaurs Theorem, which allows us to study discontinuities for perturbations of maps tangent to the identity.

Dans un graphe orienté contenant un nœud appelé racine, un sous ensemble de nœuds appelés terminaux et une pondération sur les arcs, le problème de l’arborescence de Steiner (DST) consiste en la recherche d’une arborescence de poids minimum contenant pour chaque terminal un chemin de la racine vers ce terminal. Ce problème est NP-Complet. Cette thèse se penche sur l’étude de l’approximabilité de ce problème. Sauf si P=NP, il n’existe pas pour ce problème d’approximation de rapport constant ou logarithmique en k, oú k est le nombre de terminaux. Le plus petit rapport d’approximation connu est O (k") où " est un réel strictement positif. Dans la première partie, nous donnons trois algorithmes d’approximation : un algorithme glouton efficace qui associe deux techniques d’approximations connues pour DST, un algorithme dans le cas des graphes structurés en paliers qui étudie l’approximabilité du problème quand les terminaux sont éloignés de la racine, et un algorithme exponentiel qui combine un algorithme d’approximation et un algorithme exact, dont le rapport d’approximation et la complexité temporelle sont paramétrés par le nombre de terminaux couverts par l’algorithme exact. Dans la seconde partie, nous étudions deux problèmes issus de DST auquel est ajoutée une contrainte sur les nœuds de branchement. Cette contrainte réduit le nombre de solutions réalisables et peut faciliter la recherche d’une solution optimale parmi ce sous-ensemble de solutions. En fonction de la contrainte, nous étudions la possibilité de la trouver en temps polynomial et quel est le rapport d’approximation entre cette solution et la solution du problème non contraint / The directed Steiner tree problem (DST) asks, considering a directed weighted graph, a node r called root and a set of nodes X called terminals, for a minimum cost directed tree rooted in r spanning X. DST is an NP-complete problem. We are interested in the search for polynomial approximations for DST. Unless P = NP, DST can not be approximated neither within a constant ratio nor a logarithmic ratio with respected to k, where k is the number of terminals. The smallest known approximation ratio is O(kԑ)$ where ԑ is a positive real.In the first part, we provide three new approximation algorithms : a practical greedy algorithm merging two of the main approximation techniques for DST, an algorithm for the case where the graph is layered and where the distance between the terminals and the root is high, and an exponential approximation algorithm combining an approximation algorithm and an exact algorithm, parameterized with the number of terminals the exact algorithm must cover.In the last part we study DST with two branching constraints. With this technique, we are able to reduce the number of feasible solutions, and possibly facilitate the search for an optimal solution of the constraint problem. We study how it is possible to build such a solution in polynomial time and if this solution is a good approximation of an optimal solution of the non-constraint problem

L'objectif de ce travail de thèse est le développement d'une approximation polynomiale axiale dans un solveur basé sur la Méthode des Caractéristiques. Le contexte, est celui de la solution stationnaire de l'équation de transport des neutrons pour des systèmes critiques, et l'implémentation pratique a été réalisée dans le solveur "Two/three Dimensional Transport" (TDT), faisant partie du projet APOLLO3®. Un solveur MOC pour des géométries en trois dimensions a été implémenté dans ce code pendant un projet de thèse antécédent, se basant sur une approximation constante par morceaux du flux et des sources des neutrons. Les développements présentés dans la suite représentent la continuation naturelle de ce travail. Les solveurs MOC en trois dimensions sont capables de produire des résultats précis pour des géométries complexes. Bien que précis, le coût computationnel associé à ce type de solveur est très important. Une représentation polynomiale en direction axiale du flux angulaire des neutrons a été utilisée pour réduire ce coût computationnel.Le travail réalisé pendant cette thèse peut être considéré comme divisé en trois parties: transport, accélération et autres. La première partie est constituée par l'implémentation de l'approximation polynomiale choisie dans les équations de transmission et de bilan typiques de la Méthode des Caractéristiques. Cette partie a aussi été caractérisée par le calcul d'une série de coefficients numériques qui se sont révélés nécessaires afin d'obtenir un algorithme stable. Pendant la deuxième partie, on a modifié et implémenté la solution des équations de la méthode d'accélération DPN. Cette méthode était déjà utilisée pour l'accélération et des itérations internes et externes dans TDT pour les solveurs deux et trois dimensionnels avec l'approximation des flux plat, quand ce travail a commencé. L'introduction d'une approximation polynomiale a demandé plusieurs développements numériques regardant la méthode d'accélération. Dans la dernière partie de ce travail on a recherché des solutions pour un mélange de différents problèmes liés aux premières deux parties. En premier lieux, on a eu à faire avec des instabilités numériques associées à une discrétisation spatiale ou angulaire pas suffisamment précise, soit pour la partie transport que pour la partie d'accélération. Ensuite, on a essayé d'utiliser différentes méthodes pour réduire l'empreinte mémoire des coefficients d'accélération. L'approche qu'on a finalement choisie se base sur une régression non-linéaire au sens des moindres carrés de la dépendance en fonction des sections efficaces typique de ces coefficients. L'approche standard consiste dans le stockage d'une série de coefficients pour chaque groupe d'énergie. La méthode de régression permet de remplacer cette information avec une série de coefficients calculés pendant la régression qui sont utilisés pour reconstruire les matrices d'accélération au cours des itérations. Cette procédure ajoute un certain coût computationnel à la méthode, mais nous pensons que la réduction de la mémoire rende ce surcoût acceptable.En conclusion, le travail réalisé a été concentré sur l'application d'une simple approximation polynomiale avec l'objectif de réduire le coût computationnel et l'empreinte mémoire associées à un solveur basée sur la Méthodes des Caractéristiques qui est utilisé pour calculer le flux neutroniques pour des géométries à trois dimensions extrudées. Même si cela ne constitue pas une amélioration radicale des performances, l'approximation d'ordre supérieur qu'on a introduit permet une réduction en termes de mémoire et de temps de calcul d'un facteur compris entre 2 et 5, selon le cas. Nous pensons que ces résultats constitueront une base fertile pour des futures améliorations. / The purpose of this PhD is the implementation of an axial polynomial approximation in a three-dimensional Method Of Characteristics (MOC) based solver. The context of the work is the solution of the steady state Neutron Transport Equation for critical systems, and the practical implementation has been realized in the Two/three Dimensional Transport (TDT) solver, as a part of the APOLLO3® project. A three-dimensional MOC solver for 3D extruded geometries has been implemented in this code during a previous PhD project, relying on a piecewise constant approximation for the neutrons fluxes and sources. The developments presented in the following represent the natural continuation of this work. Three-dimensional neutron transport MOC solvers are able to produce accurate results for complex geometries. However accurate, the computational cost associated to this kind of solvers is very important. An axial polynomial representation of the neutron angular fluxes has been used to lighten this computational burden.The work realized during this PhD can be considered divided in three major parts: transport, acceleration and others. The first part is constituted by the implementation of the chosen polynomial approximation in the transmission and balance equations typical of the Method Of Characteristics. This part was also characterized by the computation of a set of numerical coefficients which revealed to be necessary in order to obtain a stable algorithm. During the second part, we modified and implemented the solution of the equations of the DPN synthetic acceleration. This method was already used for the acceleration of both inners and outers iteration in TDT for the two and three dimensional solvers at the beginning of this work. The introduction of a polynomial approximation required several equations manipulations and associated numerical developments. In the last part of this work we have looked for the solutions of a mixture of different issues associated to the first two parts. Firstly, we had to deal with some numerical instabilities associated to a poor numerical spatial or angular discretization, both for the transport and for the acceleration methods. Secondly, we tried different methods to reduce the memory footprint of the acceleration coefficients. The approach that we have eventually chosen relies on a non-linear least square fitting of the cross sections dependence of such coefficients. The default approach consists in storing one set of coefficients per each energy group. The fit method allows replacing this information with a set of coefficients computed during the regression procedure that are used to re-construct the acceleration matrices on-the-fly. This procedure of course adds some computational cost to the method, but we believe that the reduction in terms of memory makes it worth it.In conclusion, the work realized has focused on applying a simple polynomial approximation in order to reduce the computational cost and memory footprint associated to a Method Of Characteristics solver used to compute the neutron fluxes in three dimensional extruded geometries. Even if this does not a constitute a radical improvement, the high order approximation that we have introduced allows a reduction in terms of memory and computational times of a factor between 2 and 5, depending on the case. We think that these results will constitute a fertile base for further improvements.

La multiplication de polynômes est une opération fondamentale en théorie de la complexité. En effet, pour de nombreux problèmes d’arithmétique, la complexité des algorithmes s’exprime habituellement en fonction de la complexité de la multiplication. Un meilleur algorithme de multiplication permet ainsi d’effectuer les opérations concernées plus rapidement. Un résultat de 2016 a établi une meilleure complexité asymptotique pour la multiplication de polynômes dans des corps finis. Cet article constitue le point de départ de la thèse ; l’objectif est d’étudier les conséquences à la fois théoriques et pratiques de la nouvelle borne de complexité.La première partie s’intéresse à la multiplication de polynômes à une variable. Cette partie présente deux nouveaux algorithmes censés accélérer le calcul en pratique (plutôt que d’un point de vue asymptotique). S’il est difficile dans le cas général d’observer l’amélioration prévue, certains cas précis sont particulièrement favorables. En l’occurrence, le second algorithme proposé, spécifique aux corps finis, conduit à une meilleure implémentation de la multiplication dans F_2[X], environ deux fois plus rapide que les logiciels précédents.La deuxième partie traite l’arithmétique des polynômes à plusieurs variables modulo un idéal, telle qu’utilisée par exemple pour la résolution de systèmespolynomiaux. Ce travail suppose une situation simplifiée, avec seulement deux variables et sous certaines hypothèses de régularité. Dans ce cas particulier, la deuxième partie de la thèse donne des algorithmes de complexité asymptotiquement optimale (à des facteurs logarithmiques près), par rapport à la taille des entrées/sorties. L’implémentation pour ce cas spécifique est alors nettement plus rapide que les logiciels généralistes, le gain étant de plus en plus marqué lorsque la taille de l’entrée augmente. / The multiplication of polynomials is a fundamental operation in complexity theory. Indeed, for many arithmetic problems, the complexity of algorithms is expressed in terms of the complexity of polynomial multiplication. For example, the complexity of euclidean division or of multi-point evaluation/interpolation (and others) is often expressed in terms of the complexity of polynomial multiplication. This shows that a better multiplication algorithm allows to perform the corresponding operations faster. A 2016 result gave an improved asymptotic complexity for the multiplication of polynomials over finite fields. This article is the starting point of the thesis; the present work aims to study the implications of the new complexity bound, from a theoretical and practical point of view.The first part focuses on the multiplication of univariate polynomials. This part presents two new algorithms that should make the computation faster in practice (rather than asymptotically speaking). While it is difficult in general to observe the predicted speed-up, some specific cases are particularly favorable. Actually, the second proposed algorithm, which is specific to finite fields, leads to a better implementation for the multiplication in F 2 [X], about twice as fast as state-of-the-art software.The second part deals with the arithmetic of multivariate polynomials modulo an ideal, as considered typically for polynomial system solving. This work assumes a simplified situation, with only two variables and under certain regularity assumptions. In this particular case, there are algorithms whose complexity is asymptotically optimal (up to logarithmic factors), with respect to input/output size. The implementation for this specific case is then significantly faster than general-purpose software, the speed-up becoming larger and larger when the input size increases.

L’objectif général de cette thèse est d’appliquer une méthode d’optimisation polynomiale basée sur la théorie des moments à certains problèmes de vision artificielle. Ces problèmes sont en général non convexes et classiquement résolus à l’aide de méthodes d’optimisation locales Ces techniques ne convergent généralement pas vers le minimum global et nécessitent de fournir une estimée initiale proche de la solution exacte. Les méthodes d’optimisation globale permettent d’éviter ces inconvénients. L’optimisation polynomiale basée sur la théorie des moments présente en outre l’avantage de prendre en compte des contraintes. Dans cette thèse nous étendrons cette méthode aux problèmes de minimisation d’une somme d’un grand nombre de fractions rationnelles. De plus, sous certaines hypothèses de "faible couplage" ou de "parcimonie" des variables du problème, nous montrerons qu’il est possible de considérer un nombre important de variables tout en conservant des temps de calcul raisonnables. Enfin nous appliquerons les méthodes proposées aux problèmes de vision par ordinateur suivants : minimisation des distorsions projectives induites par le processus de rectification d’images, estimation de la matrice fondamentale, reconstruction 3D multi-vues avec et sans distorsions radiales. / The overall objective of this thesis is to apply a polynomial optimization method, based on moments theory, on some vision problems. These problems are often nonconvex and they are classically solved using local optimization methods. Without additional hypothesis, these techniques don’t converge to the global minimum and need to provide an initial estimate close to the exact solution. Global optimization methods overcome this drawback. Moreover, the polynomial optimization based on moments theory could take into account particular constraints. In this thesis, we extend this method to the problems of minimizing a sum of many rational functions. In addition, under particular assumptions of "sparsity", we show that it is possible to deal with a large number of variables while maintaining reasonable computation times. Finally, we apply these methods to particular computer vision problems: minimization of projective distortions due to image rectification process, Fundamental matrix estimation, and multi-view 3D reconstruction with and without radial distortions.