This thesis provides a thorough literature review of the newly founded theory of compressed sensing (CS), developed by Cand`es and his collaborators. The majority of the documented developments remain in the treatment of perfectly sparse signals in the finite dimensional setting. This was extended to the treatment of nearly sparse (compressible) signals in infinite-dimensions by Adcock and Hansen. A novel approach in analyzing the performance of CS, in the finite-dimensional setting, was developed by Cohen, Dahmen and DeVore where they study the effectiveness of CS. This is carried by comparing it to the well established theory of best k-term approximation, i.e in terms of how well CS recovers non-sparse vectors which can be well approximated by sparse vectors. The contribution of this thesis extends DeVore and his collaborators instance optimality results for CS to infinite dimensions by following a similar construction carried by Adcock and Hansen. This will be made by appealing to the truncation techniques devised by Adcock and Hansen in their development of the generalized sampling theory, and by appealing to an intermediate result established by Candès and Plan regarding the restricted isometry property (RIP). / Cette thèse présente une minutieuse revue de la littérature portant sur l’acquisition comprimée (CS), une théorie récemment développée par Candès et ses collaborateurs. La majorité des travaux qui en découlent se focalise sur les signaux parfaitement parcimonieux en un nombre fini de dimensions. Ces résultats ont été étendus au cas des signaux (compressibles) quasi-parcimonieux dans les espaces de dimension infinie par Adcock et Hansen. Une nouvelle approche permettant d'analyser la performance de la CS en un nombre de dimension finie a été proposée par Cohen, Dahmen et DeVore. Celle-ci étudie l'efficacité de la CS en comparant cette méthode à la très reconnue théorie des approximations par les k meilleurs termes; c'est-à-dire en étudiant la capacité de la CS à recouvrer des vecteurs non-parcimonieux pouvant eux-mêmes être approximés par des vecteurs parcimonieux. La contribution de cette thèse étend les résultats de DeVore et de ses collaborateurs sur l'optimalité exemplaire de la CS au cas des espaces de dimension infinie, en suivant une construction similaire à celle employée par Adcock et Hansen. À cette fin, les techniques de troncation décrites par Adcock et Hansen dans leur développement de la théorie de l'échantillonage général seront utilisées, tout comme un résultat intermédiaire établi par Cand`es et Plan portant sur la Propriété Isométrique Restreinte (RIP).

The main result of this thesis is the proof of a Kolyvagin-like result for Q-curves defined over Q=(square root N) of perfect square conductor (including trivial conductor) over that field. Such a setting lies beyond the scope of the general results of Zhang [Zh1] because of the absence of a Shimura curve parameterization for E. This thesis also describes an explicit construction of Heegner points on E in a setting which so far has not yet studied in the literature and provides numerical examples. In turn, these computations yield numerical evidence for a conjectural connection, which we propose in this thesis, between the Heegner points we construct and the ATR points obtained by Darmon-Logan in [DL].

In this thesis we study two different problems related to eigenvalue error bounds. Inthe first part of our thesis, we examine a conjecture of Knyazev and Argentati [SiamJ. Matrix Anal. Appl., 29 (2006), pp. 15–32 ] bounding the difference between Ritzvalues of a Hermitian matrix A for two subspaces, one of which is A-invariant. Weprovide a proof for a slightly weaker version of the conjecture, and discuss the recentlypublished full proof. Moreover we give implications of the now proven bound andexamine how it compares to a classical bound in the same context. In the second partof our thesis, we derive some properties of complex Hessenberg matrices and considerthe relevant normal matrix cases of these to re-examine the lengths of the Ritz vectorsin the rounding error analysis of the Lanczos process for tridiagonalizing certainnormal matrices. This question has already been studied for the real symmetric case,but part of that answer has never been published in scientific journals, and in that casewe give new theory. For the more general normal matrix cases we develop applicable theory including some new tight bounds. / Dans cette thèse, nous étudions deux problèmes différents liés aux bornes d'erreur devaleurs propres. Dans la première partie de notre thèse, nous examinons une conjecturede Knyazev et Argentati [Siam J. Matrix Anal. Appl., 29 (2006), pp. 15 – 32 ]bornant la différence entre les valeurs Ritz d'une matrice hermitienne A correspondantà deux sous-espaces, dont l'un est A-invariant. Nous obtenons une preuve pourune version légèrement plus faible de la conjecture, et discutons la preuve complètepubliée récemment. De plus, nous dérivons certaines implications de la borne, maintenantprouvée, et la comparons à une borne classique dans le même contexte. Dansla deuxième partie de notre thèse, nous dérivons certaines propriétés des matricesHessenberg complexes et examinons les cas appropriés normaux de celles-ci afin deréexaminer les longueurs des vecteurs Ritz dans l'analyse d'erreur du processus deLanczos de tridiagonalization de certaines matrices normales. Cette question a déjàété étudiée pour le cas symétrique réel, mais une partie de l'analyse n'a jamais étépubliée dans une revue scientifique; dans ce cas, nous présentons une nouvelle théorie.Pour le cas plus général de matrices normales, nous développons une théorie applicable,avec de nouvelles bornes serrées.

