Depuis les premiers ordinateurs on est en quête de machines plus rapides, plus puissantes, plus performantes. Après avoir épuisé le filon de l’augmentation de la fréquence, les constructeurs se sont tournés vers les multi-cœurs. Le modèle de calcul actuel repose sur les threads de l'OS qu’on exploite à travers différents langages à constructions parallèles. Cependant, la programmation multithread reste un art délicat car le calcul parallèle découpé en threads souffre d’un grand défaut : il est non déterministe.Pourtant, on peut faire du calcul parallèle déterministe, à condition de remplacer le modèle des threads par un modèle s’appuyant sur l’ordre partiel des dépendances. Dans cette thèse, nous proposons un modèle alternatif d’architecture qui exploite le parallélisme d’instructions (ILP) présent dans les programmes. Nous proposons de nombreuses techniques pour s’affranchir de la plupart des dépendances architecturales et obtenir ainsi un ILP qui croît avec la taille de l’exécution. L’ILP qu’on atteint de cette façon est suffisant pour permettre d’alimenter plusieurs milliers de cœurs. Les dépendances architecturales sérialisantes ayant été supprimées, l’ILP peut être bien mieux exploité que dans les architectures actuelles. Un code VHDL au niveau RTL de l’architecture a été développé pour en mesurer les avantages. Les résultats de synthèse d’un processeur allant de 2 à 64 cœurs montrent que la vitesse du matériel que nous proposons reste constante et que sa surface varie linéairement avec le nombre de cœurs. Cela prouve que le modèle d’interconnexion proposé est extensible. / The pursuit for faster and more powerful machines started from the first computers. After exhausting the increase of the frequency, the manufacturers have turned to another solution and started to introduce multiples cores on a chip. The computational model is today based on the OS threads exploited through different languages offering parallel constructions. However, parallel programming remains an art because the thread management by the operating system is not deterministic.Nonetheless, it is possible to compute in a parallel deterministic way if we replace the thread model by a model built on the partial order of dependencies. In this thesis, we present an alternative architectural model exploiting the Instruction Level Parallelism (ILP) naturally present in applications. We propose many techniques to remove most of the architectural dependencies which leads to an ILP increasing with the execution length. The ILP which is reached this way is enough to allow feeding thousands of cores. Eliminating the architecutral dependencies serializing the run allows to exploit the ILP better than in actual microarchitectures. A VHDL code at the RTL level has been implemented to mesure the benefits of our design. The results of the synthesis of a processeur ranging from 2 to 64 cores are reported. They show that the speed of the proposed material keeps constant and the surface grows linearly with the number of cores : our interconnect solution is scalable.

