Добірка наукової літератури з теми "Circuits algébriques"

On s'intéresse dans cette thèse à des systèmes différentiels implicites où les inconnues et leurs dérivées sont liées algébriquement. L'objet du présent travail est l'étude d'extensions de la méthode de Relaxation d'Onde, incluant des variantes asynchrones. On élabore donc des méthodes asynchrones pour le traitement des équations différentielles algébriques avec valeurs initiales. Le début de cette thèse est consacré à la modélisation et à l'étude du comportement des méthodes itératives de point fixe appliquées à ces systèmes. On s'intéresse, ensuite, plus particulièrement à l'extension au cadre asynchrone de la méthode de Relaxation d'Onde, en établissant un résultat général de couplage des inconnues par le biais d'une application de point fixe plus implicite. On donne quelques exemples appartenant aux classes de problèmes traités, on discrétise nos systèmes par des méthodes de Runge-Kutta et on étudie les problèmes discrets associés. Après avoir étudié les erreurs d'arrondi dues à la mise en œuvre sur ordinateur, on réalise une simulation d'exécution d'algorithmes asynchrones et on traite quelques exemples issus de problèmes de circuits électriques.

La thèse porte sur l'étude de la stabilité transitoire des systèmes de puissance soumis à de fortes perturbations. On s'intéresse au problème d'élargissement du domaine d'attraction du point d'équilibre du réseau électrique. Pour décrire le comportement du réseau, nous considérons une modélisation réaliste qui conserve l'identité de chaque composant et permet un traitement plus réaliste des charges. Cette modélisation se décrit par des équations algébriques différentielles qui se dérivent du principe de conservation d'énergie entre les différents composants. Nous proposons une solution explicite de ces équations, tout en imposant une hypothèse que les charges soient à impédance constante. Après avoir résolu ces équations, nous construisons une loi de commande non linéaire stabilisante. Cette dernière assure que toutes les trajectoires convergent au point d'équilibre désiré. Afin de prouver l'efficacité de ce contrôleur, plusieurs simulations ont été réalisées sur différents réseaux. Ces simulations montrent que le contrôleur est capable d'élargir le domaine d'attraction autour du point d'équilibre stable. Comme la plupart des études rapportées par la communauté de la théorie de commande sur le problème de la stabilité transitoire du réseau multimachine, il est clair que la complexité du contrôleur proposé fait obstacle à l'application pratique de ce résultat. Ce travail est important pour la recherche fondamentale. Sur un plan plus pratique, nous proposons une famille de modèles réduits pour le réseau multimachine et construisons une nouvelle loi de commande stabilisante, où la formulation du problème de contrôle est adaptée à des exigences pratiques
This thesis is devoted to the problem of enlarging the region of attraction of equilibria in power systems. We focus our attention on multimachine power systems subjected to a severe 3-phase short circuit fault and propose a new energy based control law for excitation control of synchronous generators. Furthermore, in contrast with aggregated models used in the classical research of transient stability to describe the dynamic behavior of multimachine power systems, we consider in this work the more natural; and widely popular structure preserving models that preserve the identity of the network components and allow for a more realistic treatment of the loads. These models consist of differential algebraic equations, where the algebraic constraints stem from the power flow balance between generators, loads, and lines. Our first contribution is the explicit computation of a solution for these equations. Moreover, we explicitly calculate a control law that, under a detectability assumption, ensures that all trajectories converge to the desired equilibrium point. However, similarly to most developments reported by the control theory community on the transient stability problem, it is clear that the complexity of the proposed controller stymies the practical application of this result. On a more practical level, we propose: first, a family of reduced models for multimachine power systems using the method of moment for nonlinear systems. Secondly, using the immersion and invariance methodology, we construct a new stabilizing control law for the power systems, where the formulation of the control problem is adjusted to meet the practical transient stability requirement