"Small worlds" are large networks in which any given node has only a few connections to other nodes, but possessing the property that all pairs of nodes are connected by a short path, typically logarithmic in the number of nodes. Small-world models are widely used in the physics literature for modeling various "real-world" networks, such as World Wide Web, power grid and neural network. When the network is too big to model completely, which is often the case for "real-world" network, we need other approaches which yield information about its typical or approximate structure. One such approach is to use random walks for sampling a uniform element from a large state space; to prove that such a technique works for a given network, a bound on the mixing time is required. However, little detailed information is known about the behavior of random walks on small-world models, though many predictions can be found in the physics literature. We survey the range of small-world models, existing information about them, introduce Markov chains, mixing times and a variety of techniques for bounding mixing times. Finally, the principal contribution of this thesis is to show that for a famous small-world random graph model known as the Newman--Watts small world, the mixing time is of order $\log^2 n$. This confirms a prediction of Richard Durrett, whoproved a lower bound of order $\log^2 n$ and an upper bound of order $\log^3 n$. / "De petits mondes" sont de larges réseaux au sein desquels chaque noeud donné n'a qu'un nombre limité de connexions à d'autres noeuds, mais ayant la propriété selon laquelle chaque paire de noeuds est connectée par un court parcours, typiquement de longueur logarithmique par rapport au nombre de noeuds du réseau. Les modèles de "petits mondes" sont couramment utilisés dans la littérature de physique pour modéliser divers réseaux de "mondes réels" tels que le réseau internet, le réseau électrique ainsi que les réseaux neuronaux. Lorsque le réseau est trop complexe pour être modélisé complètement, ce qui est souvent le cas des réseaux de "mondes réels", il nous faut d'autres approches qui nous renseignent sur sa structure typique ou approximative. Une telle approche consiste à utiliser la marche aléatoire pour échantillonner un élément uniforme d'un espace plus vaste. Afin de démontrer qu'une telle méthode convient pour un réseau donné, un seuil sur le temps de mélange est nécessaire. Toutefois, peu de détails sont connus quant ou comportement des marches aléatoires dans les modèles des "petits mondes" alors que de nombreuses prévisions peuvent être trouvées dans la littérature de physique. Nous citons une multitude de modèles de "petits mondes", les informations disponibles à leur égard, introduisons les chaines de Markov, temps de mélange et une variété de techniques pour les bornes des temps de mélange. Enfin, la principale contribution de cette thèse est de montrer qu'un modèle connu de graphe de "petit monde", connu sous le nom de Newman-Watts, le temps de mélange est de l'ordre de $\log^2 n$. Ceci confirme une prévision de Richard Durrett, qui a prouvé une borne inférieure de l'ordre de $\log^2 n$ et une borne supérieure de l'ordre de $\log^3 n$.

The optimized Schwarz methods were recently introduced to enhance the convergence of the classical Schwarz iteration, by replacing the Dirichlet transmission conditions with different conditions obtained through an optimization of the convergence rate. This is formulated as a min-max problem. These new methods are well-studied for elliptic second order symmetric equations. The purpose of this work is to compute optimized Robin transmission conditions for the advection-diffusion equation in two dimensions, by finding the solution of the min-max problem. The asymptotic expansion, for small mesh size h, of the resulting convergence rate is found: it shows a weak dependence on h, if the overlap is 0(h) or no overlap is used. Numerical experiments illustrate the improved convergence of these optimized methods compared to other Schwarz methods, and also justify the continuous Fourier analysis performed on a simple model problem only. The theoretical asymptotic performance is also verified numerically.

We establish a criterion on potential energy functions which, when satisfied, asserts the existence of an infinite number of periodic orbits in a dynamical system defined by two particles moving on the two-dimensional (or “flat”) torus. The original system is reduced to that of a single point-mass moving about the torus, for which we find a continuum of tra jectories satisfying a particular symmetry relation. Using a system of Poincar´e maps, we obtain addition information about a particular subset of these tra jectories in order to describe their behaviour in a linear portion of the space. Finally, we show under certain additional assumptions that, for any sufficiently large two-dimensional torus, a countably infinite subset of these tra jectories are periodic. / On établisse un critère sur les fonctions d’énergie potentielle qui, quand satisfait, affirme l’existence d’un nombre infini d’orbites d’un système dynamique de deux particules en se déplaçant autour du tore de deux dimensions. On réduit le système d’origine au système d’un point de masse qui se déplace autour du tore, duquel on trouve un continuum de tra jectoires qui satisfait à un rapport particulier de symétrie. En utilisant un système de cartes de Poincaré, on apprend davantage d’un sous-ensemble particulier de ses trajectoires pour décrire leur comportement dans une partie linéaire de l’espace. Enfin, on démontre, selon certaines hypothèses, que pour n’importe quel tore assez grand de deux dimensions, un sous-ensemble infini dénombrable est périodique.