Dans cette thèse, nous abordons des problèmes NP-difficiles à l'aide de techniques combinatoires, en se focalisant sur le domaine de la complexité paramétrée. Les principaux problèmes que nous considérons sont les problèmes de Multicoupe et d'Arbre Orienté Couvrant avec Beaucoup de Feuilles. La Multicoupe est une généralisation naturelle du très classique problème de coupe, et consiste à séparer un ensemble donné de paires de sommets en supprimant le moins d'arêtes possible dans un graphe. Le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles consiste à trouver un arbre couvrant avec le plus de feuilles possible dans un graphe dirigé. Les résultats principaux de cette thèse sont les suivants. Nous montrons que le problème de Multicoupe paramétré par la taille de la solution est FPT (soluble à paramètre fixé), c'est-à-dire que l'existence d'une multicoupe de taille $k$ dans un graphe à $n$ sommets peut être décidée en temps $f(k)*poly(n)$. Nous montrons que Multicoupe dans les arbres admet un noyau polynomial, c'est-à-dire est réductible aux instances de taille polynomiale en $k$. Nous donnons un algorithme en temps $O^*(3.72^k)$ pour le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles et le premier algorithme exponentiel exact non trivial (c'est-à-dire meilleur que $2^n$). Nous fournissons aussi un noyau quadratique et une approximation à facteur constant. Ces résultats algorithmiques sont basés sur des résultats combinatoires et des propriétés structurelles qui concernent, entre autres, les décompositions arborescentes, les mineurs, des règles de réduction et les $s-t$ numberings. Nous présentons des résultats combinatoires hors du domaine de la complexité paramétrée: une caractérisation des graphes de cercle Helly comme les graphes de cercle sans diamant induit, et une caractérisation partielle des classes de graphes 2-bel-ordonnées. / This thesis tackles NP-hard problems with combinatorial techniques, focusing on the framework of Fixed-Parameter Tractability. The main problems considered here are Multicut and Maximum Leaf Out-branching. Multicut is a natural generalisation of the cut problem, and consists in simultaneously separating prescribed pairs of vertices by removing as few edges as possible in a graph. Maximum Leaf Out-branching consists in finding a spanning directed tree with as many leaves as possible in a directed graph. The main results of this thesis are the following. We show that Multicut is FPT when parameterized by the solution size, i.e. deciding the existence of a multicut of size $k$ in a graph with $n$ vertices can be done in time $f(k)*poly(n)$. We show that Multicut In Trees admits a polynomial kernel, i.e. can be reduced to instances of size polynomial in $k$. We give an $O^*(3.72^k)$ algorithm for Maximum Leaf Out-branching and the first non-trivial (better than $2^n$) exact algorithm. We also provide a quadratic kernel and a constant factor approximation algorithm. These algorithmic results are based on combinatorial results and structural properties, involving tree decompositions, minors, reduction rules and $s-t$ numberings, among others. We present results obtained with combinatorial techniques outside the scope of parameterized complexity: a characterization of Helly circle graphs as the diamond-free circle graphs, and a partial characterisation of 2-well-quasi-ordered classes of graphs.

Dans cette thèse, nous abordons des problèmes NP-difficiles à l'aide de techniques combinatoires, en se focalisant sur le domaine de la complexité paramétrée. Les principaux problèmes que nous considérons sont les problèmes de Multicoupe et d'Arbre Orienté Couvrant avec Beaucoup de Feuilles. La Multicoupe est une généralisation naturelle du très classique problème de coupe, et consiste à séparer un ensemble donné de paires de sommets en supprimant le moins d'arêtes possible dans un graphe. Le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles consiste à trouver un arbre couvrant avec le plus de feuilles possible dans un graphe dirigé. Les résultats principaux de cette thèse sont les suivants. Nous montrons que le problème de Multicoupe paramétré par la taille de la solution est FPT (soluble à paramètre fixé), c'est-à-dire que l'existence d'une multicoupe de taille k dans un graphe à n sommets peut être décidée en temps f(k) ∗ poly(n). Nous montrons que Multicoupe dans les arbres admet un noyau polynomial, c'est-à-dire est réductible aux instances de taille polynomiale en k. Nous donnons un algorithme en temps O∗(3.72k) pour le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles et le premier algorithme exponentiel exact non trivial (c'est-à-dire meilleur que 2n). Nous fournissons aussi un noyau quadratique et une approximation à facteur constant. Ces résultats algorithmiques sont basés sur des résultats combinatoires et des propriétés structurelles qui concernent, entre autres, les décompositions arborescentes, les mineurs, des règles de réduction et les s−t numberings. Nous présentons des résultats combinatoires hors du domaine de la complexité paramétrée: une caractérisation des graphes de cercle Helly comme les graphes de cercle sans diamant induit, et une caractérisation partielle des classes de graphes 2-bel-ordonnées.