Cette thèse s'intéresse à la simulation temps-réel de circuit audio nonlinéaires. Dans cette thèse, nous utilisons le formalisme des systèmes Hamiltoniens à ports (SHP) pour garantir le bilan de puissance et la passivité. De plus, nous adoptons un cadre fonctionnel à temps continu pour représenter des signaux "analogiques virtuels" et nous proposons d'approximer les solutions par projection sur des trames temporelles. En tant que résultat principal, nous établissons une condition suffisante sur les projecteurs de sorte à obtenir des trajectoires à bilan de puissance garanti. Notre but est double: premièrement, pour gérer l'expansion de bande-passante causée par les nonlinéarités, nous considérons des méthodes numériques traitant des signaux à bande non-limitée qui à la place ont un "taux d'innovation borné"; Deuxièmement, pour revenir dans le domaine des signaux à bande limitée, nous concevons des "convertisseurs analogique-numérique virtuels" Plusieurs méthodes numériques sont construites afin d'être à bilan de puissance garanti, avec une précision d'ordre élevé et un un ordre de régularité contrôlable. Leurs propriétés sont étudiées: existence et unicité, ordre de précision, dispersion, mais aussi, résolution fréquentielle au delà de la fréquence de Nyquist, rejet du repliement ainsi que noyaux reproduisants et noyaux de Peano. Cette approche révèle des ponts entre l'analyse numérique, le traitement du signal et la théorie de l'échantillonnage généralisé en mettant en relation la précision, la propriété de reproduction des polynômes, la bande passante ou les bancs de filtre de Legendre, etc. Nous exposons un cadre systématique pour transformer des schémas électronique en équations puis en simulations. Ce cadre est ensuite appliqué à des circuits audio représentatifs, contenant à la fois des équations différentielles ordinaires et des équation algebro-différentielles. Un travail spécifique est dédié à la modélisation SHP des amplificateurs opérationnels. Enfin, nous revisitons la modélisation des SHP dans le cadre de l'algèbre géométrique, ce qui ouvre des perspectives pour l'encodage de la structure géométrique des équations
This work addresses the real-time simulation of nonlinear audio circuits. In this thesis, we use the port-Hamiltonian (pH) formalism to guarantee power balance and passivity. Moreover, we adopt a continuous-time functional framework to represent "virtual analog" signals and propose to approximate solutions by projection over time frames. As a main result, we establish a sufficient condition on projectors to obtain time-continuous power-balanced trajectories. Our goal is twofold: first, to manage frequency-bandwidth expansion due to nonlinearities, we consider numerical engines processing signals that are not bandlimited but, instead, have a "finite rate of innovation"; second, to get back to the bandlimited domain, we design "virtual analog-to-digital converters". Several numerical methods are built to be power-balanced, high-order accurate, with a controllable regularity order. Their properties are studied: existence and uniqueness, accuracy order and dispersion, but also, frequency resolution beyond the Nyquist frequency, aliasing rejection, reproducing and Peano kernels. This approach reveals bridges between numerical analysis, signal processing and generalised sampling theory, by relating accuracy, polynomial reproduction, bandwidth, Legendre filterbanks, etc. A systematic framework to transform schematics into equations and simulations is detailed. It is applied to representative audio circuits (for the UVI company), featuring both ordinary and differential-algebraic equations. Special work is devoted to pH modelling of operational amplifiers. Finally, we revisit pH modelling within the framework of Geometric Algebra, opening perspectives for structure encoding