The central weight of this thesis lies in the study of the moduli space of principal bundles over a compact Riemann surface, as well as the closely related moduli spaces of Higgs bundles and local systems. Hecke modifications are used to parametrize the moduli space of principal bundles in certain cases; while extant in the literature, an attempt has been made here to systematize the exposition on Hecke modifications. One novel aspect of the thesis is the use of the "wonderful" or De Concini--Procesi compactification of a semisimple complex algebraic group of adjoint type to develop the deformation theory necessary for the parametrization. A few new facts about these compactifications are proved as were necessary for the deformation theory. The later chapters review the symplectic geometry of the moduli spaces of Higgs bundles and local systems as discovered by N.J. Hitchin and further developed by I. Biswas and S. Ramanan, F. Bottacin, and E. Markman, as well as the theory of isomonodromic deformation, which goes back to the Riemann--Hilbert problem. Finally, using the parametrizations for moduli of principal bundles obtained, we prove a result of I. Krichever, generalized by J. Hurtubise, in the principal bundle case, relating some of the Hitchin hamiltonians to differences in isomonodromic flows. / Le sujet principal de cette thèse est l'étude de l'espace de modules des fibrés principaux sur une surface de Riemann compacte, et aussi des espaces de modules liés des fibrés de Higgs et des systèmes locaux. Les modifications de Hecke sont utilisées pour paramétrer l'espace de modules des fibrés principaux dans quelques instances; bien qu'elle existe dans la littérature, on a tenté de systématiser l'exposition sur des modifications de Hecke. Un aspect nouveau de cette thèse est l'usage de la compactification De Concini--Procesi d'un groupe algébraique complexe semi-simple dans la théorie des déformations nécessaire pour la paramétrisation. On a prouvé quelques nouveaux énoncés sur ces compactifications, nécessaires pour la théorie des déformations. Les derniers chapitres donnent un compte rendu de la géométrie symplectique des espaces de modules de fibrés de Higgs et des systèmes locaux découverte par N.J. Hitchin et développé plus tard par I. Biswas et S. Ramanan, F. Bottacin, et E. Markman, et aussi de la déformation isomonodromique, ce qui a des racines dans le problème de Riemann--Hilbert. Finalement, en se servant des paramétrisations pour des modules des fibrés principaux obtenues auparavant, on prouve un résultat de I. Krichever, généralisé par J. Hurtubise, dans le cas des fibrés principaux, qui donne une relation entre quelques uns des hamiltoniens de Hitchin et les différences dans les flots isomonodromiques.

The relevance of the Einstein constraint equations in physics is first presented. They arise in the initial-value formulation of general relativity, and must be satisfied by the metric and the extrinsic curvature of a Cauchy surface. Propagating the resulting tensor fields with the evolution equations is then equivalent to solving Einstein's field equation. The constraint equations consist of a system of two coupled nonlinear second-order PDEs. Well-posedness of the system is addressed, following the work of Y. Choquet-Bruhat. Some brief comments about global solutions are made.The conformal method is introduced. Using this approach, along with York splitting, the constraint equations now consist of a semilinear elliptic equation and a linear elliptic system that have to be solved for the conformal factor and a vector field.The main part of the thesis addresses the questions of existence and uniqueness of solutions to the Einstein constraint equations on three-dimensional compact Cauchy surfaces without boundary. The Yamabe classification turns out to be a key tool, and is presented. Then follows a thorough literature review of the results in the cases where the mean curvature, which is part of the prescribed data, is constant or near-constant. Recent articles on the case where the mean curvature is far-from-constant are discussed qualitatively. We then turn to a specific toy-model investigated by D.Maxwell where a family of three-parameters is used to consider different regimes on a Yamabe-null manifold. A similar approach is then used to explicitly work out some existence and uniqueness results on a Yamabe-positive manifold. / Tout d'abord, le rôle des équations de contraintes d'Einstein en physique est présenté. Ces équations font partie de la formulation du problème de Cauchy de la relativité générale, et doivent être satisfaites par la métrique, ainsi que par la courbure extrinsèque moyenne d'une surface de Cauchy. Déterminer la propagation de ces champs tensoriels par les équations d'évolution équivaut à la résolution de l'équation de champ d'Einstein. Les équations de contraintes d'Einstein consistent en un système de deux EDP couplées non-linéaires de deuxième ordre. Le travail d'Y. Choquet-Bruhat démontrant que le problème est bien posé, est résumé. S'ensuivent quelques brefs commentaires concernants les solutions globales. La méthode conforme est exposée. L'utilisation de cette technique combinée à la décomposition de York tranforme les équations de contrainte en une équation semi-linéaire elliptique et un système linéaire elliptique, ayant pour inconnues le facteur conforme et un champ vectoriel.L'essentiel de la présente thèse se concentre sur les questions d'existence et d'unicité des solutions des équations de contraintes d'Einstein sur les variétés compactes tridimensionelles sans frontière. À cet effet, la classification de Yamabe est un outil important. Une revue de la littérature est alors détaillée dans les cas où la courbure moyenne, qui est une donnée prescrite, est constante, ou 'proche-de-constante'. Puis vient une présentation qualitative d'articles récents traitant du cas où la courbure moyenne est 'loin-de-constante'. On s'attarde ensuite sur un cas spécifique étudié par D.Maxwell, dans lequel une famille de trois paramètres est utilisée pour passer d'un régime à l'autre sur une variété Yamabe-nulle. Une approche similaire est ensuite utilisée pour obtenir des résultats d'existence et d'unicité explicites sur une variété Yamabe-positive.