L'étude du nombre de points rationnels d'une courbe définie sur un corps fini se divise naturellement en deux cas : lorsque le genre est petit (typiquement g<=50), et lorsqu'il tend vers l'infini. Nous consacrons une partie de cette thèse à chacun de ces cas. Dans la première partie de notre étude nous expliquons comment calculer l'équation de n'importe quel revêtement abélien d'une courbe définie sur un corps fini. Nous utilisons pour cela la théorie explicite du corps de classe fournie par les extensions de Kummer et d'Artin-Schreier-Witt. Nous détaillons également un algorithme pour la recherche de bonnes courbes, dont l'implémentation fournit de nouveaux records de nombre de points sur les corps finis d'ordres 2 et 3. Nous étudions dans la seconde partie une formule de trace d'opérateurs de Hecke sur des formes modulaires quaternioniques, et montrons que les courbes de Shimura associées forment naturellement des suites récursives de courbes asymptotiquement optimales sur une extension quadratique du corps de base. Nous prouvons également qu'alors la contribution essentielle en points rationnels est fournie par les points supersinguliers. / The study of the number of rational points of a curve defined over a finite field naturally falls into two cases: when the genus is small (typically g<=50), and when it tends to infinity. We devote one part of this thesis to each of these cases. In the first part of our study, we explain how to compute the equation of any abelian covering of a curve defined over a finite field. For this we use explicit class field theory provided by Kummer and Artin-Schreier-Witt extensions. We also detail an algorithm for the search of good curves, whose implementation provides new records of number of points over the finite fields of order 2 and 3. In the second part, we study a trace formula of Hecke operators on quaternionic modular forms, and we show that the associated Shimura curves of the form naturally form recursive sequences of asymptotically optimal curves over a quadratic extension of the base field. Moreover, we then prove that the essential contribution to the rational points is provided by supersingular points.