Nous allons étudier les propriétés des courbes algébriques sur des surfaces K3 spéciales, du point de vue de la théorie de Brill-Noether.La démonstration de Lazarsfeld du théorème de Gieseker-Petri a mis en lumière l'importance de la théorie de Brill-Noether des courbes admettant un plongement dans une surface K3. Nous allons donner une démonstration détaillée de ce résultat classique, inspirée par les idées de Pareschi. En suite, nous allons décrire le théorème de Green et Lazarsfeld, fondamental pour tout notre travail, qui établit le comportement de l'indice de Clifford des courbes sur les surfaces K3.Watanabe a montré que l'indice de Clifford de courbes sur certaines surfaces K3, admettant un recouvrement double des surfaces de del Pezzo, est calculé en utilisant les involutions non-symplectiques. Nous étudions une situation similaire pour des surfaces K3 avec un réseau de Picard isomorphe à U(m), avec m>0 un entier quelconque. Nous montrons que la gonalité et l'indice de Clifford de toute courbe lisse sur ces surfaces, avec une seule exception déterminée explicitement, sont obtenus par restriction des fibrations elliptiques de la surface. Ce travail est basé sur l'article suivant :M. Ramponi, Gonality and Clifford index of curves on elliptic K3 surfaces with Picard number two, Archiv der Mathematik, 106(4), p. 355–362, 2016.Knutsen et Lopez ont étudié en détail la théorie de Brill-Noether des courbes sur les surfaces d'Enriques. En appliquant leurs résultats, nous allons pouvoir calculer la gonalité et l'indice de Clifford de toute courbe lisse sur les surfaces K3 qui sont des recouvrements universels d'une surface d'Enriques. Ce travail est basé sur l'article suivant :M. Ramponi, Special divisors on curves on K3 surfaces carrying an Enriques involution, Manuscripta Mathematica, 153(1), p. 315–322, 2017
We study the properties of algebraic curves lying on special K3 surfaces, from the viewpoint of Brill-Noether theory.Lazarsfeld's proof of the Gieseker-Petri theorem has revealed the importance of the Brill-Noether theory of curves which admit an embedding in a K3 surface. We give a proof of this classical result, inspired by the ideas of Pareschi. We then describe the theorem of Green and Lazarsfeld, a key result for our work, which establishes the behaviour of the Clifford index of curves on K3 surfaces.Watanabe showed that the Clifford index of curves lying on certain special K3 surfaces, realizable as a double covering of a smooth del Pezzo surface, can be determined by a direct use of the non-simplectic involution carried by these surfaces. We study a similar situation for some K3 surfaces having a Picard lattice isomorphic to U(m), with m>0 any integer. We show that the gonality and the Clifford index of all smooth curves on these surfaces, with a single, explicitly determined exception, are obtained by restriction of the elliptic fibrations of the surface. This work is based on the following article:M. Ramponi, Gonality and Clifford index of curves on elliptic K3 surfaces with Picard number two, Archiv der Mathematik, 106(4), p. 355-362, 2016.Knutsen and Lopez have studied in detail the Brill-Noether theory of curves lying on Enriques surfaces. Applying their results, we are able to determine and compute the gonality and Clifford index of any smooth curve lying on the general K3 surface which is the universal covering of an Enriques surface. This work is based on the following article:M. Ramponi, Special divisors on curves on K3 surfaces carrying an Enriques involution, Manuscripta Mathematica, 153(1), p. 315-322, 2017

Cette thèse propose des méthodes de synthèse dédiées aux circuits intégrés complexes. Elle concerne l'étape de factorisation algébrique dont le but est de réduire la complexité des expressions booléennes évaluées en terme de littéraux. Les méthodes classiques proposées généralement, amènent une bonne minimisation de la surface active mais peuvent entrainer un mauvais contrôle de la connectique. Cette thèse présente d'abord un état de l'art critique sur les techniques de factorisation algébrique poussées incluant les techniques dites booléennes. Dans les chapitres suivants, deux approches alternatives de factorisation plus restreintes sont proposées. La première est réduite a une division par conoyaux et la deuxième concerne une factorisation dite lexicographique encore plus restrictive, dont le but est de préparer une connectique simplifiée. Les résultats expérimentaux ont permis de définir à partir de quel seuil de complexité, il convient d'appliquer ces deux méthodes pour obtenir une bonne surface globale ainsi qu'un bon facteur de routage