In this thesis we expose a p-adic analogue of a classical result of Shimura on the algebraicity of CM values of modular forms and certain of their nonholomorphic derivatives. More specifically, we define an analogue of the Shimura-Maass differential operator for rigid analytic modular forms on the Cerednik-Drinfeld p-adicupper half plane. This definition leads us to define the space of nearly rigid an-alytic modular forms, which is a p-adic analogue of the space of complex valuednearly holomorphic modular forms. Our main theorem is a statement about the algebraicity of values of nearly rigid analytic modular forms at CM points in thep-adic upper half plane. / Nous démontrons un variante p-adique d'un résultat classique de Shimura sur l'algébricité des valeurs des formes modulaires et de certaines de leurs dérives non-holomorphes aux points CM. Plus précisément, nous définissons un analogue rigide analytique de l'opérateur différentiel de Shimura-Maass pour les formes modulaires rigide analytiques sur le demi-plan p-adique de Cerednik-Drinfeld. Cette définition nous conduit a définir l'espace des formes modulaires presque rigide analytiques, qui correspond dans notre analogie a l'espace des formes modulaires presque holomorphes. Notre résultat principal est un énoncé d'algébricité des valeurs des formes modulaires presque rigide analytiques en des points CM dansle demi-plan p-adique de Cerednik-Drinfeld.

This thesis concerns tree decompositions. Trees are one of the simplest and most well understood class of graphs. A tree decomposition of a graph improves our understanding of the graph in a similar way. For example, as a consequence of Robertson and Seymour's groundbreaking work in the theory of graph minors, there are linear time algorithms for NP-hard problem on graphs that admit a tree decomposition of a certain type. We classify existing tree decompositions and examine what makes a tree decomposition unique.The first result of this thesis is a linear time algorithm for building a tree decomposition for the class of graphs that exclude K5 as a minor. The second result is a significant modification to this algorithm which results in a linear time algorithm to construct the tree decomposition for graphs which exclude a special set of paths. These are vertex disjoint paths between two pairs of input vertices (s_1, t_1), (s_2, t_2), one from s_1 to t_1 and the other from s_2 to t_2.We then use these tree decompositions to improve the running time of existing algorithms and extend the allowed input of other algorithms from planar graphs to graphs that exclude K_5 as a minor. / Cette thèse traite de décompositions arborescentes. Les arbres font partie des classes de graphes les mieux comprises. La décomposition arborescente d'un graphe améliore notre compréhension de ce dernier. Par exemple, grâce aux travaux de Robertson et Seymour sur les mineurs d'un graphe, nous savons qu'il existe, pour des problèmes qui sont en général NP-difficiles, un algorithme linéaire pour les graphes admettant une certaine décomposition arborescente. Nous classons les décompositions arborescentes connues et déterminons les propiétés qui rendent cette décomposition unique.Comme premier résultat, nous donnons un algorithme linéaire pour construire une décomposition arborescente d'un graphe sans mineur du graphe complet K_5. Notre deuxième resultat repose sur une modification de cet algorithme afin d'obtenir un autre algorithme linéaire. Ce dernier permet la construction d'une décomposition arborescente d'un graphe qui ne contient pas deux chemins à sommets disjoints entre deux paires de sommets données (s_1, t_1) et (s_2, t_2).Nous utilisons ces deux décompositions pour améliorer le temps de calcul des algorithmes existants et modifions des algorithmes pour graphes planaires pour leur permettre de prendre comme donnée des graphes sans mineur K_5.