Cette thèse est organisée en trois chapitres. Les deux premiers proposent une approche régularisée pour l’estimation du modèle de données de panel dynamique : l’estimateur GMM et l’estimateur LIML. Le dernier chapitre de la thèse est une application de la méthode de régularisation à l’estimation des élasticités de l’offre de travail en utilisant des modèles de pseudo-données de panel. Dans un modèle de panel dynamique, le nombre de conditions de moments augmente rapidement avec la dimension temporelle du panel conduisant à une matrice de covariance des instruments de grande dimension. L’inversion d’une telle matrice pour calculer l’estimateur affecte négativement les propriétés de l’estimateur en échantillon fini. Comme solution à ce problème, nous proposons une approche par la régularisation qui consiste à utiliser une inverse généralisée de la matrice de covariance au lieu de son inverse classique. Trois techniques de régularisation sont utilisées : celle des composantes principales, celle de Tikhonov qui est basée sur le Ridge régression (aussi appelée Bayesian shrinkage) et enfin celle de Landweber Fridman qui est une méthode itérative. Toutes ces techniques introduisent un paramètre de régularisation qui est similaire au paramètre de lissage dans les régressions non paramétriques. Les propriétés en echantillon fini de l’estimateur régularisé dépend de ce paramètre qui doit être sélectionné parmis plusieurs valeurs potentielles. Dans le premier chapitre (co-écrit avec Marine Carrasco), nous proposons l’estimateur GMM régularisé du modèle de panel dynamique. Sous l’hypothèse que le nombre d’individus et de périodes du panel tendent vers l’infini, nous montrons que nos estimateurs sont convergents and assymtotiquement normaux. Nous dérivons une méthode empirique de sélection du paramètrede régularisation basée sur une expansion de second ordre du l’erreur quadratique moyenne et nous démontrons l’optimalité de cette procédure de sélection. Les simulations montrent que la régularisation améliore les propriétés de l ’estimateur GMM classique. Comme application empirique, nous avons analysé l’effet du développement financier sur la croissance économique. Dans le deuxième chapitre (co-écrit avec Marine Carrasco), nous nous intéressons à l’estimateur LIML régularisé du modèle de données de panel dynamique. L’estimateur LIML est connu pour avoir de meilleures propriétés en échantillon fini que l’estimateur GMM mais son utilisation devient problématique lorsque la dimension temporelle du panel devient large. Nous dérivons les propriétes assymtotiques de l’estimateur LIML régularisé sous l’hypothèse que le nombre d’individus et de périodes du panel tendent vers l’infini. Une procédure empirique de sélection du paramètre de régularisation est aussi proposée. Les bonnes performances de l’estimateur régularisé par rapport au LIML classique (non régularisé), au GMM classique ainsi que le GMM régularisé sont confirmées par des simulations. Dans le dernier chapitre, je considère l’estimation des élasticités d’offre de travail des hommes canadiens. L’hétérogéneité inobservée ainsi que les erreurs de mesures sur les salaires et les revenus sont connues pour engendrer de l’endogéneité quand on estime les modèles d’offre de travail. Une solution fréquente à ce problème d’endogéneité consiste à régrouper les données sur la base des carastéristiques observables et d’ éffectuer les moindres carrées pondérées sur les moyennes des goupes. Il a été démontré que cet estimateur est équivalent à l’estimateur des variables instrumentales sur les données individuelles avec les indicatrices de groupe comme instruments. Donc, en présence d’un grand nombre de groupe, cet estimateur souffre de biais en échantillon fini similaire à celui de l’estimateur des variables instrumentales quand le nombre d’instruments est élevé. Profitant de cette correspondance entre l’estimateur sur les données groupées et l’estimateur des variables instrumentales sur les données individuelles, nous proposons une approche régularisée à l’estimation du modèle. Cette approche conduit à des élasticités substantiellement différentes de ceux qu’on obtient en utilisant l’estimateur sur données groupées. / This thesis is organized in three chapters. The first two chapters propose a regularization approach to the estimation of two estimators of the dynamic panel data model : the Generalized Method of Moment (GMM) estimator and the Limited Information Maximum Likelihood (LIML) estimator. The last chapter of the thesis is an application of regularization to the estimation of labor supply elasticities using pseudo panel data models. In a dynamic panel data model, the number of moment conditions increases rapidly with the time dimension, resulting in a large dimensional covariance matrix of the instruments. Inverting this large dimensional matrix to compute the estimator leads to poor finite sample properties. To address this issue, we propose a regularization approach to the estimation of such models where a generalized inverse of the covariance matrix of the intruments is used instead of its usual inverse. Three regularization schemes are used : Principal components, Tikhonov which is based on Ridge regression (also called Bayesian shrinkage) and finally Landweber Fridman which is an iterative method. All these methods involve a regularization parameter which is similar to the smoothing parameter in nonparametric regressions. The finite sample properties of the regularized estimator depends on this parameter which needs to be selected between many potential values. In the first chapter (co-authored with Marine Carrasco), we propose the regularized GMM estimator of the dynamic panel data models. Under double asymptotics, we show that our regularized estimators are consistent and asymptotically normal provided that the regularization parameter goes to zero slower than the sample size goes to infinity. We derive a data driven selection of the regularization parameter based on an approximation of the higher-order Mean Square Error and show its optimality. The simulations confirm that regularization improves the properties of the usual GMM estimator. As empirical application, we investigate the effect of financial development on economic growth. In the second chapter (co-authored with Marine Carrasco), we propose the regularized LIML estimator of the dynamic panel data model. The LIML estimator is known to have better small sample properties than the GMM estimator but its implementation becomes problematic when the time dimension of the panel becomes large. We derive the asymptotic properties of the regularized LIML under double asymptotics. A data-driven procedure to select the parameter of regularization is proposed. The good performances of the regularized LIML estimator over the usual (not regularized) LIML estimator, the usual GMM estimator and the regularized GMM estimator are confirmed by the simulations. In the last chapter, I consider the estimation of the labor supply elasticities of Canadian men through a regularization approach. Unobserved heterogeneity and measurement errors on wage and income variables are known to cause endogeneity issues in the estimation of labor supply models. A popular solution to the endogeneity issue is to group data in categories based on observable characteristics and compute the weighted least squares at the group level. This grouping estimator has been proved to be equivalent to instrumental variables (IV) estimator on the individual level data using group dummies as intruments. Hence, in presence of large number of groups, the grouping estimator exhibites a small bias similar to the one of the IV estimator in presence of many instruments. I take advantage of the correspondance between grouping estimators and the IV estimator to propose a regularization approach to the estimation of the model. Using this approach leads to wage elasticities that are substantially different from those obtained through grouping estimators.