Les modèles polynomiaux sont omniprésents en informatique, dans l'étude des automates et des langages formels, de l'optimisation, de la théorie des jeux, de la théorie du contrôle et de nombreux autres domaines. Dans cette thèse, nous considérons des modèles décrits par des systèmes d'équations polynomiales et des équations différentielles, où le système évolue à travers un ensemble discret de pas de temps avec des mises à jour polynomiales à chaque pas. Nous explorons trois aspects des « problèmes de zéros » pour les modèles polynomiaux : le test d'identité pour les expressions algébriques données par des polynômes, la détermination de l'existence de racines pour les systèmes polynomiaux et la détermination de l'existence de zéros dans les suites satisfaisant des récurrences à coefficients polynomiaux. Dans la première partie, nous étudions les tests d'identité pour les expressions algébriques impliquant des radicaux. En d'autres termes, étant donné un polynôme à k variables représenté par un circuit algébrique et k radicaux réels, nous examinons la complexité de déterminer si le polynôme s'annule sur l'entrée. Nous améliorons la borne PSPACE existante, en plaçant le problème dans coNP en supposant l'hypothèse de Riemann généralisée (HRG). Nous considérons ensuite une version restreinte du problème, où les entrées sont des racines carrées de nombres premiers impairs, montrant qu'il peut être résolu en temps polynomial randomisé en supposant HRG. Nous considérons ensuite les systèmes d'équations polynomiales et étudions la complexité de déterminer si un système de polynômes à coefficients polynomials a une solution. Nous présentons une approche du problème basée sur la théorie des nombres, généralisant les techniques utilisées pour les tests d'identité, et montrons que le problème appartient à la classe de complexité AM en supposant HRG. Nous analysons le lien entre ce problème et le problème de la détermination de la dimension d'une variété complexe, dont l'appartenance à AM a déjà été prouvé supposant HRG. Dans la dernière partie de cette thèse, nous analysons les suites satisfaisant des récurrences à coefficients polynomiaux. Nous étudions la question de savoir si zéro appartient d'une suite récursive polynomiale résultant d'une somme de deux suites hypergéométriques. Plus précisément, nous considérons le problème pour les suites dont les coefficients polynomiaux se décomposent dans le corps des rationnels Q. Nous montrons sa relation avec les valeurs de la fonction Gamma évaluées en des points rationnels, ce qui permet d'établir la décidabilité du problème supposant la conjecture de Rohrlich-Lang. Nous proposons une nouvelle approche basée sur l'étude des diviseurs premiers de la suite, ce qui nous permet d'établir la décidabilité inconditionnelle du problème
Polynomial models are ubiquitous in computer science, arising in the study of automata and formal languages, optimisation, game theory, control theory, and numerous other areas. In this thesis, we consider models described by polynomial systems of equations and difference equations, where the system evolves through a set of discrete time steps with polynomial updates at every step. We explore three aspects of "zero problems" for polynomial models: zero testing for algebraic expressions given by polynomials, determining the existence of zeros for polynomial systems and determining the existence of zeros for sequences satisfying recurrences with polynomial coefficients. In the first part, we study identity testing for algebraic expressions involving radicals. That is, given a k-variate polynomial represented by an algebraic circuit and k real radicals, we examine the complexity of determining whether the polynomial vanishes on the radical input. We improve on the existing PSPACE bound, placing the problem in coNP assuming the Generalised Riemann Hypothesis (GRH). We further consider a restricted version of the problem, where the inputs are square roots of odd primes, showing that it can be decided in randomised polynomial time assuming GRH. We next consider systems of polynomial equations, and study the complexity of determining whether a system of polynomials with polynomial coefficients has a solution. We present a number-theoretic approach to the problem, generalising techniques used for identity testing, showing the problem belongs to the complexity class AM assuming GRH. We discuss how the problem relates to determining the dimension of a complex variety, which is also known to belong to AM assuming GRH. In the final part of this thesis, we turn our attention to sequences satisfying recurrences with polynomial coefficients. We study the question of whether zero is a member of a polynomially recursive sequence arising as a sum of two hypergeometric sequences. More specifically, we consider the problem for sequences where the polynomial coefficients split over the field of rationals Q. We show its relation to the values of the Gamma function evaluated at rational points, which allows to establish decidability of the problem under the assumption of the Rohrlich-Lang conjecture. We propose a different approach to the problem based on studying the prime divisors of the sequence, allowing us to establish unconditional decidability of the problem

