To see the other types of publications on this topic, follow the link: Algebraic Circuits.
Dissertations / Theses on the topic 'Algebraic Circuits'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 48 dissertations / theses for your research on the topic 'Algebraic Circuits.'
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
König, Daniel [Verfasser]. "Parallel evaluation of algebraic circuits / Daniel König." Siegen : Universitätsbibliothek der Universität Siegen, 2017. http://d-nb.info/1138836931/34.
Full text
2
Pade, Jonas. "Analysis and waveform relaxation for a differential-algebraic electrical circuit model." Doctoral thesis, Humboldt-Universität zu Berlin, 2021. http://dx.doi.org/10.18452/23044.
Full textAbstract:
Die Hauptthemen dieser Arbeit sind einerseits eine tiefgehende Analyse von nichtlinearen differential-algebraischen Gleichungen (DAEs) vom Index 2, die aus der modifizierten Knotenanalyse (MNA) von elektrischen Schaltkreisen hervorgehen, und andererseits die Entwicklung von Konvergenzkriterien für Waveform Relaxationsmethoden zum Lösen gekoppelter Probleme. Ein Schwerpunkt in beiden genannten Themen ist die Beziehung zwischen der Topologie eines Schaltkreises und mathematischen Eigenschaften der zugehörigen DAE.
Der Analyse-Teil umfasst eine detaillierte Beschreibung einer Normalform für Schaltkreis DAEs vom Index 2 und Abschätzungen, die für die Sensitivität des Schaltkreises bezüglich seiner Input-Quellen folgen. Es wird gezeigt, wie diese Abschätzungen wesentlich von der topologischen Position der Input-Quellen im Schaltkreis abhängen.
Die zunehmend komplexen Schaltkreise in technologischen Geräten erfordern oftmals eine Modellierung als gekoppeltes System. Waveform relaxation (WR) empfiehlt sich zur Lösung solch gekoppelter Probleme, da sie auf die Subprobleme angepasste Lösungsmethoden und Schrittweiten ermöglicht. Es ist bekannt, dass WR zwar bei Anwendung auf gewöhnliche Differentialgleichungen konvergiert, falls diese eine Lipschitz-Bedingung erfüllen, selbiges jedoch bei DAEs nicht ohne Hinzunahme eines Kontraktivitätskriteriums sichergestellt werden kann. Wir beschreiben allgemeine Konvergenzkriterien für WR auf DAEs vom Index 2. Für den Fall von Schaltkreisen, die entweder mit anderen Schaltkreisen oder mit elektromagnetischen Feldern verkoppelt sind, leiten wir außerdem hinreichende topologische Konvergenzkriterien her, die anhand von Beispielen veranschaulicht werden. Weiterhin werden die Konvergenzraten des Jacobi WR Verfahrens und des Gauss-Seidel WR Verfahrens verglichen. Simulationen von einfachen Beispielsystemen zeigen drastische Unterschiede des WR-Konvergenzverhaltens, abhängig davon, ob die Konvergenzbedingungen erfüllt sind oder nicht.The main topics of this thesis are firstly a thorough analysis of nonlinear differential-algebraic equations (DAEs) of index 2 which arise from the modified nodal analysis (MNA) for electrical circuits and secondly the derivation of convergence criteria for waveform relaxation (WR) methods on coupled problems. In both topics, a particular focus is put on the relations between a circuit's topology and the mathematical properties of the corresponding DAE. The analysis encompasses a detailed description of a normal form for circuit DAEs of index 2 and consequences for the sensitivity of the circuit with respect to its input source terms. More precisely, we provide bounds which describe how strongly changes in the input sources of the circuit affect its behaviour. Crucial constants in these bounds are determined in terms of the topological position of the input sources in the circuit. The increasingly complex electrical circuits in technological devices often call for coupled systems modelling. Allowing for each subsystem to be solved by dedicated numerical solvers and time scales, WR is an adequate method in this setting. It is well-known that while WR converges on ordinary differential equations if a Lipschitz condition is satisfied, an additional convergence criterion is required to guarantee convergence on DAEs. We present general convergence criteria for WR on higher index DAEs. Furthermore, based on our results of the analysis part, we derive topological convergence criteria for coupled circuit/circuit problems and field/circuit problems. Examples illustrate how to practically check if the criteria are satisfied. If a sufficient convergence criterion holds, we specify at which rate of convergence the Jacobi and Gauss-Seidel WR methods converge. Simulations of simple benchmark systems illustrate the drastically different convergence behaviour of WR depending on whether or not the circuit topological convergence conditions are satisfied.
3
Tavenas, Sébastien. "Bornes inférieures et supérieures dans les circuits arithmétiques." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2014. http://tel.archives-ouvertes.fr/tel-01066752.
Full textAbstract:
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.
4
Jain, Divyanshu. "MVHAM an extension of the homotopy analysis method for improving convergence of the multivariate solution of nonlinear algebraic equations as typically encountered in analog circuits /." Cincinnati, Ohio : University of Cincinnati, 2007. http://www.ohiolink.edu/etd/view.cgi?acc%5Fnum=ucin1194974755.
Full textAbstract:
Thesis (M.S.)--University of Cincinnati, 2007.Advisor: Harold W. Carter. Title from electronic thesis title page (viewed Feb. 18, 2008). Includes abstract. Keywords: Homotopy Analysis Method; Solution of Nonlinear Algebraic Equations; Convergence. Includes bibliographical references.
5
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
6
Remscrim, Zachary (Zachary N. ). "Algebraic methods in pseudorandomness and circuit complexity." Thesis, Massachusetts Institute of Technology, 2016. http://hdl.handle.net/1721.1/106089.
Full textAbstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 93-96).
In this thesis, we apply tools from algebra and algebraic geometry to prove new results concerning extractors for algebraic sets, AC⁰-pseudorandomness, the recursive Fourier sampling problem, and VC dimension. We present a new construction of an extractor which works for algebraic sets defined by polynomials over F₂ of substantially higher degree than the previous state-of-the-art construction. We exhibit a collection of natural functions that behave pseudorandomly with regards to AC⁰ tests. We also exactly determine the F₂-polynomial degree of the recursive Fourier sampling problem and use this to provide new partial results towards a circuit lower bound for this problem. Finally, we answer a question posed in [MR15] concerning VC dimension, interpolation degree and the Hilbert function.
by Zachary Remscrim.
Ph. D.
7
Ramponi, Marco. "Clifford index and gonality of curves on special K3 surfaces." Thesis, Poitiers, 2017. http://www.theses.fr/2017POIT2317/document.
Full textAbstract:
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, 2017We 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
8
Reich, Sebastian. "Differential-algebraic equations and applications in circuit theory." Universität Potsdam, 1992. http://opus.kobv.de/ubp/volltexte/2010/4664/.
Full textAbstract:
Technical and physical systems, especially electronic circuits, are frequently modeled as a system of differential and nonlinear implicit equations. In the literature such systems of equations are called differentialalgebraic equations (DAEs). It turns out that the numerical and analytical properties of a DAE depend on an integer called the index of the problem. For example, the well-known BDF method of Gear can be applied, in general, to a DAE only if the index does not exceed one. In this paper we give a geometric interpretation of higherindex DAEs and indicate problems arising in connection with such DAEs by means of several examples.Die mathematische Modellierung technisch physikalischer Systeme wie elektrische Netzwerke, führt häufig auf ein System von Differentialgleichungen und nichtlinearen impliziten Gleichungen sogenannten Algebrodifferentialgleichungen (ADGL). Es zeigt sich, daß die numerischen und analytischen Eigenschaften von ADGL durch den Index des Problems charakterisiert werden können. Insbesondere können die bekannten Integrationsformeln von Gear im allgemeinen nur auf ADGL mit dem Index eins angewendet werden. In diesem Beitrag wird eine geometrische Interpretation von ADGL mit einem höheren Index gegeben sowie auf Probleme im Zusammenhang mit derartigen ADGL an Hand verschiedener Beispiele hingewiesen.
9
Bächle, Simone. "Numerical solution of differential-algebraic systems arising in circuit simulation." [S.l.] : [s.n.], 2007. http://opus.kobv.de/tuberlin/volltexte/2007/1524.
Full text
10
Grenet, Bruno. "Représentations des polynômes, algorithmes et bornes inférieures." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2012. http://tel.archives-ouvertes.fr/tel-00770148.
Full textAbstract:
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.
11
Strohm, Christian. "Circuit Simulation Including Full-Wave Maxwell's Equations." Doctoral thesis, Humboldt-Universität zu Berlin, 2021. http://dx.doi.org/10.18452/22544.
Full textAbstract:
Diese Arbeit widmet sich der Simulation von elektrischen/elektronischen Schaltungen welche um elektromagnetische Bauelemente erweitert werden. Im Fokus stehen unterschiedliche Kopplungen der Schaltungsgleichungen, modelliert mit der modifizierten Knotenanalyse, und den elektromagnetischen Bauelementen mit deren verfeinerten Modell basierend auf den vollen Maxwell-Gleichungen in der Lorenz-geeichten A-V Formulierung welche durch Finite-Integrations-Technik räumlich diskretisiert werden. Eine numerische Analyse erweitert die topologischen Kriterien für den Index der resultierenden differential-algebraischen Gleichungen, wie sie bereits in anderen Arbeiten mit ähnlichen Feld/Schaltkreis-Kopplungen hergeleitet wurden. Für die Simulation werden sowohl ein monolithischer Ansatz als auch Waveform-Relaxationsmethoden untersucht. Im Mittelpunkt stehen dabei Zeitintegration, Skalierungsmethoden, strukturelle Eigenschaften und ein hybride Ansatz zur Lösung der zugrundeliegenden linearen Gleichungssysteme welcher den Einsatz spezialisierter Löser für die jeweiligen Teilsysteme erlaubt. Da die vollen Maxwell-Gleichungen zusätzliche Ableitungen in der Kopplungsstruktur verursachen, sind bisher existierende Konvergenzaussagen für die Waveform-Relaxation von gekoppelten differential-algebraischen Gleichungen nicht anwendbar und motivieren eine neue Konvergenzanalyse. Auf dieser Analyse aufbauend werden hinreichende topologische Kriterien entwickelt, welche eine Konvergenz von Gauß-Seidel- und Jacobi-artigen Waveform-Relaxationen für die gekoppelten Systeme garantieren. Schließlich werden numerische Benchmarks zur Verfügung gestellt, um die eingeführten Methoden und Theoreme dieser Abhandlung zu unterstützen.This work is devoted to the simulation of electrical/electronic circuits incorporating electromagnetic devices. The focus is on different couplings of the circuit equations, modeled with the modified nodal analysis, and the electromagnetic devices with their refined model based on full-wave Maxwell's equations in Lorenz gauged A-V formulation which are spatially discretized by the finite integration technique. A numerical analysis extends the topological criteria for the index of the resulting differential-algebraic equations, as already derived in other works with similar field/circuit couplings. For the simulation, both a monolithic approach and waveform relaxation methods are investigated. The focus is on time integration, scaling methods, structural properties and a hybrid approach to solve the underlying linear systems of equations with the use of specialized solvers for the respective subsystems. Since the full-Maxwell approach causes additional derivatives in the coupling structure, previously existing convergence statements for the waveform relaxation of coupled differential-algebraic equations are not applicable and motivate a new convergence analysis. Based on this analysis, sufficient topological criteria are developed which guarantee convergence of Gauss-Seidel and Jacobi type waveform relaxation schemes for introduced coupled systems. Finally, numerical benchmarks are provided to support the introduced methods and theorems of this treatise.
12
Pade, Jonas [Verfasser]. "Analysis and waveform relaxation for a differential-algebraic electrical circuit model / Jonas Pade." Berlin : Humboldt-Universität zu Berlin, 2021. http://d-nb.info/1237685346/34.
Full text
13
Nosan, Klara. "Zero problems in polynomial models." Electronic Thesis or Diss., Université Paris Cité, 2024. http://www.theses.fr/2024UNIP7008.
Full textAbstract:
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èmePolynomial 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
14
Estévez, Schwarz Diana. "Consistent initialization for index-2 differential algebraic equations and its application to circuit simulation." [S.l. : s.n.], 2000. http://deposit.ddb.de/cgi-bin/dokserv?idn=960337202.
Full text
15
Schwarz, Diana Estévez. "Consistent initialization for index-2 differential algebraic equations and its application to circuit simulation." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, 2000. http://dx.doi.org/10.18452/14512.
Full textAbstract:
Zur numerischen L\"osung von Algebro-Differentialgleichungen (ADGln) m\"ussen konsistente Anfangswerte berechnet werden. Diese Arbeit befasst sich mit einem Ansatz zur Behandlung dieses Problems f\"ur Index-2 DAEs unter Verwendung von Projektoren auf die zur DAE zugeh\"origen Unterr\"aume. Die Arbeit hat zwei Schwerpunkte.\\ Zum einen werden neue Struktureigenschaften aus schwachen Voraussetzungen hergeleitet. Anschlie{\ss}end wird eine Vorgehensweise zur Auswahl von geeigneten Gleichungen einer Index-2 ADGln vorgeschlagen, deren Differentiation zu einer Indexreduktion f\"uhrt. Diese Indexreduktion liefert neue Existenz- und Eindeutigkeitsergebnisse f\"ur L\"osungen von Index-2 ADGln. Die Ergebnisse umfassen eine allgemeinere Aufgabenklasse als die bisherigen Resultate. Beruhend auf dieser Vorgehensweise wird ein stufenweiser Ansatz zur Berechnung konsistenter Anfangswerte hergeleitet. Auf diese Weise werden neue Einsichten hinsichtlich der Ausnutzung von Struktureigenschaften von Index-2 ADGln gewonnen. Insbesondere stellt sich heraus, dass im Vergleich zu Index-1 ADGln der zus\"atzliche Schritt oft in der L\"osung eines linearen Systems besteht. Die sich hieraus ergebenden numerischen Folgen werden f\"ur zwei in der Schaltungssimulation h\"aufig verwendete Verfahren, das implizite Eulerverfahren und die Trapezregel, erl\"autert. \\ Zum anderen wird die Anwendung der erhaltenen Ergebnisse auf die Gleichungen, die bei der Schaltungssimulation mittels modifizierter Knotenanalyse entstehen, ausgearbeitet. Abschlie{\ss}end wird eine kurze \"Ubersicht der durchgef\"uhrten Umsetzung gegeben.\\For solving DAEs numerically, consistent initial values have to be calculated. This thesis deals with an approach for handling this problem for index-2 DAEs by considering projectors onto the spaces related to the DAE. There are two major aspects in this work.\\ On the one hand, new structural properties are deduced from weak assumptions. Subsequently, a method is proposed to choose suitable equations of an index-2 DAE, whose differentiation leads to an index reduction. This index reduction yields new theoretical results for the existence and uniqueness of solutions of index-2 DAEs which apply to a wider class of applications than previous results. Based on this method, a step-by-step approach to compute consistent initial values is developed. In this way, we gain new insights about how to deal with structural properties of index-2 DAEs. In particular, it turns out that, in comparison to index-1 DAEs, the additional step that has to be undertaken in practice often consists in solving a linear system. The numerical consequences of this fact are exemplified for two methods commonly used in circuit simulation, the implicit Euler method and the trapezoidal rule.\\ On the other hand, the application of the obtained results to the equations arising in circuit simulation by means of the modified nodal analysis (MNA) is worked out. Finally, a short overview of the specifics of their realization is given.
16
Sengupta, Rimli. "Lower bounds for natural functions in restricted boolean circuits." Diss., Georgia Institute of Technology, 1995. http://hdl.handle.net/1853/8269.
Full text
17
Minárik, Michal. "Modelování elektrických obvodů s využitím diferenciálního počtu." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2010. http://www.nusl.cz/ntk/nusl-237269.
Full textAbstract:
This master's thesis deals with modeling of linear electrical circuits through the differential algebraical equation systems. It describes methods of numerical solving, discusses the need of algebraical conversions and possibility of minimalization through the use of parasitic components. In addition, it involves the design and implementation of extension of available simulation tool.
18
Hacker, Charles Hilton, and n/a. "WinLogiLab - A Computer-Based Teaching Suite for Digital Logic Design." Griffith University. School of Engineering, 2001. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20050915.172404.
Full textAbstract:
This thesis presents an interactive computerised teaching suite developed for the design of combinatorial and sequential logic circuits. This suite fills a perceived gap in the currently available computer-based teaching software for digital logic design. Several existing digital logic educational software are available, however these existing programs were found to be unsuitable for our use in providing alternative mode subject delivery. This prompted the development of a Microsoft Windows TM tutorial suite, called WinLogiLab. WinLogiLab comprises of a set of tutorials that uses student provided input data, to perform the initial design steps for digital Combinatorial and Sequential logic circuits. The combinatorial tutorials are designed to show the link between Boolean Algebra and Digital Logic circuits, and follows the initial design steps: from Boolean algebra, truth tables, to Exact and the Heuristic minimisation techniques, to finally produce the combinatorial circuit. Similarly, the sequential tutorials can design simple State Machine Counters, and can model more complex Finite State Automata.
19
Hacker, Charles. "WinLogiLab - A Computer-Based Teaching Suite for Digital Logic Design." Thesis, Griffith University, 2001. http://hdl.handle.net/10072/367209.
Full textAbstract:
This thesis presents an interactive computerised teaching suite developed for the design of combinatorial and sequential logic circuits. This suite fills a perceived gap in the currently available computer-based teaching software for digital logic design. Several existing digital logic educational software are available, however these existing programs were found to be unsuitable for our use in providing alternative mode subject delivery. This prompted the development of a Microsoft Windows TM tutorial suite, called WinLogiLab. WinLogiLab comprises of a set of tutorials that uses student provided input data, to perform the initial design steps for digital Combinatorial and Sequential logic circuits. The combinatorial tutorials are designed to show the link between Boolean Algebra and Digital Logic circuits, and follows the initial design steps: from Boolean algebra, truth tables, to Exact and the Heuristic minimisation techniques, to finally produce the combinatorial circuit. Similarly, the sequential tutorials can design simple State Machine Counters, and can model more complex Finite State Automata.Thesis (Masters)
Master of Philosophy (MPhil)
School of Engineering
Science, Environment, Engineering and Technology
Full Text
20
Bowen, Richard Strong. "Minimal Circuits for Very Incompletely Specified Boolean Functions." Scholarship @ Claremont, 2010. https://scholarship.claremont.edu/hmc_theses/18.
Full textAbstract:
In this report, asymptotic upper and lower bounds are given for the minimum number of gates required to compute a function which is only partially specified and for which we allow a certain amount of error. The upper and lower bounds match. Hence, the behavior of these minimum circuit sizes is completely (asymptotically) determined.
21
Serran, Nivaldo Vicençotto. "Circuitos digitais ternarios baseados na algebra de Post : estudo, definição de operadores e implememtação." [s.n.], 1996. http://repositorio.unicamp.br/jspui/handle/REPOSIP/260871.
Full textAbstract:
Orientador: Jose Antonio Siqueira DiasTese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação
Made available in DSpace on 2018-07-21T23:41:25Z (GMT). No. of bitstreams: 1 Serran_NivaldoVicencotto_D.pdf: 4785541 bytes, checksum: 38afdd0c1c1ffabfe505a5ab5c393a90 (MD5) Previous issue date: 1996
Resumo: Na lógica de múltiplos valores (MVL Multiple-Valued Logic), o número de níveis lógicos não está restrito a dois, como na lógica binária. Estas lógicas têm sido usadas para obter melhor aproveitamento da área dos chips, pois embora os componentes possam usar mais área, a quantidade de linhas de interconexão e pads de saída pode ser reduzida. Este trabalho descreve uma nova MVL baseada na Álgebra de Posto Juntamente com a negação cíclica de Post e a conjunção AND, são definidos novos operadores que permitem o desenvolvimento de algorítimos para a síntese e simplificação de funções lógicas. É proposta a implementação eletrônica para esta lógica em 3 níveis. Circuitos da negação de Post e dos novos operadores, são descritos e simulados, operando em modo de corrente. Estes circuitos podem ser interligados formando flip-flops, contadores, conversor D/A e outros circuitos lógicos. Esta lógica ternária, usando tecnologia bipolar em modo de corrente, pode ser útil para a construção de ASICS (circuitos dedicados) com alta velocidade de processamento
Abstract: In Multiple-Valued Logic (MVL), the logicallevels are not restricted to two, as in binary logic. These logics have been used to improve chip area. Although the components can need more area, the quantity of interconection lines and output pads can be reduced. This work describes a new non classical Multiple-Valued Logic(MVL) based on Post algebra. Besides the convencional Post 's cyclic negation and the AND conjunction, this logic algebra defines new operators which allow the development of algorithims for the synthesis and simplification of the logicalfunctions. An electronic implementation of this algebra for a 3-level logic is proposed Electronics gates of Post negation and the new operators were designed and simulated using current mode circuits. These gates can be easily interconnected toform flip-flops, counters, D/A converters and other conventional digital gates in a true 3-level gate logic. ASICS with mixed analogldigital high speed processing can benefit from this current processing ternary logic, which can be easily implemented in bipolar technology
Doutorado
Eletrônica, Microeletrônica e Optoeletrônica
Doutor em Engenharia Elétrica
22
Voigtmann, Steffen. "General linear methods for integrated circuit design." Doctoral thesis, Berlin Logos-Verl, 2006. http://deposit.d-nb.de/cgi-bin/dokserv?id=2850248&prov=M&dok_var=1&dok_ext=htm.
Full text
23
Braibant, Thomas. "Algèbres de Kleene, réécriture modulo AC et circuits en coq." Phd thesis, Université de Grenoble, 2012. http://tel.archives-ouvertes.fr/tel-00683661.
Full textAbstract:
Cette thèse décrit trois travaux de formalisation en Coq. Le premier chapitre s'intéresse à l'implémentation d'une procédure de décision efficace pour les algèbres de Kleene, pour lesquelles le modèle des langages réguliers est initial : il est possible de décider la théorie équationelle des algèbres de Kleene via la construction et la comparaison d'automates finis. Le second chapitre est consacré à la définition de tactiques pour la réécriture modulo associativité et commutativité en utilisant deux composants : une procédure de décision réflexive pour l'égalité modulo AC, ainsi qu'un greffon OCaml implémentant le filtrage modulo AC. Le dernier chapitre esquisse une formalisation des circuits digitaux via un plongement profond utilisant les types dépendants de Coq ; on s'intéresse ensuite à prouver la correction totale de circuits paramétriques.
24
Mejía, Ronald. "Fundamentos de lógica digital." Universidad Peruana de Ciencias Aplicadas - UPC, 2007. http://hdl.handle.net/10757/272760.
Full text
25
Vora, Rohit H. "An Algorithm for multi-output Boolean logic minimization." Thesis, Virginia Tech, 1987. http://hdl.handle.net/10919/43829.
Full textAbstract:
A new algorithm is presented for a guaranteed absolute minimal solution to the problem of Boolean Logic Minimization in its most generalized form of multi-output function with arbitrary cost criterion.
The proposed algorithm is shown to be tighter than the Quine-McCluskey method in its ability to eliminate redundant prime implicants, making it possible to simplify the cyclic tables. In its final form, the proposed algorithm is truly concurrent in generation of prime implicants and construction of minimal forms. A convenient and efficient technique is used for identifying existing prime implicants. Branch-and-bound method is employed to restrict the search tree to a cost cut-off value depending on the definition of cost function specified.
A most generalized statement of the algorithm is formulated for manual as well as computer implementation and its application is illustrated with an example. A program written in Pascal, for classical diode-gate cost function as well as PLA-area cost function, is developed and tested for an efficient computer implementation. Finally, various advantages of the proposed approach are pointed out by comparing it with the classical approach of Quine-McCluskey method.Master of Science
26
Cruvinel, Frederico Borges. "Tópicos de álgebra linear e aplicações em problemas de economia e de engenharia." Universidade Federal de Goiás, 2013. http://repositorio.bc.ufg.br/tede/handle/tde/2961.
Full textAbstract:
Submitted by Erika Demachki (erikademachki@gmail.com) on 2014-08-28T21:39:51Z
No. of bitstreams: 2
TCC APLICAÇÕES DE AL PROFMAT 2013.pdf: 455396 bytes, checksum: b39442c76a5d76a386c0794f86f1c9da (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)Made available in DSpace on 2014-08-28T21:39:51Z (GMT). No. of bitstreams: 2 TCC APLICAÇÕES DE AL PROFMAT 2013.pdf: 455396 bytes, checksum: b39442c76a5d76a386c0794f86f1c9da (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2013-04-12
This work shows the importance of the Linear Algebra and in particular of the theory of Matrices and Linear Systems to solve practical problems in various areas. We show examples of Applications of Linear Systems in closed and open models of Leontief in Economics, in closed circuits (Law Kirccho ) and in projects of construction of steel structures.
O presente trabalho mostra a importância da Álgebra Linear e em particular da teoria da Matrizes e Sistemas Lineares para resolver problemas práticos em diversas áreas. Mostramos exemplos de aplicações dos Sistemas Lineares nos modelos fechado e aberto de Leontief na área de Economia, em circuitos elétricos fechados (Lei de Kirccho ) e em projetos de construção de estruturas metálicas.
27
Fiszer, Robert Adrian. "Synthesis of Irreversible Incompletely Specified Multi-Output Functions to Reversible EOSOPS Circuits with PSE Gates." PDXScholar, 2014. https://pdxscholar.library.pdx.edu/open_access_etds/2109.
Full textAbstract:
As quantum computers edge closer to viability, it becomes necessary to create logic synthesis and minimization algorithms that take into account the particular aspects of quantum computers that differentiate them from classical computers. Since quantum computers can be functionally described as reversible computers with superposition and entanglement, both advances in reversible synthesis and increased utilization of superposition and entanglement in quantum algorithms will increase the power of quantum computing.
One necessary component of any practical quantum computer is the computation of irreversible functions. However, very little work has been done on algorithms that synthesize and minimize irreversible functions into a reversible form. In this thesis, we present and implement a pair of algorithms that extend the best published solution to these problems by taking advantage of Product-Sum EXOR (PSE) gates, the reversible generalization of inhibition gates, which we have introduced in previous work [1,2].
We show that these gates, combined with our novel synthesis algorithms, result in much lower quantum costs over a wide variety of functions as compared to our competitors, especially on incompletely specified functions. Furthermore, this solution has applications for milti-valued and multi-output functions.
28
Meredith, M. Brandon. "Polynomial Functions over Rings of Residue Classes of Integers." Digital Archive @ GSU, 2007. http://digitalarchive.gsu.edu/math_theses/34.
Full textAbstract:
In this thesis we discuss how to find equivalent representations of polynomial functions over the ring of integers modulo a power of a prime. Specifically, we look for lower degree representations and representations with fewer variables for which important applications in electrical and computer engineering exist. We present several algorithms for finding these compact formulations.
29
Costa, Ricardo Ferreira da. "A matemática e os circuitos elétricos de corrente contínua : uma abordagem analítica, prático-experimental e computacional." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2007. http://hdl.handle.net/10183/12535.
Full textAbstract:
Este trabalho trata do desenvolvimento de um material didático, sob a forma de cadernos (presentemente, em forma de capítulos), acompanhado de protótipo de circuito simples para testes experimentais, a ser utilizado no ensino de nível médio. O conteúdo reunido nos cadernos abrange o desenvolvimento analítico de tópicos pertinentes à física-matemática, esquema para a construção do protótipo e exemplos utilizando recursos computacionais. Mais especificamente, buscou-se enfatizar o ensino dos tópicos de equações e sistemas lineares, motivados por fenômenos físicos. Pretendeu-se explorar o aspecto experimental (com a construção e o uso de protótipo de circuitos simples), o analítico (com a resolução de equações e sistemas lineares, e com uma introdução à programação linear) e o computacional (com uso da planilha eletrônica). Em todos os conteúdos desenvolvidos, é dada especial ênfase à interpretação, à análise e à validação dos resultados. Com este material, procura-se oferecer ao professor um conjunto de atividades didático-pedagógicas, que possam estimular a sua atuação crítica e criativa. E que, também, propiciem a reflexão e a análise na identificação e resolução de problemas, a fim de desencadear processos cognitivos que levem o aluno a compreender as interrelações entre a física e a matemática.This paper is about the development of a didatic material, under the way of notebooks (here, in chapters), accompained by the prototype of simple circuit for experimental tests, to be used in high school teaching. The issue brought in the notebooks comprehends the analytic development of the topics that belong to the physics- mathematics, scheme for the building of the prototype and examples with the use of computer resources. More specifically, applied to the teaching of the topics of equations and linear systems, motivated by physics phenomena. It was intended to explore the experimental aspect (with the building of simple circuit prototype), the analytic (with the resolution of equations and linear systems, with an introduction to the linear programming) and the computer (with the use of electronic chart). In all the topics developed, a special emphasis is given to the interpretation, analysis and validating of the results. With this material, it was intended to offer the teacher a set of didatic- pedagogical activities that can stimulate the critical and creative acting. And that can also provide the thinking and analysis in the identification and resolution of problems, with the aim of triggering cognitive processes that lead the student to understand the inter-relations between physics and mathematics.
30
Soyez-Martin, Claire. "From semigroup theory to vectorization : recognizing regular languages." Electronic Thesis or Diss., Université de Lille (2022-....), 2023. http://www.theses.fr/2023ULILB052.
Full textAbstract:
L'évaluation efficace des expressions régulières constitue un défi persistant depuis de nombreuses décennies. Au fil du temps, des progrès substantiels ont été réalisés grâce à une variété d'approches, allant de nouveaux et ingénieux algorithmes à des optimisations complexes de bas niveau.Les outils de pointe de ce domaine utilisent ces techniques d'optimisation, et repoussent constamment les limites de leur efficacité. Une avancée notoire réside dans l'intégration de la vectorisation, qui exploite une forme de parallélisme de bas niveau pour traiter l'entrée par blocs, entraînant ainsi d'importantes améliorations de performances. Malgré une recherche approfondie sur la conception d'algorithmes sur mesure pour des tâches particulières, ces solutions manquent souvent de généralisabilité, car la méthodologie sous-jacente à ces algorithmes ne peut pas être appliquée de manière indiscriminée à n'importe quelle expression régulière, ce qui rend difficile son intégration dans les outils existants.Cette thèse présente un cadre théorique permettant de générer des programmes vectorisés particuliers capables d'évaluer les expressions régulières correspondant aux expressions rationnelles appartenant à une classe logique donnée. L'intérêt de ces programmes vectorisés vient de l'utilisation de la théorie algébrique des automates, qui offre certains outils algébriques permettant de traiter les lettres en parallèle. Ces outils permettent également d'analyser les langages réguliers plus finement, offrent accès à des optimisations des programmes vectorisés basées sur les propriétés algébriques de ces langages. Cette thèse apporte des contributions dans deux domaines. D'une part, nous présentons des implémentations et des benchmarks préliminaires, afin d'étudier les possibilités offertes par l'utilisation de l'algèbre et de la vectorisation dans les algorithmes d'évaluation des expressions régulières. D'autre part, nous proposons des algorithmes capables de générer des programmes vectorisés reconnaissant les langages appartenant à deux classes d'expressions rationnelles, la logique du premier ordre et sa restriction aux formules utilisant au plus deux variablesThe pursuit of optimizing regular expression validation has been a long-standing challenge,spanning several decades. Over time, substantial progress has been made through a vast range of approaches, spanning from ingenious new algorithms to intricate low-level optimizations.Cutting-edge tools have harnessed these optimization techniques to continually push the boundaries of efficient execution. One notable advancement is the integration of vectorization, a method that leverage low-level parallelism to process data in batches, resulting in significant performance enhancements. While there has been extensive research on designing handmade tailored algorithms for particular languages, these solutions often lack generalizability, as the underlying methodology cannot be applied indiscriminately to any regular expression, which makes it difficult to integrate to existing tools.This thesis provides a theoretical framework in which it is possible to generate vectorized programs for regular expressions corresponding to rational expressions in a given class. To do so, we rely on the algebraic theory of automata, which provides tools to process letters in parallel. These tools also allow for a deeper understanding of the underlying regular language, which gives access to some properties that are useful when producing vectorized algorithms. The contribution of this thesis is twofold. First, it provides implementations and preliminary benchmarks to study the potential efficiency of algorithms using algebra and vectorization. Second, it gives algorithms that construct vectorized programs for languages in specific classes of rational expressions, namely the first order logic and its subset restricted to two variables
31
Chakrapani, Lakshmi Narasimhan. "Probabilistic boolean logic, arithmetic and architectures." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/26706.
Full textAbstract:
Thesis (Ph.D)--Computing, Georgia Institute of Technology, 2009.Committee Chair: Palem, Krishna V.; Committee Member: Lim, Sung Kyu; Committee Member: Loh, Gabriel H.; Committee Member: Mudge, Trevor; Committee Member: Yalamanchili, Sudhakar. Part of the SMARTech Electronic Thesis and Dissertation Collection.
32
Laporte, Christophe. "Conception en technologie intégrée de circuits hyperfréquences pour la télémesure image d'un instrument spatial." Phd thesis, Université Paul Sabatier - Toulouse III, 1995. http://tel.archives-ouvertes.fr/tel-00144088.
Full textAbstract:
L'objectif de cette étude est la réalisation en technologie monolithique intégrée de circuits hyperfréquences pour la télémesure d'un instrument spatial. L'étude a plus particulièrement porté sur la conception d'oscillateurs à fréquences fixes et d'oscillateurs contrôlés en tension entièrement intégrés dans la bande de fréquence 8-8,4 GHz. Une nouvelle méthode de conception des oscillateurs hyperfréquences, basée sur le calcul analytique des conditions d'oscillations de l'oscillateur, est présentée. Le calcul formel est utilisé pour accéder au rôle de chacun des éléments du circuit ainsi qu'à leur sensibilité sur les performances électriques. Les résultats théoriques et expérimentaux sont en très bon accord et démontrent la faisabilité d'oscillateurs à fréquences fixes et d'oscillateurs contrôlés en tension à résonateurs intégrés sur une puce. Cette méthode est également appliquée avec succès pour la réalisation d'un oscillateur intégré à 2 GHz. Une autre partie du travail a porté sur la réalisation de modulateurs biphases et quadriphases monolithiques. Les résultats de mesure sont conformes aux simulations et répondent aux spécifications de la télémesure
33
Amoura, Aadil. "Synthese logique sur reseaux programmables de type FPGA et CPLD." Grenoble INPG, 1998. http://www.theses.fr/1998INPG0158.
Full textAbstract:
Cette these se situe dans le cadre de la synthese logique. L'objectif de ce travail est de resoudre des problemes fondamentaux de la synthese logique sur les reseaux programmables de type fpga et cpld, lies a la decomposition technologique et a la prediction temporelle sur ce type de boitiers. La premiere partie du travail s'interesse aux techniques de decomposition technologique permettant un ciblage heterogene sur les reseaux programmables de type fpga. Nous partons des techniques classiques, puis sont proposees des alternatives basees sur le principe de couverture des nuds et la decomposition de roth&karp. Nous presentons en outre des methodes de bi-decomposition booleenne en utilisant les operateurs logiques or et xor. Ces methodes sont particulierement interessantes pour permettre une meilleure exploitation des ressources des nouveaux cplds ainsi que les differentes configurations des blocs logiques des nouveaux fpgas. La derniere partie traite de la prediction temporelle sur des cibles hierarchiques. La modelisation des circuits en utilisant les structures de cones logiques, et leur classification temporelle permet d'orienter un decoupage du plan de masse, lequel guidera les outils de placement et routage.
34
Bayol, Catherine. "Une approche structurelle et comportementale de modélisation pour la vérification de composants VLSI." Phd thesis, Université Joseph Fourier (Grenoble), 1995. http://tel.archives-ouvertes.fr/tel-00005027.
Full textAbstract:
Le mémoire décrit une méthode de modélisation et de validation de composants micro-programmes pour l'implantation de protocole de communication de réseaux. Cette mèthode a été développée dans le cadre de la conception du composant FICOMP qui met en oeuvre la norme de bus de terrain FIELDBUS. Le premier chapitre décrit le contexte industriel du projet FICOMP, les différents niveaux de spécification du composant et les outils de simulation et de vérification utilisés. Le chapitre deux présente le langage VOVHDL, une extension de VHDL pour la spécification des communications et des synchronisations entre processus concurrents, et en donne une sémantique synchrone en termes de systèmes à transitions étiquetées. Le chapitre trois présente une approche de modélisation pour les descriptions VOVHDL hiérarchiques, et en illustre l'application au composant FICOMP : les modules internes sont reliés à un module de communication pour former un module de niveau supérieur ; ce module est alors traduisible dans le format d'entrée de l'outil de vérification ASA+. Le chapitre quatre rappelle les primitives essentielles du langage VHDL, et formalise la sémantique de simulation de ce langage en termes de systèmes à transitions étiquetées. Les annexes détaillent l'application de la méthode, par la spécification et la traduction dans le modèle propose de deux modules du projet FICOMP
35
Vala, Jiří. "Regulační soustavy." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2007. http://www.nusl.cz/ntk/nusl-412766.
Full textAbstract:
The MSc Thesis deals with real-time modelling, especially with the control circuits, where we focus on the regulation circuit with auxiliary model of the regulated system. The introduction contains the Theory of Controls and regulation. The work is divided into two basic parts. The first part deals with the problems from the theoretical point of view. The theoretical part is concerned with the general systems. Various definitions of systems, their partition and mathematical methods for their description are mentioned after introducing. A description the regulation circuits, their partition, structures and types follows. There are shown the particular regulators and different types of regulated systems in details. Mathematical methods applied to solve the differential equations that describe the models of the systems are summarized in the second part of the work. The end of this chapter is concerned with the TKSL system. In the practical part I have produced Microsoft Power Point program which summarizes the results of experiments, made in the TKSL and TKSL/C system. The output of simulation was transformed into the graphs in the format of Microsoft Excel. The last part deals with suggestion and implementation simulators of control circuits.
36
Laboudi, Khaled. "Contribution à la détection et à l'estimation des défauts pour des systèmes linéaires à commutations." Thesis, Reims, 2017. http://www.theses.fr/2017REIMS030/document.
Full textAbstract:
Ce travail de thèse traite de la problématique d’estimation des défauts et de l’étathybride pour une classe de systèmes linéaires à commutations. L’objectif est de développerune méthode afin de synthétiser un observateur et un estimateur dédiésrespectivement à l’estimation de l’état hybride et des défauts. Après la présentationd’un état de l’art sur les techniques d’estimation, de stabilité et de diagnosticpour les systèmes linéaires à commutations, la thèse est scindée en deux parties.La première partie propose une méthode d’estimation de l’état continu et desdéfauts dans le cas où l’état discret du système est connu. En se basant sur unetransformation de coordonnées qui découple un sous-ensemble de l’état du systèmedes défauts, nous avons synthétisé dans un premier temps un observateur hybridepour estimer l’état continu du système, et dans un second temps, un estimateurpermettant la reconstruction des défauts. L’estimateur de défauts proposé dépendde la dérivée de la sortie du système. Pour cette raison, un différenciateur robusteet exact basé sur des techniques des modes glissants est utilisé. Dans la secondepartie de ce mémoire, l’état discret du système est supposé inconnu. Une approchebasée sur des méthodes algébriques est proposée afin d’estimer les instants decommutation entre les différents sous-systèmes. Par la suite, l’estimation de l’étathybride (état continu et état discret) et des défauts est considérée dans le cas oùl’état discret du système est inconnu. Ce dernier est reconstruit en se basant surles instant de commutation estimé et sur une séquence de commutation connue.L’état continu du système est estimé en se basant sur une méthode de placementde pôles permettant d’améliorer les performances de la phase transitoire. Enfin, enexploitant des résultats trouvés dans la première partie, l’estimation des défautsest considérée en estimant la sortie du système avec un différenciateur algébrique.Ce différenciateur donne des résultats plus intéressants vis-à-vis du bruit par rapportau différenciateur basé sur les techniques des modes glissants utilisé dans lapremière partieThis work deals with the problem of estimation of fault and hybrid state for a classof switched linear systems. The objective is to develop a method to synthesize anobserver and an estimator dedicated respectively to the estimation of the hybridstate and the faults. After presenting a state of the art for estimation, stabilityand diagnostic techniques for switched linear systems, the report is divided intotwo parts. The first part proposes a method for estimating the continuous stateand the faults in the case where the discrete state of the system is known. Basedon a coordinate transformation which decouples a subset of the state of the systemof faults, we first synthesized a hybrid observer to estimate the continuous stateof the system and, in a second step, an estimator allowing the reconstructionof faults. The proposed fault estimator depends on the derivative of the systemoutput. For this reason, a robust and accurate differentiator based on sliding modetechniques is used. In the second part of this paper, the discrete state of the systemis assumed unknown. An algebraic approach is proposed to estimate the switchingtimes between the different subsystems. Thereafter, the estimation of the hybridstate (continuous and discrete state) and of the faults is considered in the casewhere the discrete state of the system is unknown. The latter is reconstructedfrom the estimated switching times and on a known switching sequence. Thecontinuous state of the system is estimated using a pole placement method allowingimprove the performances of the transient phase. Finally, by exploiting the resultsfound in the first part, the estimation of the faults is considered by estimatingthe output of the system with an algebraic differentiator. This differentiator givesmore interesting results at the noise compared to the differentiator based on thesliding mode techniques used in the first part
37
Aubert, Clément. "Logique linéaire et classes de complexité sous-polynomiales." Phd thesis, Université Paris-Nord - Paris XIII, 2013. http://tel.archives-ouvertes.fr/tel-00957653.
Full textAbstract:
Cette recherche en informatique théorique construit de nouveaux ponts entre logique linéaire et théorie de la complexité. Elle propose deux modèles de machines abstraites qui permettent de capturer de nouvelles classes de complexité avec la logique linéaire, les classes des problèmes efficacement parallélisables (NC et AC) et celle des problèmes solutionnables avec peu d'espace, dans ses versions déterministes et non-déterministes (L et NL). La représentation des preuves de la logique linéaire comme réseaux de preuves est employée pour représenter efficacement le calcul parallèle des circuits booléens, y compris à profondeur constante. La seconde étude s'inspire de la géométrie de l'interaction, une délicate reconstruction de la logique linéaire à l'aide d'opérateurs d'une algèbre de von Neumann. Nous détaillons comment l'interaction d'opérateurs représentant des entiers et d'opérateurs représentant des programmes peut être reconnue nilpotente en espace logarithmique. Nous montrons ensuite comment leur itération représente un calcul effectué par des machines à pointeurs que nous définissons et que nous rattachons à d'autres modèles plus classiques. Ces deux études permettent de capturer de façon implicite de nouvelles classes de complexité, en dessous du temps polynomial.
38
Nair, Vineet. "Expanders in Arithmetic Circuit Lower Bound : Towards a Separation Between ROABPs and Multilinear Depth 3 Circuits." Thesis, 2015. https://etd.iisc.ac.in/handle/2005/4811.
Full textAbstract:
Consider the problem of Polynomial Identity Testing(PIT): we are given an arithmetic circuit
computing a multivariate polynomial over some eld and we have to determine whether that
polynomial is identically zero or not. PIT is a fundamental problem and has applications in
both algorithms and complexity theory. In this work, our aim is to study PIT for the model
of multilinear depth three circuits for which no deterministic polynomial time identity test is
known. An nO(log n) time blackbox PIT for set-multilinear depth three circuits (a special kind of
multilinear depth three circuits) is known due to [ASS12], [FS13]. To get a better understanding
of the problem at hand, we move towards multilinear depth three circuits by considering in-
termediate circuit classes which encompasse more polynomials than set-multilinear depth three
circuits and are `natural' subclasses of multilinear depth three circuits. One such model is
`superposition of set-multilinear depth 3 circuits'. Our initial observations are:
There is an nO(log n) whitebox PIT for superposition of two set-multilinear depth 3 circuits.
There is a sub-exponential time whitebox PIT for superposition of constantly many set-
multilinear depth 3 circuits.
The second observation is subsumed by the recent independent and almost simultaneous work
by [OSV15] that gives sub-exponential time hitting set for multilinear depth three circuits.
A recent line of research considers hitting set for Read Once Oblivious Algebraic Branching
Programs (ROABP's) which subsumes set-multilinear depth three circuits. An nO(log n) black
box PIT is given for ROABP's of width polynomial in the number of variables in [AGKS14].
It is natural to ask whether this result on ROABP PIT can be used to give e cient (meaning
polynomial or quasi-polynomial time) PIT for multilinear depth three circuits. For instance,
the result by [OSV15] elegantly uses ROABP PIT as a `base case' (in a certain sense) to give
a sub-exponential time PIT algorithm for multilinear depth three circuits. At this point, we
wondered if multilinear depth three circuits of size s could also be computed by an ROABP of
size polynomial in s. If true then this would immediately imply a quasi-polynomial time hitting
set for multilinear depth three circuits, which is a long standing open problem in algebraic
complexity theory. For instance, it can be shown that any multlinear depth three circuit with
top fan-in two and just two variables per linear polynomial can be computed by an ROABP
with constant width. But we show in our main result that this is not true for general multilinear
depth three circuits that are superpositions of only two set-multilinear depth three circuits.
There is a polynomial computed by a superposition of two set-multilinear depth 3 circuits
with top fan-in just three and size polynomial in the number of variables n, such that any
ROABP computing the polynomial has width 2
(n).
There is a polynomial computed by a superposition of three set-multilinear depth 3 circuits
with top fan-in just two and size polynomial in the number of variables n, such that any
ROABP computing the polynomial has width 2
(n).
This means the approach of directly converting a multilinear depth 3 circuit (even a superposi-
tion of set-multilinear depth 3 circuits) to an ROABP and then applying the existing PIT for
ROABP will not work. However the underlying techniques in [ASS12], [AGKS14] and [OSV15]
might still be useful. The proofs of the above lower bounds are based on explicit construction
of expander graphs that can be used to design multilinear depth three circuits (in particular su-
perposition of set-multilinear depth 3 circuits) with high `evaluation dimension' - a complexity
measure that is well suited to capture a `weakness' of ROABPs.
39
Nair, Vineet. "On Learning and Lower Bound Problems Related to the Iterated Matrix Multiplication Polynomial." Thesis, 2020. https://etd.iisc.ac.in/handle/2005/4597.
Full textAbstract:
The iterated matrix multiplication polynomial (IMM) of width w and length d is the 1x1 entry in the product of d square matrices of size w. The w^2d entries in the d matrices are distinct variables. In this thesis, we study certain learning and lower bound problems related to IMM.
Our first work gives a polynomial time randomized algorithm for equivalence testing of IMM. At its core, the equivalence testing algorithm exploits a connection between the irreducible invariant subspaces of the Lie algebra of the group of symmetries of a polynomial f that is equivalent to IMM and the layer spaces of a full-rank algebraic branching program computing f. This connection also helps determine the group of symmetries of IMM and show that IMM is characterized by its group of symmetries.
Our second work is related to learning affine projections of IMM, which is believed to be a very hard problem as it is equivalent to reconstructing a powerful model to compute polynomials called algebraic branching programs (ABP). Equivalence test for IMM can be viewed as reconstructing ABPs in the average-case, when the width of the ABP is at most (n/d)^0.5, where n and d are the number of variables and the degree of the polynomial computed by the ABP respectively. Our second work improves this by first considering a related problem called `linear matrix factorization’ (LMF) which is a natural generalization of the polynomial factorization problem. We give a polynomial time randomized algorithm for average-case LMF for matrix products of width at most 0.5(n^0.5). In fact, we give a polynomial time randomized algorithm that solves (worst-case) LMF problem when the input matrix product is non-degenerate or pure product-- a notion we define in this work. Using our algorithm for LMF, we give a non-trivial average-case reconstruction algorithm for ABPs of width at most 0.5(n^0.5), which is interesting in the context of the Ω(n^0.5) width lower bound known for homogeneous ABPs.
Our last work gives lower bounds on interesting restrictions of arithmetic formulas computing IMM. We prove a w^Ω(d) lower bound on the size of multilinear depth three formulas computing IMM of width w and length d. The lower bound is proved by introducing a novel variant of the partial derivatives measure called skewed partial derivatives, which found applications in other subsequent works. Improving this result to w^Ω(log d) size lower bound on multilinear formulas computing IMM would imply a super-polynomial separation between ABPs and arithmetic formulas. We also show an exponential separation between multilinear depth three and multilinear depth four formulas which was an improvement over the quasi-polynomial separation already known. We also consider a restriction of multilinear formulas, called interval set-multilinear formulas computing IMM. Proving a super-polynomial size lower bound on interval set-multilinear formulas computing IMM would imply a super-polynomial separation between algebraic branching programs and homogeneous formulas in the non-commutative world. We make progress in this direction by giving a super-polynomial size lower bound on an interesting restriction of the interval set-multilinear formula computing IMM.
40
Ng, David. "Modeling circuit-level leakage current using algebraic decision diagrams." 2005. http://link.library.utoronto.ca/eir/EIRdetail.cfm?Resources__ID=370239&T=F.
Full text
41
Ameer, Abdul Kader Mohamed Basith Abdul. "Functional Verification of Arithmetic Circuits using Linear Algebra Methods." 2011. https://scholarworks.umass.edu/theses/657.
Full textAbstract:
This thesis describes an efficient method for speeding up functional verification of arithmetic circuits namely linear network such as wallace trees, counters using linear algebra techniques. The circuit is represented as a network of half adders, full adders and inverters, and modeled as a system of linear equations. The proof of functional correctness of the design is obtained by computing its algebraic signature using standard linear programming (LP) solver and comparing it with the reference signature provided by the designer. Initial experimental results and comparison with Satisfiability Modulo Theorem (SMT) solvers show that the method is efficient, scalable and applicable to complex arithmetic designs, including large multipliers. It is intended to provide a new front end theory/engine to enhance SMT solvers.
42
Bächle, Simone [Verfasser]. "Numerical solution of differential-algebraic systems arising in circuit simulation / vorgelegt von Simone Bächle." 2007. http://d-nb.info/983781311/34.
Full text
43
Chen, Bing-Yuan, and 陳炳元. "High-Level Synthesis of Finite-Field Arithmetic Circuits Using Abstract Algebra." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/88468495594240063925.
Full textAbstract:
碩士國立臺灣大學
電子工程學研究所
99
In high-level hardware synthesis, circuit datapaths are often expressed by polynomials in fixed-point arithmetic. Interestingly the intrinsic boundedness of hardware resources, rather than a limitation, is exploitable for circuit optimization. The data overflow (out-of-bounds) problems can be handled in different ways, for example, treating them using exceptions, congruences (modulo some positive integer), etc. Congruences under di erent moduli impose different algebraic structures. When the modulus is in the form of 2^n for some positive integer n, a polynomial can be seen as a ring. On the other hand, when the modulus is a prime number, a polynomial can be seen as a finite field. While the former received recent attention and progress, the later was relatively not well explored. This thesis is concerned with datapath optimization in the latter algebraic structure, and intends to compare the optimalities under the two di erent algebraic structures for possible design space exploration. The main results include (1) A simplification algorithm for single-output polynomials using unity polynomials. (2) An optimization algorithm for multiple-output polynomials based on common expression extraction. (3) A bracketing method to reduce the number of multiplication operations. Experimental results show that the area generated by our method is averagely 34.2% smaller than the Horner Form. Regarding the comparison with [1], the area is improved by 29.8%.
44
Estévez, Schwarz Diana [Verfasser]. "Consistent initialization for index-2 differential algebraic equations and its application to circuit simulation / von Diana Estévez Schwarz." 2000. http://d-nb.info/960337202/34.
Full text
45
"Switch preservation under two-stage interconnection: an algebraic theory for recursive construction of distributors and other types of switches." 2004. http://library.cuhk.edu.hk/record=b6073671.
Full textAbstract:
Tan Xuesong."June 2004."
Thesis (Ph.D.)--Chinese University of Hong Kong, 2004.
Includes bibliographical references (p. 247-251).
Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web.
Mode of access: World Wide Web.
Abstracts in English and Chinese.
46
Le, Van Dinh. "The broken circuit complex and the Orlik - Terao algebra of a hyperplane arrangement." Doctoral thesis, 2016. https://repositorium.ub.uni-osnabrueck.de/handle/urn:nbn:de:gbv:700-2016021714257.
Full textAbstract:
My thesis is mostly concerned with algebraic and combinatorial aspects of the
theory of hyperplane arrangements. More specifically, I study the Orlik-Terao algebra of a hyperplane arrangement and the broken circuit complex of a matroid. The Orlik-Terao algebra is a useful tool for studying hyperplane arrangements, especially for characterizing some non-combinatorial properties. The broken circuit complex, on the one hand, is closely related to the Orlik-Terao algebra, and on the other hand, plays a crucial role in the study of many combinatorial problem: the coefficients of the characteristic polynomial of a matroid are encoded in the f-vector of the broken circuit complex of the matroid. Among main results of the thesis are characterizations of the complete intersection and Gorenstein properties of the broken circuit complex and the Orlik-Terao algebra. I also study the h-vector of the broken circuit complex of a series-parallel network and relate certain entries of that vector to ear decompositions of the network. An application of the Orlik-Terao algebra in studying the relation space of a hyperplane arrangement is also included in the thesis.
47
Gupta, Nikhil. "Towards a Charcterization of the Symmetries of the Nisan-Wigderson Polynomial Family." Thesis, 2017. http://etd.iisc.ac.in/handle/2005/3802.
Full textAbstract:
Understanding the structure and complexity of a polynomial family is a fundamental problem of arithmetic circuit complexity. There are various approaches like studying the lower bounds, which deals with nding the smallest circuit required to compute a polynomial, studying the orbit and stabilizer of a polynomial with respect to an invertible transformation etc to do this. We have a rich understanding of some of the well known polynomial families like determinant, permanent, IMM etc. In this thesis we study some of the structural properties of the polyno-mial family called the Nisan-Wigderson polynomial family. This polynomial family is inspired from a well known combinatorial design called Nisan-Wigderson design and is recently used to prove strong lower bounds on some restricted classes of arithmetic circuits ([KSS14],[KLSS14], [KST16]). But unlike determinant, permanent, IMM etc, our understanding of the Nisan-Wigderson polynomial family is inadequate. For example we do not know if this polynomial family is in VP or VNP complete or VNP-intermediate assuming VP 6= VNP, nor do we have an understanding of the complexity of its equivalence test. We hope that the knowledge of some of the inherent properties of Nisan-Wigderson polynomial like group of symmetries and Lie algebra would provide us some insights in this regard.
A matrix A 2 GLn(F) is called a symmetry of an n-variate polynomial f if f(A x) = f(x): The set of symmetries of f forms a subgroup of GLn(F), which is also known as group of symmetries of f, denoted Gf . A vector space is attached to Gf to get the complete understanding of the symmetries of f. This vector space is known as the Lie algebra of group of symmetries of f (or Lie algebra of f), represented as gf . Lie algebra of f contributes some elements of Gf , known as continuous symmetries of f. Lie algebra has also been instrumental in designing e cient randomized equivalence tests for some polynomial families like determinant, permanent, IMM etc ([Kay12], [KNST17]).
In this work we completely characterize the Lie algebra of the Nisan-Wigderson polynomial family. We show that gNW contains diagonal matrices of a speci c type. The knowledge of gNW not only helps us to completely gure out the continuous symmetries of the Nisan-Wigderson polynomial family, but also gives some crucial insights into the other symmetries of Nisan-Wigderson polynomial (i.e. the discrete symmetries). Thereafter using the Hessian matrix of the Nisan-Wigderson polynomial and the concept of evaluation dimension, we are able to almost completely identify the structure of GNW . In particular we prove that any A 2 GNW is a product of diagonal and permutation matrices of certain kind that we call block-permuted permutation matrix. Finally, we give explicit examples of nontrivial block-permuted permutation matrices using the automorphisms of nite eld that establishes the richness of the discrete symmetries of the Nisan-Wigderson polynomial family.
48
Gupta, Nikhil. "Towards a Charcterization of the Symmetries of the Nisan-Wigderson Polynomial Family." Thesis, 2017. http://etd.iisc.ernet.in/2005/3802.
Full textAbstract:
Understanding the structure and complexity of a polynomial family is a fundamental problem of arithmetic circuit complexity. There are various approaches like studying the lower bounds, which deals with nding the smallest circuit required to compute a polynomial, studying the orbit and stabilizer of a polynomial with respect to an invertible transformation etc to do this. We have a rich understanding of some of the well known polynomial families like determinant, permanent, IMM etc. In this thesis we study some of the structural properties of the polyno-mial family called the Nisan-Wigderson polynomial family. This polynomial family is inspired from a well known combinatorial design called Nisan-Wigderson design and is recently used to prove strong lower bounds on some restricted classes of arithmetic circuits ([KSS14],[KLSS14], [KST16]). But unlike determinant, permanent, IMM etc, our understanding of the Nisan-Wigderson polynomial family is inadequate. For example we do not know if this polynomial family is in VP or VNP complete or VNP-intermediate assuming VP 6= VNP, nor do we have an understanding of the complexity of its equivalence test. We hope that the knowledge of some of the inherent properties of Nisan-Wigderson polynomial like group of symmetries and Lie algebra would provide us some insights in this regard.
A matrix A 2 GLn(F) is called a symmetry of an n-variate polynomial f if f(A x) = f(x): The set of symmetries of f forms a subgroup of GLn(F), which is also known as group of symmetries of f, denoted Gf . A vector space is attached to Gf to get the complete understanding of the symmetries of f. This vector space is known as the Lie algebra of group of symmetries of f (or Lie algebra of f), represented as gf . Lie algebra of f contributes some elements of Gf , known as continuous symmetries of f. Lie algebra has also been instrumental in designing e cient randomized equivalence tests for some polynomial families like determinant, permanent, IMM etc ([Kay12], [KNST17]).
In this work we completely characterize the Lie algebra of the Nisan-Wigderson polynomial family. We show that gNW contains diagonal matrices of a speci c type. The knowledge of gNW not only helps us to completely gure out the continuous symmetries of the Nisan-Wigderson polynomial family, but also gives some crucial insights into the other symmetries of Nisan-Wigderson polynomial (i.e. the discrete symmetries). Thereafter using the Hessian matrix of the Nisan-Wigderson polynomial and the concept of evaluation dimension, we are able to almost completely identify the structure of GNW . In particular we prove that any A 2 GNW is a product of diagonal and permutation matrices of certain kind that we call block-permuted permutation matrix. Finally, we give explicit examples of nontrivial block-permuted permutation matrices using the automorphisms of nite eld that establishes the richness of the discrete symmetries of the Nisan-Wigderson polynomial family.