To see the other types of publications on this topic, follow the link: Polynomial calculus.
Dissertations / Theses on the topic 'Polynomial calculus'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Polynomial calculus.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Mikša, Mladen. "On Complexity Measures in Polynomial Calculus." Doctoral thesis, KTH, Teoretisk datalogi, TCS, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-197278.
Full textAbstract:
Proof complexity is the study of different resources that a proof needs in different proof systems for propositional logic. This line of inquiry relates to the fundamental questions in theoretical computer science, as lower bounds on proof size for an arbitrary proof system would separate P from NP. We study two simple proof systems: resolution and polynomial calculus. In resolution we reason using clauses, while in polynomial calculus we use polynomials. We study three measures of complexity of proofs: size, space, and width/degree. Size is the number of clauses or monomials that appear in a resolution or polynomial calculus proof, respectively. Space is the maximum number of clauses/monomials we need to keep at each time step of the proof. Width/degree is the size of the largest clause/monomial in a proof. Width is a lower bound for space in resolution. The original proof of this claim used finite model theory. In this thesis we give a different, more direct proof of the space-width relation. We can ask whether a similar relation holds between space and degree in polynomial calculus. We make some progress on this front by showing that when a formula F requires resolution width w then the XORified version of F requires polynomial calculus space Ω(w). We also show that space lower bounds do not imply degree lower bounds in polynomial calculus. Width/degree and size are also related, as strong lower bounds for width/degree imply strong lower bounds for size. Currently, proving width lower bounds has a well-developed machinery behind it. However, the degree measure is much less well-understood. We provide a unified framework for almost all previous degree lower bounds. We also prove some new degree and size lower bounds. In addition, we explore the relation between theory and practice by running experiments on some current state-of-the-art SAT solvers.QC 20161206
Understanding the Hardness of Theorem Proving
2
Curzi, Gianluca. "Non-laziness in implicit computational complexity and probabilistic λ-calculus." Thesis, Université de Paris (2019-....), 2020. http://www.theses.fr/2020UNIP7010.
Full textAbstract:
Cette thèse explore les avantages de la “non-paresse” dans la Complexité Computationnelle implicite et dans le lambda calcul probabiliste. Plus précisément, cette thèse peut être divisée en deux parties principales. Dans la première, nous étudions dans tous les sens les mécanismes d’effacement et de duplication linéaire, qui nous conduisent aux systèmes de typage LEM (Lin- early Exponential Multiplicative Type Assignment) et LAM (Linearly Additive Multiplicative Type Assignment). Le premier est capable d’exprimer des versions plus faibles des règles exponentielles de la Logique Linéaire, tandis que le second est doté de règles additifs plus faibles, appelées additifs linéaires. Ces systèmes bénéficient respectivement d’une élimination de coupure cubique et d’un résultat de normalisation linéaire. Étant donné que les additifs linéaires ne nécessitent pas d’évaluation paresseuse pour éviter l’explosion exponentielle de la normalisation (contraire- ment aux additifs standard), ils peuvent être utilisés pour obtenir une caractérisation implicite des fonctions calculables en temps polynomial probabiliste qui ne dépend pas du choix de la stratégie de réduction. Ce résultat a été réalisé dans STA, un système obtenu en dotant STA (Soft Type Assignment) d’une formulation aléatoire des additifs linéaires, qui capture aussi les classes de complexité PP et BPP. La deuxième partie de la thèse est centrée sur le lambda calcul probabiliste doté d’une sémantique opérationnelle basée sur la réduction de tête, c’est-à-dire une politique d’évaluation non paresseuse d’appel par nom. Nous prouvons que la bisimilarité probabiliste est “fully abstract” par rapport à l’équivalence observationnelle. Ce résultat témoigne le pouvoir discriminant de la non-paresse, qui permet de retrouver une correspondance parfaite entre les deux équivalences qui manquait dans le cadre paresseux. De plus, nous montrons que la similarité probabiliste est correcte mais pas complète par rapport au préordre observationnelThis thesis explores the benefits of non-laziness in both Implicit Computational Complexity and probabilistic computation. More specifically, this thesis can be divided in two main parts. In the first one, we investigate in all directions the mechanisms of linear erasure and duplication, which lead us to the type assignment systems LEM (Linearly Exponential Multiplicative Type Assignment) and LAM (Linearly Additive Multiplicative Type Assignment). The former is able to express weaker versions of the exponential rules of Linear Logic, while the latter has weaker additive rules, called linear additives. These systems enjoy, respectively, a cubic cut-elimination and a linear normalization result. Since linear additives do not require a lazy evaluation to avoid the exponential blow up in normalization (unlike the standard additives), they can be employed to obtain an implicit characterization of the functions computable in probabilistic polynomial time that does not depend on the choice of the reduction strategy. This result is achieved in STA⊕, a system that extends STA (Soft Type Assignment) with a randomized formulation of linear additives. Also, this system is able to capture the complexity classes PP and BPP. The second part of the thesis is focused on the probabilistic λ-calculus endowed with an operational semantics based on the head reduction, i.e. a non-lazy call-by-name evaluation policy. We prove that probabilistic applicative bisimilarity is fully abstract with respect to context equivalence. This result witnesses the discriminating power of non-laziness, which allows to recover a perfect match between the two equivalences that was missing in the lazy setting. Moreover, we show that probabilistic applicative similarity is sound but not complete for the context preorder
3
Araaya, Tsehaye. "The Symmetric Meixner-Pollaczek polynomials." Doctoral thesis, Uppsala University, Department of Mathematics, 2003. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-3501.
Full textAbstract:
The Symmetric Meixner-Pollaczek polynomials are considered. We denote these polynomials in this thesis by pn(λ)(x) instead of the standard notation pn(λ) (x/2, π/2), where λ > 0. The limiting case of these sequences of polynomials pn(0) (x) =limλ→0 pn(λ)(x), is obtained, and is shown to be an orthogonal sequence in the strip, S = {z ∈ ℂ : −1≤ℭ (z)≤1}.
From the point of view of Umbral Calculus, this sequence has a special property that makes it unique in the Symmetric Meixner-Pollaczek class of polynomials: it is of convolution type. A convolution type sequence of polynomials has a unique associated operator called a delta operator. Such an operator is found for pn(0) (x), and its integral representation is developed. A convolution type sequence of polynomials may have associated Sheffer sequences of polynomials. The set of associated Sheffer sequences of the sequence pn(0)(x) is obtained, and is found
to be ℙ = {{pn(λ) (x)} =0 : λ ∈ R}. The major properties of these sequences of polynomials are studied.
The polynomials {pn(λ) (x)}∞n=0, λ < 0, are not orthogonal polynomials on the real line with respect to any positive real measure for failing to satisfy Favard’s three term recurrence relation condition. For every λ ≤ 0, an associated nonstandard inner product is defined with respect to which pn(λ)(x) is orthogonal.
Finally, the connection and linearization problems for the Symmetric Meixner-Pollaczek polynomials are solved. In solving the connection problem the convolution property of the polynomials is exploited, which in turn helps to solve the general linearization problem.
4
Heinz, Sebastian. "Preservation of quasiconvexity and quasimonotonicity in polynomial approximation of variational problems." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, 2008. http://dx.doi.org/10.18452/15808.
Full textAbstract:
Die vorliegende Arbeit beschäftigt sich mit drei Klassen ausgewählter nichtlinearer Probleme, die Forschungsgegenstand der angewandten Mathematik sind. Diese Probleme behandeln die Minimierung von Integralen in der Variationsrechnung (Kapitel 3), das Lösen partieller Differentialgleichungen (Kapitel 4) und das Lösen nichtlinearer Optimierungsaufgaben (Kapitel 5). Mit deren Hilfe lassen sich unterschiedlichste Phänomene der Natur- und Ingenieurwissenschaften sowie der Ökonomie mathematisch modellieren. Als konkretes Beispiel werden mathematische Modelle der Theorie elastischer Festkörper betrachtet. Das Ziel der vorliegenden Arbeit besteht darin, ein gegebenes nichtlineares Problem durch polynomiale Probleme zu approximieren. Um dieses Ziel zu erreichen, beschäftigt sich ein großer Teil der vorliegenden Arbeit mit der polynomialen Approximation von nichtlinearen Funktionen. Den Ausgangspunkt dafür bildet der Weierstraßsche Approximationssatz. Auf der Basis dieses bekannten Satzes und eigener Sätze wird als Hauptresultat der vorliegenden Arbeit gezeigt, dass im Übergang von einer gegebenen Funktion zum approximierenden Polynom wesentliche Eigenschaften der gegebenen Funktion erhalten werden können. Die wichtigsten Eigenschaften, für die dies bisher nicht bekannt war, sind: Quasikonvexität im Sinne der Variationsrechnung, Quasimonotonie im Zusammenhang mit partiellen Differentialgleichungen sowie Quasikonvexität im Sinne der nichtlinearen Optimierung (Theoreme 3.16, 4.10 und 5.5). Schließlich wird gezeigt, dass die zu den untersuchten Klassen gehörenden nichtlinearen Probleme durch polynomiale Probleme approximiert werden können (Theoreme 3.26, 4.16 und 5.8). Die dieser Approximation zugrunde liegende Konvergenz garantiert sowohl eine Approximation im Parameterraum als auch eine Approximation im Lösungsraum. Für letztere werden die Konzepte der Gamma-Konvergenz (Epi-Konvergenz) und der G-Konvergenz verwendet.In this thesis, we are concerned with three classes of non-linear problems that appear naturally in various fields of science, engineering and economics. In order to cover many different applications, we study problems in the calculus of variation (Chapter 3), partial differential equations (Chapter 4) as well as non-linear programming problems (Chapter 5). As an example of possible applications, we consider models of non-linear elasticity theory. The aim of this thesis is to approximate a given non-linear problem by polynomial problems. In order to achieve the desired polynomial approximation of problems, a large part of this thesis is dedicated to the polynomial approximation of non-linear functions. The Weierstraß approximation theorem forms the starting point. Based on this well-known theorem, we prove theorems that eventually lead to our main result: A given non-linear function can be approximated by polynomials so that essential properties of the function are preserved. This result is new for three properties that are important in the context of the considered non-linear problems. These properties are: quasiconvexity in the sense of the calculus of variation, quasimonotonicity in the context of partial differential equations and quasiconvexity in the sense of non-linear programming (Theorems 3.16, 4.10 and 5.5). Finally, we show the following: Every non-linear problem that belongs to one of the three considered classes of problems can be approximated by polynomial problems (Theorems 3.26, 4.16 and 5.8). The underlying convergence guarantees both the approximation in the parameter space and the approximation in the solution space. In this context, we use the concepts of Gamma-convergence (epi-convergence) and of G-convergence.
5
Souvay, Arnaud. "Une approche intrinsèque des foncteurs de Weil." Thesis, Université de Lorraine, 2012. http://www.theses.fr/2012LORR0257/document.
Full textAbstract:
Nous construisons un foncteur de la catégorie des variétés sur un corps ou un anneau topologique K, de caractéristique arbitraire, dans la catégorie des variétés sur A, où A est une algèbre de Weil, c'est-à-dire une K-algèbre de la forme A = K + N, où N est un idéal nilpotent. Le foncteur correspondant, noté T^A, et appelé foncteur de Weil, peut être interprété comme un foncteur d'extension scalaire de K à A. Il est construit à l'aide des polynômes de Taylor, dont nous donnons une définition en caractéristique quelconque. Ce résultat généralise à la fois des résultats connus pour les variétés réelles ordinaires, et les résultats obtenus dans le cas des foncteurs tangents itérés et dans le cas des anneaux de jets (A = K[X]/(X^{k+1})). Nous montrons que pour toute variété M, T^A M possède une structure de fibré polynomial sur M, et nous considérons certains aspects algébriques des foncteurs de Weil, notamment ceux liés à l'action du « groupe de Galois » Aut_K(A). Nous étudions les connexions, qui sont un outil important d'analyse des fibrés, dans deux contextes différents : d'une part sur les fibrés T^A M, et d?autre part sur des fibrés généraux sur M, en suivant l'approche d'Ehresmann. Les opérateurs de courbure d'une connexion sont induits par l'action du groupe de Galois Aut_K(A) et ils forment une obstruction à l'« intégrabilité » d'une connexion K-lisse en une connexion A-lisseWe construct a functor from the category of manifolds over a general topological base field or ring K, of arbitrary characteristic, to the category of manifolds over A, where A is a so-called Weil algebra, i.e. a K-algebra of the form A = K + N, where N is a nilpotent ideal. The corresponding functor, denoted by T^A, and called a Weil functor, can be interpreted as a functor of scalar extension from K to A. It is constructed by using Taylor polynomials, which we define in arbitrary characteristic. This result generalizes simultaneously results known for ordinary, real manifolds, and results for iterated tangent functors and for jet rings (A = K[X]/(X^{k+1})). We show that for any manifold M, T^A M is a polynomial bundle over M, and we investigate some algebraic aspects of the Weil functors, in particular those related to the action of the "Galois group" Aut_K(A). We study connections, which are an important tool for the analysis of fiber bundles, in two different contexts : connections on the Weil bundles T^A M, and connections on general bundles over M, following Ehresmann's approach. The curvature operators are induced by the action of the Galois group Aut_K(A) and they form an obstruction to the "integrability" of a K-smooth connection to an A-smooth one
6
Schimanski, Stefan. "Polynomial Time Calculi." Diss., lmu, 2009. http://nbn-resolving.de/urn:nbn:de:bvb:19-99100.
Full text
7
Vinyals, Marc. "Space in Proof Complexity." Doctoral thesis, KTH, Teoretisk datalogi, TCS, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-206571.
Full textAbstract:
ropositional proof complexity is the study of the resources that are needed to prove formulas in propositional logic. In this thesis we are concerned with the size and space of proofs, and in particular with the latter. Different approaches to reasoning are captured by corresponding proof systems. The simplest and most well studied proof system is resolution, and we try to get our understanding of other proof systems closer to that of resolution. In resolution we can prove a space lower bound just by showing that any proof must have a large clause. We prove a similar relation between resolution width and polynomial calculus space that lets us derive space lower bounds, and we use it to separate degree and space. For cutting planes we show length-space trade-offs. This is, there are formulas that have a proof in small space and a proof in small length, but there is no proof that can optimize both measures at the same time. We introduce a new measure of space, cumulative space, that accounts for the space used throughout a proof rather than only its maximum. This is exploratory work, but we can also prove new results for the usual space measure. We define a new proof system that aims to capture the power of current SAT solvers, and we show a landscape of length-space trade-offs comparable to those in resolution. To prove these results we build and use tools from other areas of computational complexity. One area is pebble games, very simple computational models that are useful for modelling space. In addition to results with applications to proof complexity, we show that pebble game cost is PSPACE-hard to approximate. Another area is communication complexity, the study of the amount of communication that is needed to solve a problem when its description is shared by multiple parties. We prove a simulation theorem that relates the query complexity of a function with the communication complexity of a composed function.QC 20170509
8
Verron, Thibaut. "Régularisation du calcul de bases de Gröbner pour des systèmes avec poids et déterminantiels, et application en imagerie médicale." Thesis, Paris 6, 2016. http://www.theses.fr/2016PA066355/document.
Full textAbstract:
La résolution de systèmes polynomiaux est un problème aux multiples applications, et les bases de Gröbner sont un outil important dans ce cadre. Il est connu que de nombreux systèmes issus d'applications présentent une structure supplémentaire par rapport à des systèmes arbitraires, et que ces structures peuvent souvent être exploitées pour faciliter le calcul de bases de Gröbner.Dans cette thèse, on s'intéresse à deux exemples de telles structures, pour différentes applications. Tout d'abord, on étudie les systèmes homogènes avec poids, qui sont homogènes si on calcule le degré en affectant un poids à chaque variable. Cette structure apparaît naturellement dans de nombreuses applications, dont un problème de cryptographie (logarithme discret). On montre comment les algorithmes existants, efficaces pour les polynômes homogènes, peuvent être adaptés au cas avec poids, avec des bornes de complexité générique divisées par un facteur polynomial en le produit des poids.Par ailleurs, on étudie un problème de classification de racines réelles pour des variétés définies par des déterminants. Ce problème a une application directe en théorie du contrôle, pour l'optimisation de contraste de l'imagerie à résonance magnétique. Ce système particulier s'avère insoluble avec les stratégies générales pour la classification. On montre comment ces stratégies peuvent tirer profit de la structure déterminantielle du système, et on illustre ce procédé en apportant des réponses aux questions posées par le problème d'optimisation de contrastePolynomial system solving is a problem with numerous applications, and Gröbner bases are an important tool in this context. Previous studies have shown that systèmes arising in applications usually exhibit more structure than arbitrary systems, and that these structures can be used to make computing Gröbner bases easier.In this thesis, we consider two examples of such structures. First, we study weighted homogeneous systems, which are homogeneous if we give to each variable an arbitrary degree. This structure appears naturally in many applications, including a cryptographical problem (discrete logarithm). We show how existing algorithms, which are efficient for homogeneous systems, can be adapted to a weighted setting, and generically, we show that their complexity bounds can be divided by a factor polynomial in the product of the weights.Then we consider a real roots classification problem for varieties defined by determinants. This problem has a direct application in control theory, for contrast optimization in magnetic resonance imagery. This specific system appears to be out of reach of existing algorithms. We show how these algorithms can benefit from the determinantal structure of the system, and as an illustration, we answer the questions from the application to contrast optimization
9
Monnot, Jérôme. "Familles d'instances critiques et approximation polynomiale." Paris 9, 1998. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1998PA090028.
Full textAbstract:
S'il est facile de concevoir que le comportement d'un algorithme approché diffère suivant l'instance à traiter, quel est réellement le rôle de ces instances dans l'approximation d'un problème ? Quelles influences ont-elles sur le comportement d'un algorithme ? A quel niveau ? Pour répondre à ces questions, nous avons construit un formalisme permettant d'ordonner les instances selon le niveau d'information qu'elles procurent. Ce formalisme nous conduit à définir des familles d'instances dépendant soit d'un problème soit d'un triplet (problème, algorithme approche, mesure d'approximation). La classification en familles critiques et fortement critiques permet de comprendre, d'analyser et d'éventuellement améliorer le comportement de cet algorithme au pire des cas. Afin de construire de telles familles, nous proposons divers outils et méthodes basés sur la notion centrale de plus mauvaise instance. D'un point de vue opérationnel, concernant la mesure différentielle, nous avons spécifié certaines formes d'instances empêchant la très bonne approximabilité et caractérise les classes ptas() et fptas(). Ensuite, nous avons obtenu, grâce aux familles critiques, des résultats d'approximation positifs et négatifs sur une classe de problèmes de partitionnement définis par certaines propriétés logiques. Les problèmes de la coloration, du bin-packing, de l'ensemble dominant de Steiner en font partie. Précisons toutefois qu'une étude spécifique de ces problèmes met en évidence des différences d'approximation : la coloration appartient à apx()ptas() tandis que le bin-packing appartient à ptas()isfptas(). Enfin, par les mêmes procédés, nous obtenons de bons résultats d'approximation pour les problèmes connexes à celui de l'arbre de Steiner
10
Wailly, Olivier. "Placement optimal de capteurs sur un système à modèle polynomial." Corte, 2004. http://www.theses.fr/2005CORT3091.
Full textAbstract:
La présente thèse met en évidence une méthode novatrice dans le placement de capteurs sur un système automatisé. Cette méthode n'est applicable que sur les systèmes présentant un modèle polynomial. Cette méthode est innovante dans l'utilisation du calcul formel, et plus spécifiquement des algorithmes des bases de Groëbner. Après avoir montré comment il est possible, utile et interressant d'utiliser le calcul formel, il est développé une recherche de placement prenant en compte des critères optimums. Ainsi, des algorithmes avec critères de coût et critères de fiabilité sont élaborésThe present thesus present a novel method in sensor design on automated system. This method is only applicable on polynomial systems. This method is using symbolic calculus software. Especially, the Groënberg bases' algorithms are used. After showing the interest of this method, algoritms and programs with optimal criteria are presented. So, the criteria like cost and reliability are developed
11
Moalla, Borhane. "Approximants de Padé, polynômes orthogonaux (cas matriciel)." Rouen, 1995. http://www.theses.fr/1995ROUES052.
Full textAbstract:
Ce travail est consacré aux approximants de Padé. On commence par une amélioration du calcul des coefficients des polynômes orthogonaux par rapport à une fonctionnelle linéaire quelconque en utilisant la méthode Cestac de J. Vignes. On étend les notions d'approximants de Padé en deux points des séries formelles aux séries de fonctions. On étend également la méthode de C. Brezinski, pour l'estimation de l'erreur des approximants de Padé en un point dans le cas normal, au cas non normal et au cas des approximants de Padé en deux points. On étudie la stabilité et la convergence des formules de quadrature de Gauss pour une fonction poids polynomiale de degré inferieur ou égal à 2. Enfin, les approximants de Padé matriciels rectangulaires ayant des polynômes générateurs à coefficients matriciels carrés sont définis ; des relations de récurrence que vérifient ces polynômes sont établies. On obtient un algorithme QD matriciel ; on généralise le théorème de Shohat-Favard et on étend la procédure de Kronrod pour l'estimation de l'erreur de ces approximants.
12
Serrière, Fabrice. "Approximation polynomiale du recouvrement d'ensemble." Paris 9, 2005. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=2005PA090018.
Full textAbstract:
Cette thèse a pour objet l'approximation polynomiale du problème NP_difficile de recouvrement d'ensemble, dit set covering problem dans la littérature. Dans la première partie, nous situons le problème de recouvrement au sein du domaine de la complexité avant de relater les plus importants résultats relatifs à l'approximation classique et à l'inapproximation classique de ce dernier. Dans la seconde partie, nous travaillons sur l'approximation différentielle du problème pour des instances pondérées et non pondérées, en commençant par situer les limites de la problématique puis en obtenant des bornes inférieures et supérieures du rapport différentiel pour certains algorithmes dont le célèbre algorithme glouton. Dans la troisième partie nous étudions la problématique probabiliste relative au recouvrement non pondéré et prouvons qu'elle est équivalente à la problématique pondérée du problème pour la stratégie que nous proposons. Dans la quatrième et dernière partie, nous étudions l'approximation du recouvrement sous son angle expérimental en testant les algorithmes étudiés au cours du document et en testant de nouveaux algorithmes sur les instances de la littérature et sur des instances générées par nos soins. La première annexe est dédiée à un certain nombre d'analyses d'algorithme. La seconde propose une méthode générale d'analyse pouvant s'adapter à de nombreux problèmes. La troisième présente la globalité des résultats expérimentaux, et la dernière annexe est une question relative à l'énumération sous contrainteThis thesis deals with the polynomial approximation of the NP_Hard set covering problem. In the first part, we locate the problem of covering within the field of complexity before reporting the most significant results relating to the classical approximation and the traditional inapproximation of it. In the second part, we work on the differential approximation of the problem for weighted and unweighted cases, while starting by locating the limits of the problems then by proving lower and higher bounds for the differential ratio for certain algorithms whose well known greedy one. In the third part we study the probabilistic problems relating to unweighted set cover and prove that it is equivalent to the weighted one for the strategy which we propose. In the fourth and last part, we study the approximation of covering under its experimental angle by testing the algorithms studied during the document and by testing new algorithms on the instances of the literature and instances that we generated. The first appendix is dedicated to well known analyses of algorithm for set covering problem. The second one proposes a general method of analysis adaptable to many combinatorial problems. The third gives the experimental results studied in the forth part, and the last appendix is a question relating to the enumeration under constraint
13
Pham, Van tuan. "Applications des foncteurs strictement polynomiaux." Thesis, Sorbonne Paris Cité, 2015. http://www.theses.fr/2015USPCD016/document.
Full textAbstract:
Les travaux présentés dans cette thèse concernent l'étude des représentations et la cohomologie des foncteurs strictement polynomiaux d'une ou plusieurs variables. Ces foncteurs d'une variable ont été introduits par Friedlander-Suslin dans leur article fondamental [Eric M. Friedlander and Andrei Suslin. Cohomology of finite group schemes over a field. Invent. Math., 127(2) : 209-270, 1997]. Des variantes à plusieurs variables sont définies dans [Vincent Franjou, Eric M. Friedlander, Alexander Scorichenko, and Andrei Suslin. General linear and functor cohomology over finite fields. Ann. of Math (2), 150(2) : 663-728, 1999], [Vincent Franjou and Eric Friedlander. Cohomology of bifunctors. Proc. Lond. Math. Soc. (3), 97(2) : 514-544, 2008], [Antoine Touzé. Cohomology of classical algebraic groups from the functorial viewpoint. Adv. Math., 225(1) : 33-68, 2010]. Dans une première partie de la thèse (chapitre 2), nous étudions l'influence de la torsion de Frobenius sur les groupes d'extension dans les catégories des foncteurs strictement polynomiaux. [...]The work presented in this thesis deals with the study of representations ans cohomology of strict polynomial functors. The category P* of strict polynomial functors was introduced by Friedlander and Suslin in thei fouder article [Eric M. Friedlanderand Andrei Suslin. Cohomology of finite group schemes over a field. Invent. Math., 127(2) : 209-270, 1997]. Variants of this category, that is strict polynomial functors with several variables were introduced in [Vincent Franjou, Eric M. Friedlander, Alexander Scorichenko, and Andrei Suslin. General linear and functor cohomology over finite fields. Ann. of Math (2), 150(2) : 663-728, 1999], [Vincent Franjou and Eric Friedlander. Cohomology of bifunctors. Proc. Lond. Math. Soc. (3), 97(2) : 514-544, 2008], [Antoine Touzé. Cohomology of classical algebraic groups from the functorial viewpoint. Adv. Math., 225(1) : 33-68, 2010]. The first part of this thesis (chapter 2) studies the effect of Frobenius twist on the cohomology of strict polynomial functors. [...]
14
Lin, Zhicong. "Eulerian calculus arising from permutation statistics." Phd thesis, Université Claude Bernard - Lyon I, 2014. http://tel.archives-ouvertes.fr/tel-00996105.
Full textAbstract:
In 2010 Chung-Graham-Knuth proved an interesting symmetric identity for the Eulerian numbers and asked for a q-analog version. Using the q-Eulerian polynomials introduced by Shareshian-Wachs we find such a q-identity. Moreover, we provide a bijective proof that we further generalize to prove other symmetric qidentities using a combinatorial model due to Foata-Han. Meanwhile, Hyatt has introduced the colored Eulerian quasisymmetric functions to study the joint distribution of the excedance number and major index on colored permutations. Using the Decrease Value Theorem of Foata-Han we give a new proof of his main generating function formula for the colored Eulerian quasisymmetric functions. Furthermore, certain symmetric q-Eulerian identities are generalized and expressed as identities involving the colored Eulerian quasisymmetric functions. Next, generalizing the recent works of Savage-Visontai and Beck-Braun we investigate some q-descent polynomials of general signed multipermutations. The factorial and multivariate generating functions for these q-descent polynomials are obtained and the real rootedness results of some of these polynomials are given. Finally, we study the diagonal generating function of the Jacobi-Stirling numbers of the second kind by generalizing the analogous results for the Stirling and Legendre-Stirling numbers of the second kind. It turns out that the generating function is a rational function, whose numerator is a polynomial with nonnegative integral coefficients. By applying Stanley's theory of P-partitions we find combinatorial interpretations of those coefficients
15
Watel, Dimitri. "Approximation de l'arborescence de Steiner." Thesis, Versailles-St Quentin en Yvelines, 2014. http://www.theses.fr/2014VERS0025/document.
Full textAbstract:
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 contraintThe 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
16
Dreossi, Tommaso. "Calcul d'atteignabilité et synthèse de paramètres pour systèmes dynamiques polynomiaux." Thesis, Université Grenoble Alpes (ComUE), 2016. http://www.theses.fr/2016GREAM096.
Full textAbstract:
Les systèmes dynamiques sont des importants modèles mathématiques utilisés pour décrire l'évolution temporelle des systèmes.Souvent, les systèmes dynamiques sont équipées avec des paramètres qui permettent les modèles de mieux saisir les caractéristiques des phénomènes abstraits. Une question importante autour des systèmes dynamiques est de déterminer formellement si un modèle (sollicité par ses paramètres) se comporte bien.Dans cette thèse, nous traitons deux questions principales concernant les systèmes dynamiques polynomiaux en temps discret:1) problème de calcul de la d'atteignabilité, i.e., étant donné un ensemble de conditions initiales et un ensemble deparamètres, calculer l'ensemble des états atteignable par le système dans un horizon de temps borné;2) le problème de la synthèse de paramètre, i.e., étant donné un ensemble de conditions initiales,un ensemble de paramètres, et une spécification, trouver l'ensemble de paramètres le plus grandtels que tous les comportements du système fixes de l'ensemble de conditions initiales satisfont la spécification.Le problème de calcul d'atteignabilité pour les systèmes dynamiques non linéaires est bien connu pour être non triviale.Des difficultés surgissent dans le traitement et la représentation des ensembles générés par les transformations non linéaires.Dans cette thèse, nous adoptons une technique courante qui consistede rapprocher les ensembles atteignable avec des ensembles complexes qui sont faciles à manipuler.Le défi est de déterminer précis sur-approximations.Nous proposons des méthodes pour rapprocher finement les images des ensembles utilisant des boîtes,parallelotopes, et une nouvelle structure appelé parallelotope bundle (ce sont des collections de parallelotopes dont les intersections représentent symboliquement polytopes). Ces techniques d'approximation sont les étapes de base de notre algorithme d'accessibilité.La synthèse des paramètres vise à déterminer les valeursdes paramètres tels que le système se comporte comme prévu. Cette fonctionnalité peut êtreutilisé, par exemple, pour régler un modèle qu'il imite la modéliséphénomène avec un niveau suffisant de précision. Les contributions de cettethèse sur le problème de synthèse de paramètres sont de deux ordres. Premièrement,nous définissons une nouvelle sémantique pour le signal logique temporelle (STL) que nous permetde formaliser une spécification et de raisonner sur des ensembles de paramètres et des flux de comportements.Deuxièmement, nous définissons un algorithme pour calculer la sémantique de synthèsed'une formule à l'encontre d'un système dynamique à temps discret. Le résultat de l'algorithmeconstitue une solution conservatrice du problème de la synthèse de paramètre.Les méthodes développées exploitent et améliorent le calcul des coefficients de Bernstein.Les techniques définies dans cette thèse ont été mises en œuvreun tool appelé Sapo. L'efficacité de notre méthode est validéepar l'application de notre tool pour plusieurs systèmes dynamiques polynomiauxDynamical systems are important mathematical models used to describe the temporal evolution of systems.Often dynamical systems are equipped with parameters that allow the models to better capture the characteristicsof the abstracted phenomena. An important question around dynamical systems isto formally determine whether a model (biased by its parameters) behaves well.In this thesis we deal with two main questions concerning discrete-time polynomial dynamical systems:1) the reachability computation problem, i.e, given a set of initial conditions and a set ofparameters, compute the set of states reachable by the system in a bounded time horizon;2) the parameter synthesis problem, i.e., given a set of initial conditions,a set of parameters, and a specification, find the largestset of parameters such that all the behaviors of the system staring from the set ofinitial conditions satisfy the specification.The reachability computation problem for nonlinear dynamical systems is well known for being nontrivial.Difficulties arise in handling and representing sets generated by nonlinear transformations.In this thesis we adopt a common technique that consistsin over-approximating the complex reachable sets with sets that are easy to manipulate.The challenge is to determine accurate over-approximations.We propose methods to finely over-approximate the images of sets using boxes,parallelotopes, and a new data structure called parallelotope bundles (that are collections of parallelotopeswhose intersections symbolically represent polytopes). These approximation techniquesare the basic steps of our reachability algorithm.The synthesis of parameters aims at determining the valuesof the parameters such that the system behaves as expected. This feature can beused, for instance, to tune a model so that it imitates the modeledphenomenon with a sufficient level of precision. The contributions of thisthesis concerning the parameter synthesis problem are twofold. Firstly,we define a new semantics for the Signal Temporal Logic (STL) that allows oneto formalize a specification and reason on sets of parameters and flows of behaviors.Secondly, we define an algorithm to compute the synthesis semanticsof a formula against a discrete-time dynamical system. The result of the algorithmconstitutes a conservative solution of the parameter synthesis problem.The developed methods for both reachability computation and parameter synthesisexploit and improve Bernstein coefficients computation.The techniques defined in this thesis have been implemented ina tool called Sapo. The effectiveness of our methods is validatedby the application of our tool to several polynomial dynamical systems
17
Escoffier, Bruno. "Approximation polynomiale de problèmes d’optimisation : aspects structurels et opérationnels." Paris 9, 2005. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=2005PA090065.
Full textAbstract:
Cette thèse s'inscrit dans le domaine de l'étude des problèmes de NPO (problèmes d'optimisation dont la version décision est dans NP), et plus particulièrement dans la théorie de l'approximation polynomiale de ces problèmes. Il s'agit d'étudier la possibilité de fournir efficacement des solutions réalisables ayant une certaine qualité, qualité que nous mesurons tantôt par le rapport standard, tantôt par le rapport différentiel. Deux aspects principaux se dégagent dans notre travail : - La structure des classes d'approximation : il s'agit de structurer les classes classiques par l'introduction de réductions qui préservent certains types d'approximation et qui induisent des notions de complétude. - L'approximation polynomiale de problèmes de NPO : nous avons étudié les problèmes de la coloration pondérée, de la coloration probabiliste et de la couverture d'ensemble quadratique selon le rapport standard, ainsi que des problèmes de satisfiabilité selon le rapport différentielThis thesis deals with the study of NPO-problems (optimization problems the decision version of which is in NP), and more precisely the theory of worst case polynomial approximation. In this problematic, we aim at determining how it is possible to produce efficiently a feasible solution achieving a certain quality, quality measured either by the standard ratio or by the differential ratio. Our work can be divided into two parts : - The structure of approximation classes, structure which emerges from the introduction of approximation preserving reductions which induce notions of completeness. - Polynomial approximation of some NPO problems: we studied approximation properties of the weighted coloring problem, the probabilistic coloring problem and the quadratic set covering problem using the standard ratio, and satisfiability problems using the differential ratio
18
Blanc, Monique. "Modèle polynomial contraint discret par couche pour le calcul thermique et thermoélastique des multicouches épais." Phd thesis, Paris, ENSAM, 2005. http://tel.archives-ouvertes.fr/tel-00012005.
Full textAbstract:
Nous présentons dans ce travail un modèle numérique performant pour le calcul de la température, du flux thermique, des déplacements et des contraintes dans un multicouche épais. Ce modèle est basé sur une approche "couche discrète " et utilise des fonctions polynomiales de degré 2 dans l'épaisseur de chaque couche. La spécificité du modèle proposé est qu'il assure la continuité, tant pour tant pour la composante normale du flux thermique que pour le vecteur contrainte suivant la normale aux interfaces. Ce modèle autorise la présence de résistance de contact aux interfaces ; il permet de diminuer le nombre de paramètres du modèle tout en assurant une meilleure approximation. Pour valider ce modèle, nous avons été amené à expliciter les solutions analytiques exactes, pour certaines géométries. Nous avons également comparé ce modèle à des modèles couramment utilisés par les codes éléments finis spécifiques aux multicouches et nous avons montré qu'il apportait une amélioration certaine sur la précision des résultats, pour des problèmes de conduction thermique, d'élasticité et de thermoélasticité.
19
Joldes, Mioara Maria. "Approximations polynomiales rigoureuses et applications." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2011. http://tel.archives-ouvertes.fr/tel-00657843.
Full textAbstract:
Quand on veut évaluer ou manipuler une fonction mathématique f, il est fréquent de la remplacer par une approximation polynomiale p. On le fait, par exemple, pour implanter des fonctions élémentaires en machine, pour la quadrature ou la résolution d'équations différentielles ordinaires (ODE). De nombreuses méthodes numériques existent pour l'ensemble de ces questions et nous nous proposons de les aborder dans le cadre du calcul rigoureux, au sein duquel on exige des garanties sur la précision des résultats, tant pour l'erreur de méthode que l'erreur d'arrondi.Une approximation polynomiale rigoureuse (RPA) pour une fonction f définie sur un intervalle [a,b], est un couple (P, Delta) formé par un polynôme P et un intervalle Delta, tel que f(x)-P(x) appartienne à Delta pour tout x dans [a,b].Dans ce travail, nous analysons et introduisons plusieurs procédés de calcul de RPAs dans le cas de fonctions univariées. Nous analysons et raffinons une approche existante à base de développements de Taylor.Puis nous les remplaçons par des approximants plus fins, tels que les polynômes minimax, les séries tronquées de Chebyshev ou les interpolants de Chebyshev.Nous présentons aussi plusieurs applications: une relative à l'implantation de fonctions standard dans une bibliothèque mathématique (libm), une portant sur le calcul de développements tronqués en séries de Chebyshev de solutions d'ODE linéaires à coefficients polynômiaux et, enfin, un processus automatique d'évaluation de fonction à précision garantie sur une puce reconfigurable.
20
Greuet, Aurélien. "Optimisation polynomiale et variétés polaires : théorie, algorithmes et implantations." Phd thesis, Université de Versailles-Saint Quentin en Yvelines, 2013. http://tel.archives-ouvertes.fr/tel-00922805.
Full textAbstract:
Le calcul de l'infimum global $f^*$ d'un polynôme à $n$ variables sous contraintes est une question centrale qui apparaît dans de nombreux domaines des sciences de l'ingénieur. Pour certaines applications, il est important d'obtenir des résultats fiables. De nombreuses techniques ont été développées dans le cas où les contraintes sont données par des inéquations polynomiales. Dans cette thèse, on se concentre sur le problème d'optimisation d'un polynôme à $n$ variables sous des contraintes définies par des équations polynomiales à $n$ variables. Notre but est d'obtenir des outils, algorithmes et implémentations efficaces et fiables pour résoudre ces problèmes d'optimisation. Notre stratégie est de ramener le problème d'optimisation sous des contraintes qui définissent des ensembles algébriques de dimension quelconque à un problème équivalent, sous des nouvelles contraintes dont on maîtrise la dimension. La variété algébrique définie par ces nouvelles contraintes est l'union du lieu critique du polynôme objectif et d'un ensemble algébrique de dimension au plus 1. Pour cela, on utilise des objets géométriques définis comme lieux critiques de projections linéaires. Grâce au bon contrôle de la dimension, on prouve l'existence de certificats pour des bornes inférieures sur $f^*$ sur nos nouvelles variétés. Ces certificats sont donnés par des sommes de carrés et on ne suppose pas que $f^*$ est atteint. De même, on utilise les propriétés de nos objets géométriques pour concevoir un algorithme exact pour le calcul de $f^*$. S'il existe, l'algorithme renvoie aussi un minimiseur. Pour un problème avec $s$ contraintes et des polynômes de degrés au plus $D$, la complexité est essentiellement cubique en $(sD)^n$ et linéaire en la complexité d'évaluation des entrées. L'implantation, disponible sous forme de bibliothèque Maple, reflète cette complexité. Elle a permis de résoudre des problèmes inatteignables par les autres algorithmes exacts.
21
Bender, Matias Rafael. "Algorithms for sparse polynomial systems : Gröbner bases and resultants." Electronic Thesis or Diss., Sorbonne université, 2019. http://www.theses.fr/2019SORUS029.
Full textAbstract:
La résolution de systèmes polynomiaux est l’un des problèmes les plus anciens et importants en mathématiques informatiques et a des applications dans plusieurs domaines des sciences et de l’ingénierie. C'est un problème intrinsèquement difficile avec une complexité au moins exponentielle du nombre de variables. Cependant, dans la plupart des cas, les systèmes polynomiaux issus d'applications ont une structure quelconque. Dans cette thèse, nous nous concentrons sur l'exploitation de la structure liée à la faible densité des supports des polynômes; c'est-à-dire que nous exploitons le fait que les polynômes n'ont que quelques monômes à coefficients non nuls. Notre objectif est de résoudre les systèmes plus rapidement que les estimations les plus défavorables, qui supposent que tous les termes sont présents. Nous disons qu'un système creux est non mixte si tous ses polynômes ont le même polytope de Newton, et mixte autrement. La plupart des travaux sur la résolution de systèmes creux concernent le cas non mixte, à l'exception des résultants creux et des méthodes d'homotopie. Nous développons des algorithmes pour des systèmes mixtes. Nous utilisons les résultantes creux et les bases de Groebner. Nous travaillons sur chaque théorie indépendamment, mais nous les combinons également: nous tirons parti des propriétés algébriques des systèmes associés à une résultante non nulle pour améliorer la complexité du calcul de leurs bases de Groebner; par exemple, nous exploitons l’exactitude du complexe de Koszul pour déduire un critère d’arrêt précoce et éviter tout les réductions à zéro. De plus, nous développons des algorithmes quasi-optimaux pour décomposer des formes binairesSolving polynomial systems is one of the oldest and most important problems in computational mathematics and has many applications in several domains of science and engineering. It is an intrinsically hard problem with complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. In this thesis we focus on exploiting the structure related to the sparsity of the supports of the polynomials; that is, we exploit the fact that the polynomials only have a few monomials with non-zero coefficients. Our objective is to solve the systems faster than the worst case estimates that assume that all the terms are present. We say that a sparse system is unmixed if all its polynomials have the same Newton polytope, and mixed otherwise. Most of the work on solving sparse systems concern the unmixed case, with the exceptions of mixed sparse resultants and homotopy methods. In this thesis, we develop algorithms for mixed systems. We use two prominent tools in nonlinear algebra: sparse resultants and Groebner bases. We work on each theory independently, but we also combine them to introduce new algorithms: we take advantage of the algebraic properties of the systems associated to a non-vanishing resultant to improve the complexity of computing their Groebner bases; for example, we exploit the exactness of some strands of the associated Koszul complex to deduce an early stopping criterion for our Groebner bases algorithms and to avoid every redundant computation (reductions to zero). In addition, we introduce quasi-optimal algorithms to decompose binary forms
22
Colson, Pierre. "Cogèbres et calcul symbolique." Paris, EHESS, 2004. http://www.theses.fr/2004EHES0159.
Full textAbstract:
Les aspects algébriques de l'opérateur de translation sur un espace de polynômes sont bien connus. Ils permettent de rendre compte de notions telles que les polynômes d'Appell, les opérateurs invariants par translation et la formule d'Euler-McLaurin. Dans les années 1970, G. -C. Rota en a donné une approche nouvelle en interprétant l'opérateur de translation comme un comultiplication. Dans cette thèse, nous étendons certains résultats de Rota à une cogèbre arbitraire. Notre approche est caractérisée par le fait qu'elle peut être transposée dans d'autres contextes où l'on dispose d'une catégorie monoïdale. En la formulant par exemple pour les espaces localement convexes, on obtient une généralisation de la notion de moyenne-périodicité introduite par J. Delsarte dans les années 1930The algebra of the translation operator on a space of polynomials is well known and is the key to objects such as Appell polynomials, shift-invariant operators and the Euler-McLaurin summation formula. In the 1970's G. -C. Rota proposed a new approach by interpreting the translation operator as a comultiplication. In the present thesis, we generalize some of Rota's results to arbitrary coalgebras. Our appproach is singled out by the fact that it may be tranposed to any context where an appropriate monoidal category is available. For example, the formulation for locally convex spaces provides a generalization of the concept of mean-periodicity, which goes back to J. Delsarte in the 1930's
23
Milio, Enea. "Calcul de polynômes modulaires en dimension 2." Thesis, Bordeaux, 2015. http://www.theses.fr/2015BORD0285/document.
Full textAbstract:
Les polynômes modulaires sont utilisés dans le calcul de graphes d’isogénies, le calcul des polynômes de classes ou le comptage du nombre de points d’une courbe elliptique, et sont donc fondamentaux pour la cryptographie basée sur les courbes elliptiques. Des polynômes analogues sur les surfaces abéliennes principalement polarisées ont été introduits par Régis Dupont en 2006, qui a également proposé un algorithme pour les calculer, et des résultats théoriques sur ces polynômes ont été donnés dans un article de Bröker–Lauter, en 2009. Mais les polynômes sont très gros et ils n’ont pu être calculés que pour l’exemple minimal p = 2. Dans cette thèse, nous poursuivons les travaux de Dupont et Bröker–Lauter en permettant de calculer des polynômes modulaires pour des invariants basés sur les thêta constantes, avec lesquels nous avons pu calculer les polynômes jusqu’à p = 7, tout en démontrant des propriétés de ces polynômes. Mais des exemples plus grands ne semblent pas envisageables. Ainsi, nous proposons une nouvelle définition des polynômes modulaires dans laquelle l’on se restreint aux surfaces abéliennes principalement polarisées qui ont multiplication réelle par l’ordre maximal d’un corps quadratique réel afin d’obtenir des polynômes plus petits. Nous présentons alors de nombreux exemples de polynômes et des résultats théoriquesModular polynomials on elliptic curves are a fundamental tool used for the computation of graph of isogenies, class polynomials or for point counting. Thus, they are fundamental for the elliptic curve cryptography. A generalization of these polynomials for principally polarized abelian surfaces has been introduced by Régis Dupont in 2006, who has also described an algorithm to compute them, while theoretical results can been found in an article of Bröker– Lauter of 2009. But these polynomials being really big, they have been computed only in the minimal case p = 2. In this thesis, we continue the work of Dupont and Bröker–Lauter by defining and giving theoretical results on modular polynomials with new invariants, based on theta constants. Using these invariants, we have been able to compute the polynomials until p = 7 but bigger examples look intractable. Thus we define a new kind of modular polynomials where we restrict on the surfaces having real multiplication by the maximal order of a real quadratic field. We present many examples and theoretical results
24
Rollet, Yannis. "Vers une maîtrise des incertitudes en calculs des structures composites." Phd thesis, Ecole Polytechnique X, 2007. http://tel.archives-ouvertes.fr/tel-00257371.
Full textAbstract:
Les exigences de sécurité dans le domaine aéronautique imposent de tenir compte des diverses incertitudes affectant les structures, notamment la variabilité matériau. Malgré son essor la simulation numérique considère actuellement cette problématique de façon simplifiée, par exemple en usant d'abattements sur les valeurs de propriétés utilisées dans les calculs. Mais l'emploi accru des matériaux composites, par nature plus sensibles aux incertitudes, demande l'introduction de méthodes plus précises afin d'assurer une meilleure robustesse du dimensionnement. Pour cela, il a été développé une nouvelle démarche dite d'Analyse de Variabilité respectant certaines contraintes de la simulation numérique telle l'indépendance vis-à-vis du code de calcul (non-intrusivité) et la parcimonie des calculs. Face à la grande diversité des techniques de transport d'incertitudes, le choix a été fait de construire une démarche en s'appuyant sur les techniques de surfaces de réponses. Afin d'exploiter au mieux les diverses formes retenues (polynômes en les paramètres incertains, chaos polynomial, krigeage) pour construire l'approximation, la démarche a été rendue progressive. Des méthodes de validation croisée (leave-k-out, bootstrap) ont été utilisées pour évaluer la qualité de l'approximation. Ainsi, il est possible d'afficher une estimation des effets des incertitudes (par exemple sous la forme de barres d'erreur) mais également de quantifier la confiance dans cette estimation. La validation de la démarche s'est tout d'abord appuyée sur des exemples mathématiques, puis sur des situations mécaniques simples et analytiques. Les résultats obtenus montrent notamment une bonne cohérence vis-à-vis des simulations de Monte-Carlo pour un coût de calcul nettement inférieur. Les incertitudes considérées portent aussi bien sur des paramètres géométriques que matériau, avec notamment des caractéristiques propres aux composites (angles d'empilement, épaisseur des plis). L'application de la démarche à divers exemples (plaque multiperforée, assemblage boulonné,...) de calcul de structures par la méthode des éléments finis a souligné son applicabilité pour un surcoût de calcul raisonnable. Pour finir, le problème de la réduction des effets des incertitudes a été abordé sous des angles classiques comme la réduction des incertitudes d'entrée ou l'amélioration de la qualité des modèles utilisés. Enfin, une méthode plus originale, dite de consolidation de bases de données, utilisant les corrélations entre paramètres mesurés aux diverses échelles des composites a été proposée.
25
Larrieu, Robin. "Arithmétique rapide pour des corps finis." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLX073/document.
Full textAbstract:
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 augmenteThe 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
26
Bouvier, Cyril. "Algorithmes pour la factorisation d'entiers et le calcul de logarithme discret." Thesis, Université de Lorraine, 2015. http://www.theses.fr/2015LORR0053/document.
Full textAbstract:
Dans cette thèse, nous étudions les problèmes de la factorisation d'entier et de calcul de logarithme discret dans les corps finis. Dans un premier temps, nous nous intéressons à l'algorithme de factorisation d'entier ECM et présentons une méthode pour analyser les courbes elliptiques utilisées dans cet algorithme en étudiant les propriétés galoisiennes des polynômes de division. Ensuite, nous présentons en détail l'algorithme de factorisation d'entier NFS, et nous nous intéressons en particulier à l'étape de sélection polynomiale pour laquelle des améliorations d'algorithmes existants sont proposées. Puis, nous présentons les algorithmes NFS-DL et FFS pour le calcul de logarithme discret dans les corps finis. Nous donnons aussi des détails sur deux calculs de logarithme discret effectués durant cette thèse, l'un avec NFS-DL et l'autre avec FFS. Enfin, nous étudions une étape commune à l'algorithme NFS pour la factorisation et aux algorithmes NFS-DL et FFS pour le calcul de logarithme discret: l'étape de filtrage. Nous l'étudions en détail et nous présentons une amélioration dont nous validons l'impact en utilisant des données provenant de plusieurs calculs de factorisation et de logarithme discretIn this thesis, we study the problems of integer factorization and discrete logarithm computation in finite fields. First, we study the ECM algorithm for integer factorization and present a method to analyze the elliptic curves used in this algorithm by studying the Galois properties of division polynomials. Then, we present in detail the NFS algorithm for integer factorization and we study in particular the polynomial selection step for which we propose improvements of existing algorithms. Next, we present two algorithms for computing discrete logarithms in finite fields: NFS-DL and FFS. We also give some details of two computations of discrete logarithms carried out during this thesis, one with NFS-DL and the other with FFS. Finally, we study a common step of the NFS algorithm for integer factorization and the NFS-DL and FFS algorithms for discrete logarithm computations: the filtering step. We study this step thoroughly and present an improvement for which we study the impact using data from several computations of discrete logarithms and factorizations
27
Raksanyl, Atilla. "Utilisation du calcul formel pour l'étude des systèmes d'équations polynomiales applications en modélisation /." Grenoble 2 : ANRT, 1986. http://catalogue.bnf.fr/ark:/12148/cb37600594x.
Full text
28
Raksanyi, Atilla. "Utilisation du calcul formel pour l'étude des systèmes d'équations polynomiales (applications en modélisation)." Paris 9, 1986. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1986PA090011.
Full textAbstract:
De nombreux problèmes rencontrés en modélisation peuvent se ramener au calcul du rang d'une matrice, ou à la résolution d'un système d'équations polynomiales. C'est le cas pour l'étude des propriétés structurelles de commandabilité, d'observabilité, d'identifiable et de discernabilise de modelés paramétrés. Les langages de calcul formel sur ordinateur sont particulièrement adaptes à leur résolution.
29
Lassus, Saint-Genies Hugues de. "Elementary functions : towards automatically generated, efficient, and vectorizable implementations." Thesis, Perpignan, 2018. http://www.theses.fr/2018PERP0010/document.
Full textAbstract:
Les fonctions élémentaires sont utilisées dans de nombreux codes de calcul haute performance. Bien que les bibliothèques mathématiques (libm) auxquelles font appel ces codes proposent en général plusieurs variétés d'une même fonction, celles-ci sont figées lors de leur implémentation. Cette caractéristique représente un frein à la performance des programmes qui les utilisent car elles sont conçues pour être polyvalentes au détriment d'optimisations spécifiques. De plus, la duplication de modèles partagés rend la maintenance de ces libms plus difficile et sujette à l'introduction de bugs. Un défi actuel est de proposer des "méta-outils" visant la génération automatique de code performant pour l'évaluation des fonctions élémentaires. Ces outils doivent permettre la réutilisation d'algorithmes efficaces et génériques pour différentes variétés de fonctions ou architectures matérielles. Il devient alors possible de générer des libms optimisées pour des besoins très spécifiques avec du code générateur factorisé, qui facilite sa maintenance. Dans un premier temps, nous proposons un algorithme original permettant de générer des tables sans erreur pour les fonctions trigonométriques et hyperboliques. Puis nous étudions les performances de schémas d'évaluation polynomiale vectorisés, premier pas vers la génération de fonctions vectorisées efficaces. Enfin, nous proposons une méta-implémentation d'un logarithme vectorisé, factorisant la génération de code pour différents formats et architectures. Ces contributions sont compétitives comparées à d'autres solutions, justifiant le développement de tels méta-codesElementary mathematical functions are pervasive in many high performance computing programs. However, although the mathematical libraries (libms), on which these programs rely, generally provide several flavors of the same function, these are fixed at implementation time. Hence this monolithic characteristic of libms is an obstacle for the performance of programs relying on them, because they are designed to be versatile at the expense of specific optimizations. Moreover, the duplication of shared patterns in the source code makes maintaining such code bases more error prone and difficult. A current challenge is to propose "meta-tools" targeting automated high performance code generation for the evaluation of elementary functions. These tools must allow reuse of generic and efficient algorithms for different flavours of functions or hardware architectures. Then, it becomes possible to generate optimized tailored libms with factorized generative code, which eases its maintenance. First, we propose an novel algorithm that allows to generate lookup tables that remove rounding errors for trigonometric and hyperbolic functions. The, we study the performance of vectorized polynomial evaluation schemes, a first step towards the generation of efficient vectorized elementary functions. Finally, we develop a meta-implementation of a vectorized logarithm, which factors code generation for different formats and architectures. Our contributions are shown competitive compared to free or commercial solutions, which is a strong incentive to push for developing this new paradigm
30
Dessombz, Olivier. "Analyse dynamique de structures comportant des paramètres incertains." Ecully, Ecole centrale de Lyon, 2000. http://www.theses.fr/2000ECDL0036.
Full textAbstract:
Dans le cadre de la mobilisation de structures comportant des paramètres incertains, on s'intéresse aux caractéristiques des réponses statiques et dynamiques de systèmes mécaniques. On distingue dans cette étude le cas de paramètres aléatoires à loi de probabilité connue et le cas de variables dont on ne connaît que les bornes. Dans cette optique, on s'applique dans une première partie à décrire les réponses dynamiques, aussi bien les fonctions de transfert que les modes propres, de structures comportant des paramètres modélisés comme des variables aléatoires. Pour ce faire, on utilise une méthode de projection sur une base de polynômes orthogonaux (chaos polynomial), qui permet d'obtenir les caractéristiques principales des réponses. Dans une deuxième partie, on utilise l'arihmétique des intervalles pour résoudre les problèmes statiques et dynamiques. Après avoir proposé une formulation adaptée à la modélisation des systèmes mécaniques, on reformule un algorithme de résolution de systèmes linéaires intervalles, qu'on utilise alors pour trouver les enveloppes des réponses cherchéesWe are interested in the modelling of structures with uncertain parameters. We focus on the characteristics of static and dynamic responses of such mechanical systems. We distinguish in this study two cases : first, the case of random parameters with a known probability law and second the case of variables of which only the bounds are known. In a first part, we investigate the case of structures with uncertain parameters modelled as random variables. We are particularly interested in the dynamic responses, as well the frequency response functions as the eigenmodes. An inovative method is carried out, which consists in a projection on orthogonal polynomial (polynomial chaos) that leads to the main stochastic characteristics of the responses. In a second part, we use the interval arithmetic to solve static and dynamic problems. We first propose an adapted formulation of the mathematical problems with respect to the finite element modeling of mechanical systems. We then introduce a new formulation of an iterative algorithm that leads to enveloppes of responses for interval linear systems
31
Melczer, Stephen. "Analytic Combinatorics in Several Variables : Effective Asymptotics and Lattice Path Enumeration." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSEN013/document.
Full textAbstract:
La combinatoire analytique étudie le comportement asymptotique des suites à travers les propriétés analytiques de leurs fonctions génératrices. Ce domaine a conduit au développement d’outils profonds et puissants avec de nombreuses applications. Au delà de la théorie univariée désormais classique, des travaux récents en combinatoire analytique en plusieurs variables (ACSV) ont montré comment calculer le comportement asymptotique d’une grande classe de fonctions différentiellement finies:les diagonales de fractions rationnelles. Cette thèse examine les méthodes de l’ACSV du point de vue du calcul formel, développe des algorithmes rigoureux et donne les premiers résultats de complexité dans ce domaine sous des hypothèses très faibles. En outre, cette thèse donne plusieurs nouvelles applications de l’ACSV à l’énumération des marches sur des réseaux restreintes à certaines régions: elle apporte la preuve de plusieurs conjectures ouvertes sur les comportements asymptotiques de telles marches,et une étude détaillée de modèles de marche sur des réseaux avec des étapes pondéréesThe field of analytic combinatorics, which studies the asymptotic behaviour ofsequences through analytic properties of their generating functions, has led to thedevelopment of deep and powerful tools with applications across mathematics and thenatural sciences. In addition to the now classical univariate theory, recent work in thestudy of analytic combinatorics in several variables (ACSV) has shown how to deriveasymptotics for the coefficients of certain D-finite functions represented by diagonals ofmultivariate rational functions. This thesis examines the methods of ACSV from acomputer algebra viewpoint, developing rigorous algorithms and giving the firstcomplexity results in this area under conditions which are broadly satisfied.Furthermore, this thesis gives several new applications of ACSV to the enumeration oflattice walks restricted to certain regions. In addition to proving several openconjectures on the asymptotics of such walks, a detailed study of lattice walk modelswith weighted steps is undertaken
32
Bréhard, Florent. "Certified numerics in function spaces : polynomial approximations meet computer algebra and formal proof." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSEN032/document.
Full textAbstract:
Le calcul rigoureux vise à produire des représentations certifiées pour les solutions de nombreux problèmes, notamment en analyse fonctionnelle, comme des équations différentielles ou des problèmes de contrôle optimal. En effet, certains domaines particuliers comme l’ingénierie des systèmes critiques ou les preuves mathématiques assistées par ordinateur ont des exigences de fiabilité supérieures à ce qui peut résulter de l’utilisation d’algorithmes relevant de l’analyse numérique classique.Notre objectif consiste à développer des algorithmes à la fois efficaces et validés / certifiés, dans le sens où toutes les erreurs numériques (d’arrondi ou de méthode) sont prises en compte. En particulier, nous recourons aux approximations polynomiales rigoureuses combinées avec des méthodes de validation a posteriori à base de points fixes. Ces techniques sont implémentées au sein d’une bibliothèque écrite en C, ainsi que dans un développement de preuve formelle en Coq, offrant ainsi le plus haut niveau de confiance, c’est-à-dire une implémentation certifiée.Après avoir présenté les opérations élémentaires sur les approximations polynomiales rigoureuses, nous détaillons un nouvel algorithme de validation pour des approximations sous forme de séries de Tchebychev tronquées de fonctions D-finies, qui sont les solutions d’équations différentielles ordinaires linéaires à coefficients polynomiaux. Nous fournissons une analyse fine de sa complexité, ainsi qu’une extension aux équations différentielles ordinaires linéaires générales et aux systèmes couplés de telles équations. Ces méthodes dites symboliques-numériques sont ensuite utilisées dans plusieurs problèmes reliés : une nouvelle borne sur le nombre de Hilbert pour les systèmes quartiques, la validation de trajectoires de satellites lors du problème du rendez-vous linéarisé, le calcul de polynômes d’approximation optimisés pour l’erreur d’évaluation, et enfin la reconstruction du support et de la densité pour certaines mesures, grâce à des techniques algébriquesRigorous numerics aims at providing certified representations for solutions of various problems, notably in functional analysis, e.g., differential equations or optimal control. Indeed, specific domains like safety-critical engineering or computer-assisted proofs in mathematics have stronger reliability requirements than what can be achieved by resorting to standard numerical analysis algorithms. Our goal consists in developing efficient algorithms, which are also validated / certified in the sense that all numerical errors (method or rounding) are taken into account. Specifically, a central contribution is to combine polynomial approximations with a posteriori fixed-point validation techniques. A C code library for rigorous polynomial approximations (RPAs) is provided, together with a Coq formal proof development, offering the highest confidence at the implementation level.After providing basic operations on RPAs, we focus on a new validation algorithm for Chebyshev basis solutions of D-finite functions, i.e., solutions of linear ordinary differential equations (LODEs) with polynomial coefficients. We give an in-depth complexity analysis, as well as an extension to general LODEs, and even coupled systems of them. These symbolic-numeric methods are finally used in several related problems: a new lower bound on the Hilbert number for quartic systems; a validation of trajectories arising in the linearized spacecraft rendezvous problem; the design of evaluation error efficient polynomial approximations; and the support and density reconstruction of particular measures using algebraic techniques
33
Svartz, Jules. "Résolution de systèmes polynomiaux structurés de dimension zéro." Thesis, Paris 6, 2014. http://www.theses.fr/2014PA066621/document.
Full textAbstract:
Les systèmes polynomiaux à plusieurs variables apparaissent naturellement dans de nombreux domaines scientifiques. Ces systèmes issus d'applications possèdent une structure algébrique spécifique. Une méthode classique pour résoudre des systèmes polynomiaux repose sur le calcul d'une base de Gröbner de l'idéal associé au système. Cette thèse présente de nouveaux outils pour la résolution de tels systèmes structurés, lorsque la structure est induite par l'action d'un groupe ou une structure monomiale particulière, qui englobent les systèmes multi-homogènes ou quasi-homogènes. D'une part, cette thèse propose de nouveaux algorithmes qui exploitent ces structures algébriques pour améliorer l'efficacité de la résolution de systèmes (systèmes invariant sous l'action d'un groupe ou à support dans un ensemble de monômes particuliers). Ces techniques permettent notamment de résoudre un problème issu de la physique pour des instances hors de portée jusqu'à présent. D'autre part, ces outils permettent d'améliorer les bornes de complexité de résolution de plusieurs familles de systèmes polynomiaux structurés (systèmes globalement invariant sous l'action d'un groupe abélien, individuellement invariant sous l'action d'un groupe quelconque, ou ayant leur support dans un même polytope). Ceci permet en particulier d'étendre des résultats connus sur les systèmes bilinéaires aux systèmes mutli-homogènes générauxMultivariate polynomial systems arise naturally in many scientific fields. These systems coming from applications often carry a specific algebraic structure.A classical method for solving polynomial systems isbased on the computation of a Gr\"obner basis of the ideal associatedto the system.This thesis presents new tools for solving suchstructured systems, where the structure is induced by the action of a particular group or a monomial structure, which include multihomogeneous or quasihomogeneous systems.On the one hand, this thesis proposes new algorithmsusing these algebraic structures to improve the efficiency of solving suchsystems (invariant under the action of a group or having a support in a particular set of monomials). These techniques allow to solve a problem arising in physics for instances out of reach until now.On the other hand, these tools improve the complexity bounds for solving several families of structured polynomial systems (systems globally invariant under the action of an abelian group or with their support in the same polytope). This allows in particular to extend known results on bilinear systems to general mutlihomogeneous systems
34
Javan, Peykar Ariyan. "Explicit polynomial bounds for Arakelov invariants of Belyi curves." Thesis, Paris 11, 2013. http://www.theses.fr/2013PA112075/document.
Full textAbstract:
On borne explicitement la hauteur de Faltings d'une courbe sur le corps de nombres algèbriques en son degré de Belyi. Des résultats similaires sont démontré pour trois autres invariants arakeloviennes : le discriminant, l'invariant delta et l'auto-intersection de omega. Nos résultats nous permettent de borner explicitement les invariantes arakeloviennes des courbes modulaires, des courbes de Fermat et des courbes de Hurwitz. En plus, comme application, on montre que l'algorithme de Couveignes-Edixhoven-Bruin est polynomial sous l’hypothèse de Riemann pour les fonctions zeta des corps de nombres. Ceci était connu uniquement pour certains sous-groupes de congruence. Finalement, on utilise nos résultats pour démontrer une conjecture de Edixhoven, de Jong et Schepers sur la hauteur de Faltings d'un revêtement ramifié de la droite projective sur l'anneau des entiersWe explicitly bound the Faltings height of a curve over the field of algebraic numbers in terms of the Belyi degree. Similar bounds are proven for three other Arakelov invariants: the discriminant, Faltings' delta invariant and the self-intersection of the dualizing sheaf. Our results allow us to explicitly bound these Arakelov invariants for modular curves, Hurwitz curves and Fermat curves. Moreover, as an application, we show that the Couveignes-Edixhoven-Bruin algorithmtime under the Riemann hypothesis for zeta-functions of number fields. This was known before only for certain congruence subgroups. Finally, we utilize our results to prove a conjecture of Edixhoven, de Jong and Schepers on the Faltings height of a branched cover of the projective line over the ring of integers
35
Guyon, Christophe. "Calcul symbolique pour la planification de trajectoire des systèmes dynamiques Nilpotents." Lille 1, 1995. http://www.theses.fr/1995LIL10146.
Full textAbstract:
Dans le cadre de la commande des systèmes dynamiques non holonomes (tels certains robots), ce travail s'intéresse au calcul de fonctions d'entrée (commandes) menant le système exactement dans une configuration cible arbitraire. Les méthodes développées et étudiées ici s'appliquent au cas ou l'algèbre de Lie des champs de vecteurs du système est nilpotente. L'utilisation de la combinatoire des mots des structures libres associées aux groupes et algèbres de Lie permet dans ce cas de transformer ce problème différentiel en un problème algébrique de géométrie réelle. On parvient à calculer symboliquement les entrées polynomiales ou constantes par morceaux les plus simples en terme du degré des polynômes ou du nombre d'inconnues nécessaires (les coefficients des polynômes, les valeurs des entrées constantes). A l'inverse, on calcule des solutions paramétrées lorsque les inconnues qui caractérisent l'entrée sont en surnombre. Nous présentons des résolutions complètes dans le cas des systèmes nilpotents à l'ordre 4 (correspondant à 5 équations différentielles, une pour chaque variable d'état). Une résolution complète a pu être calculée avec des entrées polynomiales, dans le cas d'un système nilpotent à l'ordre 6 (correspondant à 14 équations différentielles). En particulier, dans le cas des systèmes nilpotents à l'ordre 4, on a pu faire passer le nombre d'inconnues nécessaires à 8 au lieu des 26 nécessaires à la seule autre méthode générale connue, due à H. J. Sussmann. Par ailleurs le lien est fait avec les systèmes plats (M. Fliess).
36
Ayad, Ali. "Complexité de résolution de systèmes algébriques paramétrés." Rennes 1, 2006. https://tel.archives-ouvertes.fr/tel-00127383.
Full textAbstract:
On présente trois algorithmes dans cette thèse. Le premier algorithme résout des systèmes polynomiaux homogènes et paramétrés zéro-dimensionnels avec un temps simplement exponentiel en le nombre n des inconnus. Cet algorithme décompose l'espace des paramètres en un nombre fini d'ensembles constructibles et calcule le nombre fini de solutions par des représentations rationnelles paramétriques uniformes sur chaque ensemble constructible. Le deuxième algorithme factorise absolument des polynômes multivariés paramétrés avec un temps simplement exponentiel en n et en la borne supérieure d de degrés de polynômes à factoriser. Le troisième algorithme décompose les variétés algébriques définies par des systèmes algébriques paramétrés de dimensions positives en composantes absolument irréductibles d'une manière uniforme sur les valeurs des paramètres. La complexité de cet algorithme est doublement exponentielle en n. D'autre part, la borne inférieure du problème de résolution de systèmes algébriques paramétrés est doublement exponentielle en n.
37
Perrinel, Matthieu. "Investigating the expressivity of linear logic subsystems characterizing polynomial time." Thesis, Lyon, École normale supérieure, 2015. http://www.theses.fr/2015ENSL1001/document.
Full textAbstract:
La complexité implicite est la caractérisation de classes de complexité par des restrictions syntaxiques sur des modèles de calcul. Plusieurs sous-systèmes de la logique linéaire caractérisant le temps polynomial ont été définis: ces systèmes sont corrects (les termes normalisent en temps polynomial) et complets (il est possible de simuler une machine de Turing pendant un nombre polynomial d'étapes). Un des buts sur le long terme est de donner statiquement des bornes de complexité. C’est pourquoi nous cherchons les caractérisations du temps polynomial les plus expressives possible. Notre principal outil est la sémantique des contextes: des jetons voyagent à travers le réseau selon certaines règles. Les chemins définis par ces jetons représentent la réduction du réseau. Contrairement aux travaux précédents, nous ne définissons pas directement des sous-systèmes de la logique linéaire. Nous définissons d'abord des relations -> sur les sous-termes des réseaux de preuves tel que: B -> C ssi ”le nombre de copies de B dépend du nombre de copies de C”. L’acyclicité de -> borne le nombre de copies de chaque sous-terme, donc la complexité du terme. Ensuite nous définissons des sous-systèmes de la logique linéaire assurant l’acyclicité de ->. Nous étudions aussi des caractérisations du temps élémentaire et primitif récursif. Dans le but d’adapter nos sous-systèmes de la logique linéaire à des langages plus riches, nous adaptons la sémantique des contextes aux réseaux d’interaction, utilisés comme langage cible pour de petits langage de programmation. Nous utilisons cette sémantique des contexte pour définir une sémantique dénotationnelle sur les réseaux d’interactionsImplicit computational complexity is the characterization of complexity classes by syntactic restrictions on computation models. Several subsystems of linear logic characterizing polynomial time have been defined : these systems are sound (terms normalize in polynomial time) and complete (it is possible to simulate a Turing machine during a polynomial number of steps). One of the long term goals is to statically prove complexity bounds. This is why we are looking for the most expressive characterizations possible. Our main tool is context semantics : tokens travel across proof-nets (programs of linear logic) according to some rules. The paths defined by these tokens represent the reduction of the proof-net.Contrary to previous works, we do not directly define subsystems of linear logic. We first define relations -> on subterms of proof-nets such that: B -> C means \the number of copies of B depends on the number of copies of C". The acyclicity of -> allows us to bound the number of copies of any subterm, this bounds the complexity of the term. Then, we define subsystems of linear logic guaranteeing the acyclicity of ->. We also study characterizations of elementary time and primitive recursive time. In orderto adapt our linear logic subsystems to richer languages, we adapt the context semantics to interaction nets, used as a target language for small programming languages. We use this context semantics to define a denotational semantics on interaction nets
38
Pasqualini, Olivier. "Éléments finis stochastiques étendus pour le calcul en fatigue de joints soudés avec géométries aléatoires." Nantes, 2013. http://www.theses.fr/2013NANT2090.
Full textAbstract:
Les cordons de soudure sont des éléments essentiels présents lors de la construction de nombreuses structures fixes, flottantes ou immergées. L’importance structurelle de ces éléments requiert d’avoir une parfaite connaissance de leur tenue en fatigue dans le but de prédire le comportement de la structure sous l’effet de charges cycliques. Le calcul de durée de vie d’un cordon de soudure est dépendant de plusieurs paramètres, notamment de sa géométrie. Le calcul du coefficient de concentration de contraintes Kt permet de relier la contrainte RDM connue ou facilement calculable avec le maximum de la contrainte dans la structure et de déterminer la durée de vie de la structure via les courbes de Wöhler. Afin de réaliser un calcul du Kt intégrant des données réalistes et leur incertitude, des mesures sur cordon de soudure ont été effectuées sur des structures réelles en utilisant un procédé de contrôle non-destructif par mesure au laser. Une analyse statistique de ces mesures a été effectuée afin de modéliser les paramètres géométriques du cordon par des variables aléatoires dont on a identifié les distributions de probabilité. Le calcul du Kt a été effectué en utilisant la méthode aux Eléments Finis Stochastiques Etendus combinant la méthode SSFEM efficace pour prendre en compte l’aléa physique du domaine et la méthode XFEM efficace pour délimiter implicitement la géométrie du domaine à l’aide de level-sets. En particulier, nous utilisons une méthode non-intrusive par régression permettant d’obtenir une formulation du Kt sur une base de chaos polynomial en réalisant un minimum de tirages aléatoires. Sur cette base, le manuscrit aboutit à une formulation semi-probabilisteWelded joints are essential components for the construction of various fixed or floating structures. These elements are so important that we need to fully understand the fatigue process in order to foresee the structural behaviour under cyclic loading. The fatigue lifetime computation of a welded joint depends of various parameters such as the geometry of the structure. The stress concentration factor computation Kt is an efficient key parameter to model the fatigue lifetime. It has the advantage to link theoretical stress with the maximum value of local stresses and so with the fatigue lifetime thanks to S-N curves. In order to compute the Kt coefficient from real data and their uncertainties, some measurements along welded joints were realized by using a Non-Destructive Control device with laser process measurement. A statistical analysis of these measures were carried out to model the geometrical parameters by random variables and to identify their probability distribution. Kt-computation were performed by using eXtended Stochastic Finite Element Method; this computation method combines the Stochastic Finite Element Method, efficient to solve problems governed by random physical inputs, and the XFEM, efficient to implicitly define the domain geometry by using level-sets. In particular, we use a non-intrusive method of least-square computation to carry out, with a few numbers of random values, a Kt formulation defined on Polynomial Chaos base. From these results, an original semi-probabilistic model is suggested which introduces the geometrical parameters
39
Leroy, Richard. "Certificats de positivité et minimisation polynomiale dans la base de Bernstein multivariée." Phd thesis, Université Rennes 1, 2008. http://tel.archives-ouvertes.fr/tel-00349444.
Full textAbstract:
L'étude des polynômes réels en plusieurs variables est un problème classique en géométrie algébrique réelle et en calcul formel. Plusieurs questions sont naturelles : positivité éventuelle, calcul du minimum...Nous nous proposons, dans cette thèse, d'étudier ces questions dans le cas particulier où l'étude est menée sur un simplexe de $\R^k$.
L'outil essentiel dans notre travail est la base de Bernstein, plus adaptée à la situation que la traditionnelle base des monômes. Elle jouit notamment de propriétés de positivité et d'encadrement essentielles à notre étude.
Elle permet tout d'abord d'obtenir un algorithme décidant si un polynôme $f$ est positif sur un simplexe $V$, et le cas échéant, fournissant une écriture de $f$ rendant triviale cette positivité : on parle de certificat de positivité.
En outre, elle est à l'origine d'un algorithme de minimisation polynomiale sur un simplexe. Ces deux algorithmes sont certifiés, et l'étude de leur complexité est menée dans cette thèse. Ils ont également fait l'objet d'implémentation sur ordinateur.
40
Nesme, Vincent. "Complexité en requêtes et symétries." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2007. http://tel.archives-ouvertes.fr/tel-00156762.
Full textAbstract:
Ces travaux portent sur l'étude de la complexité en requêtes de problèmes symétriques, dans les cadres du calcul probabiliste classique
et du calcul quantique.
Il est montré, dans le cas quantique, une application de la méthode de
bornes inférieures dite "polynomiale" au calcul de la complexité en
requêtes des problèmes de sous-groupes cachés abéliens, via la technique de "symétrisation".
Dans le cas du calcul probabiliste, sous une hypothèse de "symétrie
transitive" des problèmes, il est donné une formule combinatoire
permettant de calculer la complexité en requêtes exacte du meilleur
algorithme non-adaptatif. De plus, il est mis en évidence que sous
certaines hypothèses de symétrie, ce meilleur algorithme non-adaptatif
est optimal même parmi les algorithmes probabilistes plus généraux, ce qui donne pour la classe de problèmes correspondante une expression exacte de la complexité en requêtes.
41
Diamoutani, Mamadou. "De quelques méthodes de calcul de valeurs propres de grandes matrices." Grenoble INPG, 1986. http://tel.archives-ouvertes.fr/tel-00321850.
Full textAbstract:
Etude de quelques algorithmes de calcul d'éléments propres de matrices de grande taille : méthode des puissances, itérations de Tchébychev simultanées et algorithme de Lanczos, base orthonormée du sous-espace dominant construite à partir de la forme de Schur de la matrice de projection. Présentation des résultats numériques
42
Tran, Cuong. "Calcul formel dans la base des polynômes unitaires de Chebyshev." Thesis, Paris 6, 2015. http://www.theses.fr/2015PA066379/document.
Full textAbstract:
Nous proposons des méthodes simples et efficaces pour manipuler des expressions trigonométriques de la forme $F=\sum_{k} f_k\cos\tfrac{k\pi}{n}, f_k\in Z$ où $dWe propose a set of simple and fast algorithms for evaluating and using trigonometric expressions in the form $F=\sum_{k}f_k\cos\frac{k\pi}{n}$, $f_k\in Z$ where $d
43
Lagarde, Guillaume. "Contributions to arithmetic complexity and compression." Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCC192/document.
Full textAbstract:
Cette thèse explore deux territoires distincts de l’informatique fondamentale : la complexité et la compression. Plus précisément, dans une première partie, nous étudions la puissance des circuits arithmétiques non commutatifs, qui calculent des polynômes non commutatifs en plusieurs indéterminées. Pour cela, nous introduisons plusieurs modèles de calcul, restreints dans leur manière de calculer les monômes. Ces modèles en généralisent d’autres, plus anciens et largement étudiés, comme les programmes à branchements. Les résultats sont de trois sortes. Premièrement, nous donnons des bornes inférieures sur le nombre d’opérations arithmétiques nécessaires au calcul de certains polynômes tels que le déterminant ou encore le permanent. Deuxièmement, nous concevons des algorithmes déterministes fonctionnant en temps polynomial pour résoudre le problème du test d’identité polynomiale. Enfin, nous construisons un pont entre la théorie des automates et les circuits arithmétiques non commutatifs, ce qui nous permet de dériver de nouvelles bornes inférieures en utilisant une mesure reposant sur le rang de la matrice dite de Hankel, provenant de la théorie des automates. Une deuxième partie concerne l’analyse de l’algorithme de compression sans perte Lempel-Ziv. Pourtant très utilisé, sa stabilité est encore mal établie. Vers la fin des années 90s, Jack Lutz popularise la question suivante, connue sous le nom de « one-bit catastrophe » : « étant donné un mot compressible, est-il possible de le rendre incompressible en ne changeant qu’un seul bit ? ». Nous montrons qu’une telle catastrophe est en effet possible. Plus précisément, en donnant des bornes optimales sur la variation de la taille de la compression, nous montrons qu’un mot « très compressible » restera toujours compressible après modification d’un bit, mais que certains mots « peu compressibles » deviennent en effet incompressiblesThis thesis explores two territories of computer science: complexity and compression. More precisely, in a first part, we investigate the power of non-commutative arithmetic circuits, which compute multivariate non-commutative polynomials. For that, we introduce various models of computation that are restricted in the way they are allowed to compute monomials. These models generalize previous ones that have been widely studied, such as algebraic branching programs. The results are of three different types. First, we give strong lower bounds on the number of arithmetic operations needed to compute some polynomials such as the determinant or the permanent. Second, we design some deterministic polynomial-time algorithm to solve the white-box polynomial identity problem. Third, we exhibit a link between automata theory and non-commutative arithmetic circuits that allows us to derive some old and new tight lower bounds for some classes of non-commutative circuits, using a measure based on the rank of a so-called Hankel matrix. A second part is concerned with the analysis of the data compression algorithm called Lempel-Ziv. Although this algorithm is widely used in practice, we know little about its stability. Our main result is to show that an infinite word compressible by LZ’78 can become incompressible by adding a single bit in front of it, thus closing a question proposed by Jack Lutz in the late 90s under the name “one-bit catastrophe”. We also give tight bounds on the maximal possible variation between the compression ratio of a finite word and its perturbation—when one bit is added in front of it
44
Blondel, Jean-Louis. "Étude et mise en oeuvre d'une méthode de décomposition additive pour le calcul des valeurs propres d'une matrice." Caen, 1988. http://www.theses.fr/1988CAEN2035.
Full textAbstract:
On propose un nouvel algorithme basé sur une décomposition additive pour le calcul des valeurs propres d'une matrice. On établit une condition suffisante de convergence. L'utilisation de la méthode Cestac permet d'obtenir facilement la précision sur les valeurs propres obtenues. On donne de nombreux exemples numériques illustrant l'efficacité de l'algorithme.
45
Rérat, Michel. "Methode invariante de jauge pour le calcul de proprietes magnetiques : applications a de petites molecules." Paris 6, 1987. http://www.theses.fr/1987PA066024.
Full textAbstract:
Developpement d'une technique de calcul des proprietes magnetiques qui combine les avantages des methodes classiques tenant compte de la correlation electronique et qui conserve l'invariance de jauge de la methode des polynomes par un systeme de compensation interne. Calcul des corrections rovibroniques, decrites analytiquement par la methode des perturbation, pour des molecules diatomiques (h::(2), co) pour une comparaison des resultats theoriques et experimentaux
46
Dridi, Marwa. "Sur les méthodes rapides de résolution de systèmes de Toeplitz bandes." Thesis, Littoral, 2016. http://www.theses.fr/2016DUNK0402/document.
Full textAbstract:
Cette thèse vise à la conception de nouveaux algorithmes rapides en calcul numérique via les matrices de Toeplitz. Tout d'abord, nous avons introduit un algorithme rapide sur le calcul de l'inverse d'une matrice triangulaire de Toeplitz en se basant sur des notions d'interpolation polynomiale. Cet algorithme nécessitant uniquement deux FFT(2n) est manifestement efficace par rapport à ses prédécésseurs. ensuite, nous avons introduit un algorithme rapide pour la résolution d'un système linéaire de Toeplitz bande. Cette approche est basée sur l'extension de la matrice donnée par plusieurs lignes en dessus, de plusieurs colonnes à droite et d'attribuer des zéros et des constantes non nulles dans chacune de ces lignes et de ces colonnes de telle façon que la matrice augmentée à la structure d'une matrice triangulaire inférieure de Toeplitz. La stabilité de l'algorithme a été discutée et son efficacité a été aussi justifiée. Finalement, nous avons abordé la résolution d'un système de Toeplitz bandes par blocs bandes de Toeplitz. Ceci étant primordial pour établir la connexion de nos algorithmes à des applications en restauration d'images, un domaine phare en mathématiques appliquéesThis thesis aims to design new fast algorithms for numerical computation via the Toeplitz matrices. First, we introduced a fast algorithm to compute the inverse of a triangular Toeplitz matrix with real and/or complex numbers based on polynomial interpolation techniques. This algorithm requires only two FFT (2n) is clearly effective compared to predecessors. A numerical accuracy and error analysis is also considered. Numerical examples are given to illustrate the effectiveness of our method. In addition, we introduced a fast algorithm for solving a linear banded Toeplitz system. This new approach is based on extending the given matrix with several rows on the top and several columns on the right and to assign zeros and some nonzero constants in each of these rows and columns in such a way that the augmented matrix has a lower triangular Toeplitz structure. Stability of the algorithm is discussed and its performance is showed by numerical experiments. This is essential to connect our algorithms to applications such as image restoration applications, a key area in applied mathematics
47
Garreau, Pierre-Olivier. "Contribution à un environnement pour le calcul scientifique et la modélisation : strates et systèmes polynômiaux sur les corps finis." Phd thesis, Université Joseph Fourier (Grenoble), 1994. http://tel.archives-ouvertes.fr/tel-00344983.
Full textAbstract:
Cette thèse concerne le développement et la mise en œuvre d'un environnement pour le calcul scientifique et la modélisation. L'approche retenue est celle d'une décomposition stratifiée des problèmes, ceci dans un double but: marquer le cheminement progressif des étapes de description, allant de l'énoncé informel vers un langage cible en passant par des langages intermédiaires plus ou moins formalisés ; et, d'obtenir une décomposition structurée, modulaire, pour aller du problème initial vers le programme. Dans le but de vérifier la cohérence des descriptions, des schémas de résolutions, des décompositions, nous associons à tout énoncé des conditions logiques dépendant du langage de description. Pour cela, il nous a paru nécessaire d'étudier les formulations logiques décrites par des systèmes polynômiaux sur les corps finis de la forme Z/pZ. L'étude de ces systèmes nous conduisent à traiter le problème de l'élimination des quantificateurs sur un corps fini, le problème du calcul du résultat sur Z/pZ: des algorithmes sont proposés, ainsi qu'une généralisation de la méthode de Dixon-Biard. Le problème de la déduction est aussi abordé. Ces algorithmes nous permettent de vérifier localement la cohérence d'un énoncé mais aussi d'une décomposition de problème. Ceci rend envisageable une vérification globale. Un éditeur de strates sous Grif est présenté
48
Nguyen, Viet anh. "Contributions to tensor models, Hurwitz numbers and Macdonald-Koornwinder polynomials." Thesis, Angers, 2017. http://www.theses.fr/2017ANGE0052/document.
Full textAbstract:
Dans cette thèse, j’étudie trois sujets reliés : les modèles de tenseurs, les nombres de Hurwitz et les polynômes de Macdonald-Koornwinder. Les modèles de tenseurs généralisent les modèles de matrices en tant qu’une approche à la gravité quantique en dimension arbitraire (les modèles de matrices donnent une version bidimensionnelle). J’étudie un modèle particulier qui s’appelle le modèle quartique mélonique. Sa spécialité est qu’il s’écrit en termes d’un modèle de matrices qui est lui-même aussi intéressant. En utilisant les outils bien établis, je calcule les deux premiers ordres de leur 1=N expansion. Parmi plusieurs interprétations, les nombres de Hurwitz comptent le nombre de revêtements ramifiés de surfaces de Riemann. Ils sont connectés avec de nombreux sujets en mathématiques contemporaines telles que les modèles de matrices, les équations intégrables et les espaces de modules. Ma contribution principale est une formule explicite pour les nombres doubles avec 3-cycles complétées d’une part. Cette formule me permet de prouver plusieurs propriétés intéressantes de ces nombres. Le dernier sujet de mon étude est les polynôme de Macdonald et Koornwinder, plus précisément les identités de Littlewood. Ces polynômes forment les bases importantes de l’algèbre des polynômes symétriques. Un des problèmes intrinsèques dans la théorie des fonctions symétriques est la décomposition d’un polynôme symétrique dans la base de Macdonald. La décomposition obtenue (notamment si les coefficients sont raisonnablement explicites et compacts) est nommée une identité de Littlewood. Dans cette thèse, j’étudie les identités démontrées récemment par Rains et Warnaar. Mes contributions incluent une preuve d’une extension d’une telle identité et quelques progrès partiels vers la généralisation d’une autreIn this thesis, I study three related subjects: tensor models, Hurwitz numbers and Macdonald-Koornwinder polynomials. Tensor models are generalizations of matrix models as an approach to quantum gravity in arbitrary dimensions (matrix models give a 2D version). I study a specific model called the quartic melonic tensor model. Its specialty is that it can be transformed into a multi-matrix model which is very interesting by itself. With the help of well-established tools, I am able to compute the first two leading orders of their 1=N expansion. Among many interpretations, Hurwitz numbers count the number of weighted ramified coverings of Riemann surfaces. They are connected to many subjects of contemporary mathematics such as matrix models, integrable equations and moduli spaces of complex curves. My main contribution is an explicit formula for one-part double Hurwitz numbers with completed 3-cycles. This explicit formula also allows me to prove many interesting properties of these numbers. The final subject of my study is Macdonald-Koornwinder polynomials, in particular their Littlewood identities. These polynomials form important bases of the algebra of symmetric polynomials. One of the most important problems in symmetric function theory is to decompose a symmetric polynomial into the Macdonald basis. The obtained decomposition (in particular, if the coefficients are explicit and reasonably compact) is called a Littlewood identity. In this thesis, I study many recent Littlewood identities of Rains and Warnaar. My own contributions include a proof of an extension of one of their identities and partial progress towards generalization of one another
49
Lecerf, Grégoire. "Une alternative aux methodes de reecriture pour la resolution des systemes algebriques." Palaiseau, Ecole polytechnique, 2001. http://www.theses.fr/2001EPXX0018.
Full textAbstract:
Introduite par h. Hironaka au milieu des annees 1960, la notion de base standard d'un ideal dans un anneau de polynomes connait depuis les travaux de b. Buchberger un engouement particulier en mathematiques et informatique. La construction effective d'une telle base est desormais une fonctionnalite essentielle dans tous les logiciels de calcul formel. Les algorithmes sous-jacents sont sans cesse ameliores et permettent de traiter des problemes concrets inaccessibles aux methodes numeriques. Et pourtant la complexite de ces algorithmes est doublement exponentielle dans le pire des cas. Dans les annees 1990, m. Giusti et j. Heintz montrent que les problemes d'elimination peuvent etre ramenes dans une classe polynomiale en representant les polynomes eliminant par des calculs d'evaluation. Sur la base de leurs travaux, ma these aboutit a un algorithme probabiliste de calcul de la decomposition en composantes equidimensionnelles de l'ensemble des solutions d'un systeme d'equations et d'inequations polynomiales. Sa complexite est polynomiale en un degre intrinseque, de nature geometrique. Implante dans le systeme de calcul formel magma et appele kronecker en hommage a l'illustre mathematicien pour ses travaux sur l'elimination, notre paquetage affiche des performances qui sont a la hauteur des meilleurs implantations dans le langage c de calcul de bases standard.
50
Lebreton, Romain. "Contributions à l'algorithmique détendue et à la résolution des systèmes polynomiaux." Phd thesis, Ecole Polytechnique X, 2012. http://tel.archives-ouvertes.fr/tel-00780618.
Full textAbstract:
Cette thèse est en majeure partie dédiée au calcul rapide de remontée p-adique par des algorithmes détendus. Dans une première partie, nous présentons le cadre général des algorithmes détendus et de leur application au calcul de p-adiques récursifs. Pour appliquer ce cadre à la remontée p-adique de divers systèmes d'équations, il reste à transformer ces équations implicites en équations récursives. Ainsi, la seconde partie traite des systèmes d'équations linéaires, éventuellement différentiels. La remontée de résolutions de systèmes polynomiaux se trouve en troisième partie. Dans tous les cas, les nouveaux algorithmes détendus sont comparés, en théorie comme en pratique, aux algorithmes existants. En quatrième partie, nous étudions l'algèbre de décomposition universelle d'un polynôme. Nous développons un algorithme rapide pour calculer une représentation adéquate de cette algèbre et l'utilisons pour manipuler efficacement les éléments de l'algèbre. Finalement, nous montrons en annexe que la recherche d'invariants fondamentaux d'algèbres d'invariants sous un groupe fini peut se faire directement modulo p, facilitant ainsi leur calcul.