La complexité arithmétique est l'étude des ressources nécessaires pour calcu- ler des polynômes en n'utilisant que des opérations arithmétiques. À la fin des années 70, Valiant a défini (de manière semblable à la complexité booléenne) des classes de polynômes. Les polynômes, ayant des circuits de taille polyno- miale, considérés faciles forment la classe VP. Les sommes exponentielles de ces derniers correpondent alors à la classe VNP. L'hypothèse de Valiant est la conjecture que VP ̸= VNP.Bien que cette conjecture soit encore grandement ouverture, cette dernière semble toutefois plus accessible que son homologue booléen. La structure algé- brique sous-jacente limite les possibilités de calculs. En particulier, un résultat important du domaine assure que les polynômes faciles peuvent aussi être cal- culés efficacement en paralèlle. De plus, quitte à autoriser une augmentation raisonnable de la taille, il est possible de les calculer avec une profondeur de calcul bornée par une constante. Comme ce dernier modèle est très restreint, de nombreuses bornes inférieures sont connues. Nous nous intéresserons en premier temps à ces résultats sur les circuits de profondeur constante.Bürgisser a montré qu'une conjecture (la τ-conjecture) qui borne supérieu- rement le nombre de racines de certains polynômes univariés, impliquait des bornes inférieures en complexité arithmétique. Mais, que se passe-t-il alors, si on essaye de réduire, comme précédemment, la profondeur du polynôme consi- déré? Borner le nombre de racines réelles de certaines familles de polynômes permetterait de séparer VP et VNP. Nous étudierons finalement ces bornes su- périeures sur le nombre de racines réelles.

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 incompressibles
This 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

Valiant définit des analogues algébriques des classes P et NP. Nous caractérisons les classes VP et VQP, d'où une preuve simplifiée de VNP = VNPe et de la VQP-complétude du déterminant, et la preuve d'une conjecture de Bürgisser. Les classes VPo et VNPo, définies sans constantes arbitraires, donnent facilement un lien entre la complexité d'un polynôme et celle de sa fonction coefficient: VNPo est stable par passage à la fonction coefficient et réciproquement; supposer ce résultat pour VPo est équivalent à VPo = VNPo. Pour traiter le cas du degré non borné, il faut un calcul rapide des coefficients binomiaux, faisable en caractéristique positive et peu probable en caractéristique 0. Nous étudions enfin un problème lié: l'effet de la dérivation sur la complexité. Nous retrouvons le résultat de Kaltofen (le nombre de variables fait exploser la taille plus que l'ordre de dérivation) et donnons un calcul simultané des dérivées partielles.

La complexité algorithmique est l'étude des ressources nécessaires -- le temps, la mémoire, ... -- pour résoudre un problème de manière algorithmique. Dans ce cadre, la théorie de la complexité algébrique est l'étude de la complexité algorithmique de problèmes de nature algébrique, concernant des polynômes.Dans cette thèse, nous étudions différents aspects de la complexité algébrique. D'une part, nous nous intéressons à l'expressivité des déterminants de matrices comme représentations des polynômes dans le modèle de complexité de Valiant. Nous montrons que les matrices symétriques ont la même expressivité que les matrices quelconques dès que la caractéristique du corps est différente de deux, mais que ce n'est plus le cas en caractéristique deux. Nous construisons également la représentation la plus compacte connue du permanent par un déterminant. D'autre part, nous étudions la complexité algorithmique de problèmes algébriques. Nous montrons que la détection de racines dans un système de n polynômes homogènes à n variables est NP-difficile. En lien avec la question " VP = VNP ? ", version algébrique de " P = NP ? ", nous obtenons une borne inférieure pour le calcul du permanent d'une matrice par un circuit arithmétique, et nous exhibons des liens unissant ce problème et celui du test d'identité polynomiale. Enfin nous fournissons des algorithmes efficaces pour la factorisation des polynômes lacunaires à deux variables.