Relevant bibliographies by topics / Algorithm algebra / Dissertations / Theses

Dissertations / Theses on the topic 'Algorithm algebra'

To see the other types of publications on this topic, follow the link: Algorithm algebra.
Author: Grafiati
Published: 30 May 2022
Last updated: 31 May 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 dissertations / theses for your research on the topic 'Algorithm algebra.'

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

Maust, Reid S. "Optimal power flow using a genetic algorithm and linear algebra." Morgantown, W. Va. : [West Virginia University Libraries], 1999. http://etd.wvu.edu/templates/showETD.cfm?recnum=1163.

Full text
Abstract:
Thesis (Ph. D.)--West Virginia University, 1999.
Title from document title page. Document formatted into pages; contains vi, 91 p. : ill. Vita. Includes abstract. Includes bibliographical references (p. 41-42).
APA, Harvard, Vancouver, ISO, and other styles
2

Delaplace, Claire. "Algorithmes d'algèbre linéaire pour la cryptographie." Thesis, Rennes 1, 2018. http://www.theses.fr/2018REN1S045/document.

Full text
Abstract:
Dans cette thèse, nous discutons d’aspects algorithmiques de trois différents problèmes, en lien avec la cryptographie. La première partie est consacrée à l’algèbre linéaire creuse. Nous y présentons un nouvel algorithme de pivot de Gauss pour matrices creuses à coefficients exacts, ainsi qu’une nouvelle heuristique de sélection de pivots, qui rend l’entière procédure particulièrement efficace dans certains cas. La deuxième partie porte sur une variante du problème des anniversaires, avec trois listes. Ce problème, que nous appelons problème 3XOR, consiste intuitivement à trouver trois chaînes de caractères uniformément aléatoires de longueur fixée, telles que leur XOR soit la chaîne nulle. Nous discutons des considérations pratiques qui émanent de ce problème et proposons un nouvel algorithme plus rapide à la fois en théorie et en pratique que les précédents. La troisième partie est en lien avec le problème learning with errors (LWE). Ce problème est connu pour être l’un des principaux problèmes difficiles sur lesquels repose la cryptographie à base de réseaux euclidiens. Nous introduisons d’abord un générateur pseudo-aléatoire, basé sur la variante dé-randomisée learning with rounding de LWE, dont le temps d’évaluation est comparable avec celui d’AES. Dans un second temps, nous présentons une variante de LWE sur l’anneau des entiers. Nous montrerons que dans ce cas le problème est facile à résoudre et nous proposons une application intéressante en re-visitant une attaque par canaux auxiliaires contre le schéma de signature BLISS
In this thesis, we discuss algorithmic aspects of three different problems, related to cryptography. The first part is devoted to sparse linear algebra. We present a new Gaussian elimination algorithm for sparse matrices whose coefficients are exact, along with a new pivots selection heuristic, which make the whole procedure particularly efficient in some cases. The second part treats with a variant of the Birthday Problem with three lists. This problem, which we call 3XOR problem, intuitively consists in finding three uniformly random bit-strings of fixed length, such that their XOR is the zero string. We discuss practical considerations arising from this problem, and propose a new algorithm which is faster in theory as well as in practice than previous ones. The third part is related to the learning with errors (LWE) problem. This problem is known for being one of the main hard problems on which lattice-based cryptography relies. We first introduce a pseudorandom generator, based on the de-randomised learning with rounding variant of LWE, whose running time is competitive with AES. Second, we present a variant of LWE over the ring of integers. We show that in this case the problem is easier to solve, and we propose an interesting application, revisiting a side-channel attack against the BLISS signature scheme
APA, Harvard, Vancouver, ISO, and other styles
3

Abrahamsson, Olle. "A Gröbner basis algorithm for fast encoding of Reed-Müller codes." Thesis, Linköpings universitet, Matematik och tillämpad matematik, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-132429.

Full text
Abstract:
In this thesis the relationship between Gröbner bases and algebraic coding theory is investigated, and especially applications towards linear codes, with Reed-Müller codes as an illustrative example. We prove that each linear code can be described as a binomial ideal of a polynomial ring, and that a systematic encoding algorithm for such codes is given by the remainder of the information word computed with respect to the reduced Gröbner basis. Finally we show how to apply the representation of a code by its corresponding polynomial ring ideal to construct a class of codes containing the so called primitive Reed-Müller codes, with a few examples of this result.
APA, Harvard, Vancouver, ISO, and other styles
4

Böhm, Josef. "Linking Geometry, Algebra and Calculus with GeoGebra." Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2012. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-79488.

Full text
Abstract:
GeoGebra is a free, open-source, and multi-platform software that combines dynamic geometry, algebra and calculus in one easy-to-use package. Students from middle-school to university can use it in classrooms and at home. In this workshop, we will introduce the features of GeoGebra with a special focus on not very common applications of a dynamic geometry program. We will inform about plans for developing training and research networks connected to GeoGebra. We can expect that at the time of the conference a spreadsheet will be integrated into GeoGebra which offers new ways teaching mathematics using the interplay between the features of a spreadsheet and the objects of dynamic geometry.
APA, Harvard, Vancouver, ISO, and other styles
5

Vora, Rohit H. "An Algorithm for multi-output Boolean logic minimization." Thesis, Virginia Tech, 1987. http://hdl.handle.net/10919/43829.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
6

Enkosky, Thomas. "Grobner Bases and an Algorithm to Find the Monomials of an Ideal." Fogler Library, University of Maine, 2004. http://www.library.umaine.edu/theses/pdf/EnkoskyT2004.pdf.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Wood, Peter John, and drwoood@gmail com. "Wavelets and C*-algebras." Flinders University. Informatics and Engineering, 2003. http://catalogue.flinders.edu.au./local/adt/public/adt-SFU20070619.120926.

Full text
Abstract:
A wavelet is a function which is used to construct a specific type of orthonormal basis. We are interested in using C*-algebras and Hilbert C*-modules to study wavelets. A Hilbert C*-module is a generalisation of a Hilbert space for which the inner product takes its values in a C*-algebra instead of the complex numbers. We study wavelets in an arbitrary Hilbert space and construct some Hilbert C*-modules over a group C*-algebra which will be used to study the properties of wavelets. We study wavelets by constructing Hilbert C*-modules over C*-algebras generated by groups of translations. We shall examine how this construction works in both the Fourier and non-Fourier domains. We also make use of Hilbert C*-modules over the space of essentially bounded functions on tori. We shall use the Hilbert C*-modules mentioned above to study wavelet and scaling filters, the fast wavelet transform, and the cascade algorithm. We shall furthermore use Hilbert C*-modules over matrix C*-algebras to study multiwavelets.
APA, Harvard, Vancouver, ISO, and other styles
8

Hansen, Nils Bahne [Verfasser]. "Structure Analysis of the Pohlmeyer-Rehren Lie Algebra and Adaptations of the Hall Algorithm to Non-Free Graded Lie Algebras / Nils Bahne Hansen." Göttingen : Niedersächsische Staats- und Universitätsbibliothek Göttingen, 2021. http://d-nb.info/1236401646/34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Linfoot, Andy James. "A Case Study of A Multithreaded Buchberger Normal Form Algorithm." Diss., The University of Arizona, 2006. http://hdl.handle.net/10150/305141.

Full text
Abstract:
Groebner bases have many applications in mathematics, science, and engineering. This dissertation deals with the algorithmic aspects of computing these bases. The dissertation begins with a brief introduction of fundamental concepts about Groebner bases. Following this a discussion of various implementation issues are discussed. Much of the practical difficulties of using Groebner basis algorithms and techniques stems from the high computational complexity. It is shown that the algorithmic complexity of computing a Groebner basis primarily stems from the calculation of normal forms. This is established by studying run profiles of various computations. This leads to two options of making Groebner basis techniques more practical. They are to reduce the complexity by developing new algorithms (heuristics) or reduce running time of normal form calculations by introducing concurrency. The later approach is taken in the remainder of the dissertation where a multithreaded normal form algorithm is presented and discussed. It is shown with a simple example that the new algorithm demonstrates a speedup and scalability. The algorithm also has the advantage of being completion strategy independent. We conclude with an outline of future research involving the new algorithm.
APA, Harvard, Vancouver, ISO, and other styles
10

Neverauskas, Aurimas. "Lygčių ir nelygybių simbolinio sprendimo lygiagretusis metodas." Master's thesis, Lithuanian Academic Libraries Network (LABT), 2011. http://vddb.laba.lt/obj/LT-eLABa-0001:E.02~2011~D_20110831_140404-69461.

Full text
Abstract:
Pateiktas lygčių ir nelygybių simbolinio sprendimo lygiagretus algoritmas ir jo analizė, palyginimas su neefektyvia algoritmo realizacija. Atliktas įgyvendinto algoritmo tyrimas, nustatant jo spartos priklausomybes nuo aplinkos ir užduoties, palyginant rezultatus su esama PĮ. Taip pat, šiame darbe aptariami sukurtos programų sistemos architektūriniai sprendimai: MVC patern‘as (design pattern), „Svogūno“ architektūra, priklausomybių injekcijos (Dependency Injections). Šie architektūriniai sprendimai yra pranašesni už standartinę sluoksninę architekūrą, jais paremta PĮ yra lengviau palaikoma ir modifikuojama. Šiais laikais dauguma kompiuterių turi daugiabranduolius procesorius, tačiau esama PĮ jų neišnaudoja. Šio darbo tikslas yra sukurti tokią lygčių ir nelygybių simbolinio sprendimo lygiagrečiu metodu realizaciją, kuri panaudodama turimą skaičiavimų galią, sutrumpintų skaičiavimų laiką. Atlikus tyrimus nustatyta, jog sukurtoji PĮ yra pranašesnė už Maple CAS tik tuo atveju, kai uždavinio sąlyga nėra didelė, bet reikalaujama didelės skaičiavimų galios (nelygybių sistemų sprendimas). Tačiau sprendžiant didelės apimties lygčių sistemas (40-50 nežinomųjų ir tiek pat lygčių) sukurtoji PĮ atsilieka nuo Maple CAS, kadangi daug laiko sugaištama nagrinėjant pateiktą užduotį ir skaidant ją į dalinius uždavinius.
I have presented an effective way to solve symbolic systems of equations and inequalities using parallel processes and compared it to ineffective method. Also, I have performed analysis of presented algorithm, determining its performance dependencies and comparing its performance to existing software. Also, this paper discusses architectural solutions for the application system: MVC design pattern, "Onion" architecture and Dependency Injection. These architectural patterns benefit more than standard layered architecture, software, based on these patterns, is more maintainable and changeable. These days, computers usually have multi-core processors, but not all software use them efficiently. The main problem is to create algorithm for solving symbolic systems of equations and inequalities using parallel processes, using calculation power and decreasing calculation time. Such application system was created and analyzed in this paper. It was determined that created software is superior to Maple CAS when task is small by input but requires a lot of calculating power (systems of inequalities). On the other hand, results differ when task consist of plenty of equations (40-50 equations in system, same number of unknowns). Created software falls behind Maple CAS in performance. The main reason, for this, is that created software spends too much time to analyze task and strings in it.
APA, Harvard, Vancouver, ISO, and other styles
11

Caponi, Louis. "On the Classification of Groups Generated by Automata with 4 States over a 2-Letter Alphabet." Scholar Commons, 2014. https://scholarcommons.usf.edu/etd/4995.

Full text
Abstract:
The class of groups generated by automata have been a source of many counterexamples in group theory. At the same time it is connected to other branches of mathematics, such as analysis, holomorphic dynamics, combinatorics, etc. A question that naturally arises is finding the ways to classify these groups. The task of a complete classification and understanding at the moment seems to be too ambitious, but it is reasonable to concentrate on some smaller subclasses of this class. One approach is to consider groups generated by small automata: the automata with k states over d-letter alphabet (so called, (k,d)-automata) with small values of k and d. Certain steps in this directions have been made already: All groups generated by (2,2)-automata have been classified, and groups generated by (3,2)-automata were studied. In this work we study the class of groups generated by (4,2)-automata. More specifically, we partition all such automata into equivalence classes up to symmetry and minimal symmetry (symmetric and minimally symmetric automata naturally generate isomorphic groups) and classify completely all finite groups generated by automata in this class. We also list all classes generating abelian groups. Another important result of the project is developing a database of (4,2)-automata and computational routines that represent a new effective tool for the search for (4,2)-automata generating groups with specific properties, which hopefully will lead to finding counterexamples of certain conjectures.
APA, Harvard, Vancouver, ISO, and other styles
12

Chen, Shaoshi. "Quelques applications de l'algébre différentielle et aux différences pour le télescopage créatif." Phd thesis, Ecole Polytechnique X, 2011. http://pastel.archives-ouvertes.fr/pastel-00576861.

Full text
Abstract:
Depuis les années 90, la méthode de création télescopique de Zeilberger a joué un rôle important dans la preuve automatique d'identités mettant en jeu des fonctions spéciales. L'objectif de long terme que nous attaquons dans ce travail est l'obtension d'algorithmes et d'implantations rapides pour l'intégration et la sommation définies dans le cadre de cette création télescopique. Nos contributions incluent de nouveaux algorithmes pratiques et des critères théoriques pour tester la terminaison d'algorithmes existants. Sur le plan pratique, nous nous focalisons sur la construction de télescopeurs minimaux pour les fonctions rationnelles en deux variables, laquelle a de nombreuses applications en lien avec les fonctions algébriques et les diagonales de séries génératrices rationnelles. En considérant cette classe d'entrées contraintes, nous parvenons à mâtiner la méthode générale de création télescopique avec réduction bien connue d'Hermite, issue de l'intégration symbolique. En outre, nous avons obtenu pour cette sous-classe quelques améliorations des algorithmes classiques d'Almkvist et Zeilberger. Nos résultats expérimentaux ont montré que les algorithmes à base de réduction d'Hermite battent tous les autres algorithmes connus, à la fois en ce qui concerne la complexité au pire et en ce qui concerne les mesures de temps sur nos implantations. Sur le plan théorique, notre premier résultat est motivé par la conjecture de Wilf et Zeilberger au sujet des fonctions hyperexponentielles-hypergéométriques holonomes. Nous présentons un théorème de structure pour les fonctions hyperexponentielles-hypergéométriques de plusieurs variables, indiquant qu'une telle fonction peut s'écrire comme le produit de fonctions usuelles. Ce théorème étend à la fois le théorème d'Ore et Sato pour les termes hypergéométriques en plusieurs variables et le résultat récent par Feng, Singer et Wu. Notre second résultat est relié au problème de l'existence de télescopeurs. Dans le cas discret à deux variables, Abramov a obtenu un critère qui indique quand un terme hypergéométrique a un télescopeur. Des résultats similaires ont été obtenus pour le $q$-décalage par Chen, Hou et Mu. Ces résultats sont fondamentaux pour la terminaison des algorithmes s'inspirant de celui de Zeilberger. Dans les autres cas mixtes continus/discrets, nous avons obtenu deux critères pour l'existence de télescopeurs pour des fonctions hyperexponentielles-hypergéométriques en deux variables. Nos critères s'appuient sur une représentation standard des fonctions hyperexponentielles-hypergéométriques en deux variables, sur sur deux décompositions additives.
APA, Harvard, Vancouver, ISO, and other styles
13

Thakre, Purva. "USING A NUMERICAL ALGORITHM TO SEARCH FOR DECOHERENCE-FREE SUB-SYSTEMS." OpenSIUC, 2018. https://opensiuc.lib.siu.edu/theses/2465.

Full text
Abstract:
In this paper, we discuss the need for quantum error correction. We also describe some basic techniques used in quantum error correction which includes decoherence-free subspaces and subsystems. These subspaces and subsystems are described in detail. We also introduce a numerical algorithm that was used previously to search for these decoherence-free subspaces and subsystems under collective error. It is useful to search for them as they can be used to store quantum information. We use this algorithm in some specific examples involving qubits and qutrits. The results of these algorithm are then compared with the error algebra obtained using Young tableaux. We use these results to describe how the specific numerical algorithm can be used for the search of approximate decoherence-free subspaces and subsystems and minimal noise subsystems.
APA, Harvard, Vancouver, ISO, and other styles
14

Stothers, Andrew James. "On the complexity of matrix multiplication." Thesis, University of Edinburgh, 2010. http://hdl.handle.net/1842/4734.

Full text
Abstract:
The evaluation of the product of two matrices can be very computationally expensive. The multiplication of two n×n matrices, using the “default” algorithm can take O(n3) field operations in the underlying field k. It is therefore desirable to find algorithms to reduce the “cost” of multiplying two matrices together. If multiplication of two n × n matrices can be obtained in O(nα) operations, the least upper bound for α is called the exponent of matrix multiplication and is denoted by ω. A bound for ω < 3 was found in 1968 by Strassen in his algorithm. He found that multiplication of two 2 × 2 matrices could be obtained in 7 multiplications in the underlying field k, as opposed to the 8 required to do the same multiplication previously. Using recursion, we are able to show that ω ≤ log2 7 < 2.8074, which is better than the value of 3 we had previously. In chapter 1, we look at various techniques that have been found for reducing ω. These include Pan’s Trilinear Aggregation, Bini’s Border Rank and Sch¨onhage’s Asymptotic Sum inequality. In chapter 2, we look in detail at the current best estimate of ω found by Coppersmith and Winograd. We also propose a different method of evaluating the “value” of trilinear forms. Chapters 3 and 4 build on the work of Coppersmith and Winograd and examine how cubing and raising to the fourth power of Coppersmith and Winograd’s “complicated” algorithm affect the value of ω, if at all. Finally, in chapter 5, we look at the Group-Theoretic context proposed by Cohn and Umans, and see how we can derive some of Coppersmith and Winograd’s values using this method, as well as showing how working in this context can perhaps be more conducive to showing ω = 2.
APA, Harvard, Vancouver, ISO, and other styles
15

Lian, Tea Sormbroen. "Computing Almost Split Sequences : An algorithm for computing almost split sequences of finitely generated modules over a finite dimensional algebra." Thesis, Norges teknisk-naturvitenskapelige universitet, Institutt for matematiske fag, 2012. http://urn.kb.se/resolve?urn=urn:nbn:no:ntnu:diva-19355.

Full text
Abstract:
An artin algebra $l$ over a commutative, local, artinian ring $R$ was fixed, and with this foundation some topics from representation theory were discussed. A series of functors of module categories were defined, and almost split sequences were introduced with some basic results. An isomorphism $omega_{delta,X} : D delta^* rightarrow delta_*(DTr(X))$ of $Gamma$-modules for an artin $R$-algebra $Gamma$ was constructed. The isomorphism $omega_{delta,X}$ was applied to a special case, yielding a deterministic algorithm for computing almost split sequences in the case that $R$ is a field.
APA, Harvard, Vancouver, ISO, and other styles
16

Peh, Lawrence T. W. "An efficient algorithm for extracting Boolean functions from linear threshold gates, and a synthetic decompositional approach to extracting Boolean functions from feedforward neural networks with arbitrary transfer functions." University of Western Australia. Dept. of Computer Science, 2000. http://theses.library.uwa.edu.au/adt-WU2003.0013.

Full text
Abstract:
[Formulae and special characters can only be approximated here. Please see the pdf version of the Abstract for an accurate reproduction.] Artificial neural networks are universal function approximators that represent functions subsymbolically by weights, thresholds and network topology. Naturally, the representation remains the same regardless of the problem domain. Suppose a network is applied to a symbolic domain. It is difficult for a human to dynamically construct the symbolic function from the neural representation. It is also difficult to retrain networks on perturbed training vectors, to resume training with different training sets, to form a new neuron by combining trained neurons, and to reason with trained neurons. Even the original training set does not provide a symbolic representation of the function implemented by the trained network because the set may be incomplete or inconsistent, and the training phase may terminate with residual errors. The symbolic information in the network would be more useful if it is available in the language of the problem domain. Algorithms that translate the subsymbolic neural representation to a symbolic representation are called extraction algorithms. I argue that extraction algorithms that operate on single-output, layered feedforward networks are sufficient to analyse the class of multiple-output networks with arbitrary connections, including recurrent networks. The translucency dimensions of the ADT taxonomy for feedforward networks classifies extraction approaches as pedagogical, eclectic, or decompositional. Pedagogical and eclectic approaches typically use a symbolic learning algorithm that takes the network’s input-output behaviour as its raw data. Both approaches construct a set of input patterns and observe the network’s output for each pattern. Eclectic and pedagogical approaches construct the input patterns respectively with and without reference to the network’s internal information. These approaches are suitable for approximating the network’s function using a probably-approximately-correct (PAC) or similar framework, but they are unsuitable for constructing the network’s complete function. Decompositional approaches use internal information from a network more directly to produce the network’s function in symbolic form. Decompositional algorithms have two components. The first component is a core extraction algorithm that operates on a single neuron that is assumed to implement a symbolic function. The second component provides the superstructure for the first. It consists of a decomposition rule for producing such neurons and a recomposition rule for symbolically aggregating the extracted functions into the symbolic function of the network. This thesis makes contributions to both components for Boolean extraction. I introduce a relatively efficient core algorithm called WSX based on a novel Boolean form called BvF. The algorithm has a worst case complexity of O(2 to power of n divided by the square root of n) for a neuron with n inputs, but in all cases, its complexity can also be expressed as O(l) with an O(n) precalculation phase, where l is the length of the extracted expression in terms of the number of symbols it contains. I extend WSX for approximate extraction (AWSX) by introducing an interval about the neuron’s threshold. Assuming that the input patterns far from the threshold are more symbolically significant to the neuron than those near the threshold, ASWX ignores the neuron’s mappings for the symbolically input patterns, remapping them as convenient for efficiency. In experiments, this dramatically decreased extraction time while retaining most of the neuron’s mappings for the training set. Synthetic decomposition is this thesis’ contribution to the second component of decompositional extraction. Classical decomposition decomposes the network into its constituent neurons. By extracting symbolic functions from these neurons, classical decomposition assumes that the neurons implement symbolic functions, or that approximating the subsymbolic computation in the neurons with symbolic computation does not significantly affect the network’s symbolic function. I show experimentally that this assumption does not always hold. Instead of decomposing a network into its constituent neurons, synthetic decomposition uses constraints in the network that have the same functional form as neurons that implement Boolean functions; these neurons are called synthetic neurons. I present a starting point for constructing synthetic decompositional algorithms, and proceed to construct two such algorithms, each with a different strategy for decomposition and recomposition. One of the algorithms, ACX, works for networks with arbitrary monotonic transfer functions, so long as an inverse exists for the functions. It also has an elegant geometric interpretation that leads to meaningful approximations. I also show that ACX can be extended to layered networks with any number of layers.
APA, Harvard, Vancouver, ISO, and other styles
17

Karlsson, Andréas. "Algorithm Adaptation and Optimization of a Novel DSP Vector Co-processor." Thesis, Linköping University, Computer Engineering, 2010. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-57427.

Full text
Abstract:

The Division of Computer Engineering at Linköping's university is currently researching the possibility to create a highly parallel DSP platform, that can keep up with the computational needs of upcoming standards for various applications, at low cost and low power consumption. The architecture is called ePUMA and it combines a general RISC DSP master processor with eight SIMD co-processors on a single chip. The master processor will act as the main processor for general tasks and execution control, while the co-processors will accelerate computing intensive and parallel DSP kernels.This thesis investigates the performance potential of the co-processors by implementing matrix algebra kernels for QR decomposition, LU decomposition, matrix determinant and matrix inverse, that run on a single co-processor. The kernels will then be evaluated to find possible problems with the co-processors' microarchitecture and suggest solutions to the problems that might exist. The evaluation shows that the performance potential is very good, but a few problems have been identified, that causes significant overhead in the kernels. Pipeline mismatches, that occurs due to different pipeline lengths for different instructions, causes pipeline hazards and the current solution to this, doesn't allow effective use of the pipeline. In some cases, the single port memories will cause bottlenecks, but the thesis suggests that the situation could be greatly improved by using buffered memory write-back. Also, the lack of register forwarding makes kernels with many data dependencies run unnecessarily slow.

APA, Harvard, Vancouver, ISO, and other styles
18

Nyman, Peter. "On relations between classical and quantum theories of information and probability." Doctoral thesis, Linnéuniversitetet, Institutionen för datavetenskap, fysik och matematik, DFM, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:lnu:diva-13830.

Full text
Abstract:
In this thesis we study quantum-like representation and simulation of quantum algorithms by using classical computers.The quantum--like representation algorithm (QLRA) was  introduced by A. Khrennikov (1997) to solve the ``inverse Born's rule problem'', i.e. to construct a representation of probabilistic data-- measured in any context of science-- and represent this data by a complex or more general probability amplitude which matches a generalization of Born's rule.The outcome from QLRA matches the formula of total probability with an additional trigonometric, hyperbolic or hyper-trigonometric interference term and this is in fact a generalization of the familiar formula of interference of probabilities. We study representation of statistical data (of any origin) by a probability amplitude in a complex algebra and a Clifford algebra (algebra of hyperbolic numbers). The statistical data is collected from measurements of two dichotomous and trichotomous observables respectively. We see that only special statistical data (satisfying a number of nonlinear constraints) have a quantum--like representation. We also study simulations of quantum computers on classical computers.Although it can not be denied that great progress have been made in quantum technologies, it is clear that there is still a huge gap between the creation of experimental quantum computers and realization of a quantum computer that can be used in applications. Therefore the simulation of quantum computations on classical computers became an important part in the attempt to cover this gap between the theoretical mathematical formulation of quantum mechanics and the realization of quantum computers. Of course, it can not be expected that quantum algorithms would help to solve NP problems for polynomial time on classical computers. However, this is not at all the aim of classical simulation.  The second part of this thesis is devoted to adaptation of the Mathematica symbolic language to known quantum algorithms and corresponding simulations on classical computers. Concretely we represent Simon's algorithm, Deutsch-Josza algorithm, Shor's algorithm, Grover's algorithm and quantum error-correcting codes in the Mathematica symbolic language. We see that the same framework can be used for all these algorithms. This framework will contain the characteristic property of the symbolic language representation of quantum computing and it will be a straightforward matter to include future algorithms in this framework.
APA, Harvard, Vancouver, ISO, and other styles
19

Davidsdottir, Agnes. "Algorithms, Turing machines and algorithmic undecidability." Thesis, Uppsala universitet, Algebra och geometri, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-441282.

Full text
APA, Harvard, Vancouver, ISO, and other styles
20

Sawada, Koichiro. "Reconstruction of invariants of configuration spaces of hyperbolic curves from associated Lie algebras." Kyoto University, 2019. http://hdl.handle.net/2433/242578.

Full text
APA, Harvard, Vancouver, ISO, and other styles
21

Khungurn, Pramook. "Shirayanagi-Sweedler algebraic algorithm stabilization and polynomial GCD algorithms." Thesis, Massachusetts Institute of Technology, 2007. http://hdl.handle.net/1721.1/41662.

Full text
Abstract:
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2007.
Includes bibliographical references (p. 71-72).
Shirayanagi and Sweedler [12] proved that a large class of algorithms on the reals can be modified slightly so that they also work correctly on floating-point numbers. Their main theorem states that, for each input, there exists a precision, called the minimum converging precision (MCP), at and beyond which the modified "stabilized" algorithm follows the same sequence of steps as the original "exact" algorithm. In this thesis, we study the MCP of two algorithms for finding the greatest common divisor of two univariate polynomials with real coefficients: the Euclidean algorithm, and an algorithm based on QR-factorization. We show that, if the coefficients of the input polynomials are allowed to be any computable numbers, then the MCPs of the two algorithms are not computable, implying that there are no "simple" bounding functions for the MCP of all pairs of real polynomials. For the Euclidean algorithm, we derive upper bounds on the MCP for pairs of polynomials whose coefficients are members of Z, 0, Z[6], and Q[6] where ( is a real algebraic integer. The bounds are quadratic in the degrees of the input polynomials or worse. For the QR-factorization algorithm, we derive a bound on the minimal precision at and beyond which the stabilized algorithm gives a polynomial with the same degree as that of the exact GCD, and another bound on the the minimal precision at and beyond which the algorithm gives a polynomial with the same support as that of the exact GCD. The bounds are linear in (1) the degree of the polynomial and (2) the sum of the logarithm of diagonal entries of matrix R in the QR factorization of the Sylvester matrix of the input polynomials.
by Pramook Khungurn.
M.Eng.
APA, Harvard, Vancouver, ISO, and other styles
22

Asafu-Adjei, Joseph Kwaku. "Probabilistic Methods." VCU Scholars Compass, 2007. http://hdl.handle.net/10156/1420.

Full text
APA, Harvard, Vancouver, ISO, and other styles
23

Krone, Robert Carlton. "Symmetric ideals and numerical primary decomposition." Diss., Georgia Institute of Technology, 2015. http://hdl.handle.net/1853/53907.

Full text
Abstract:
The thesis considers two distinct strategies for algebraic computation with polynomials in high dimension. The first concerns ideals and varieties with symmetry, which often arise in applications from areas such as algebraic statistics and optimization. We explore the commutative algebra properties of such objects, and work towards classifying when symmetric ideals admit finite descriptions including equivariant Gröbner bases and generating sets. Several algorithms are given for computing such descriptions. Specific focus is given to the case of symmetric toric ideals. A second area of research is on problems in numerical algebraic geometry. Numerical algorithms such as homotopy continuation can efficiently compute the approximate solutions of systems of polynomials, but generally have trouble with multiplicity. We develop techniques to compute local information about the scheme structure of an ideal at approximate zeros. This is used to create a hybrid numeric-symbolic algorithm for computing a primary decomposition of the ideal.
APA, Harvard, Vancouver, ISO, and other styles
24

Duchamp, Gérard. "Algorithmes sur les polynomes en variables non commutatives." Paris 7, 1987. http://www.theses.fr/1987PA077069.

Full text
Abstract:
Etude des monoides libres et de leurs algebres. Presentation de nouvelles caracterisations des bisections reconnaissables; de la caracterisation des mots pouvant appartenir au support d'un polynome de lie et de l'etude de quelques proprietes algebriques de polynomes en variables partiallement commutatives. Etude du treillis des congruences regulieres sur le monoide bicyclique
APA, Harvard, Vancouver, ISO, and other styles
25

Ishigami, Hiroyuki. "Studies on Parallel Solvers Based on Bisection and Inverse Iterationfor Subsets of Eigenpairs and Singular Triplets." 京都大学 (Kyoto University), 2016. http://hdl.handle.net/2433/215685.

Full text
Abstract:
5章（本文31～40ページ）と元となった論文の著作権はIEEEに属するため、規約に従い、本文79ページにおいて出典を示すともに、コピーライト表記を付している。本文39、40ページの全ての図の著作権は、IEEEに属する。このため、これら全ての図においてコピーライト表記を付している。
Kyoto University (京都大学)
0048
新制・課程博士
博士(情報学)
甲第19858号
情博第609号
新制||情||106(附属図書館)
32894
京都大学大学院情報学研究科数理工学専攻
(主査)教授 中村 佳正, 教授 梅野 健, 教授 中島 浩
学位規則第4条第1項該当
APA, Harvard, Vancouver, ISO, and other styles
26

Sultan, Ziad. "Algèbre linéaire exacte, parallèle, adaptative et générique." Thesis, Université Grenoble Alpes (ComUE), 2016. http://www.theses.fr/2016GREAM030/document.

Full text
Abstract:
Les décompositions en matrices triangulaires sont une brique de base fondamentale en calcul algébrique. Ils sont utilisés pour résoudre des systèmes linéaires et calculer le rang, le déterminant, l'espace nul ou les profiles de rang en ligne et en colonne d'une matrix. Le projet de cette thèse est de développer des implantations hautes performances parallèles de l'élimination de Gauss exact sur des machines à mémoire partagée.Dans le but d'abstraire le code de l'environnement de calcul parallèle utilisé, un langage dédié PALADIn (Parallel Algebraic Linear Algebra Dedicated Interface) a été implanté et est basé essentiellement sur des macros C/C++. Ce langage permet à l'utilisateur d'écrire un code C++ et tirer partie d’exécutions séquentielles et parallèles sur des architectures à mémoires partagées en utilisant le standard OpenMP et les environnements parallel KAAPI et TBB, ce qui lui permet de bénéficier d'un parallélisme de données et de taches.Plusieurs aspects de l'algèbre linéaire exacte parallèle ont été étudiés. Nous avons construit de façon incrémentale des noyaux parallèles efficaces pour les multiplication de matrice, la résolution de systèmes triangulaires au dessus duquel plusieurs variantes de l'algorithme de décomposition PLUQ sont construites. Nous étudions la parallélisation de ces noyaux en utilisant plusieurs variantes algorithmiques itératives ou récursives et en utilisant des stratégies de découpes variées.Nous proposons un nouvel algorithme récursive de l'élimination de Gauss qui peut calculer simultanément les profiles de rang en ligne et en colonne d'une matrice et de toutes ses sous-matrices principales, tout en étant un algorithme état de l'art de l'élimination de Gauss. Nous étudions aussi les conditions pour qu'un algorithme de l'élimination de Gauss révèle cette information en définissant un nouvel invariant matriciel, la matrice de profil de rang
Triangular matrix decompositions are fundamental building blocks in computational linear algebra. They are used to solve linear systems, compute the rank, the determinant, the null-space or the row and column rank profiles of a matrix. The project of my PhD thesis is to develop high performance shared memory parallel implementations of exact Gaussian elimination.In order to abstract the computational code from the parallel programming environment, we developed a domain specific language, PALADIn: Parallel Algebraic Linear Algebra Dedicated Interface, that is based on C/C + + macros. This domain specific language allows the user to write C + + code and benefit from sequential and parallel executions on shared memory architectures using the standard OpenMP, TBB and Kaapi parallel runtime systems and thus providing data and task parallelism.Several aspects of parallel exact linear algebra were studied. We incrementally build efficient parallel kernels, for matrix multiplication, triangular system solving, on top of which several variants of PLUQ decomposition algorithm are built. We study the parallelization of these kernels using several algorithmic variants: either iterative or recursive and using different splitting strategies.We propose a recursive Gaussian elimination that can compute simultaneously therow and column rank profiles of a matrix as well as those of all of its leading submatrices, in the same time as state of the art Gaussian elimination algorithms. We also study the conditions making a Gaussian elimination algorithm reveal this information by defining a new matrix invariant, the rank profile matrix
APA, Harvard, Vancouver, ISO, and other styles
27

Gunnels, John Andrew. "A systematic approach to the design and analysis of linear algebra algorithms." Access restricted to users with UT Austin EID Full text (PDF) from UMI/Dissertation Abstracts International, 2001. http://wwwlib.umi.com/cr/utexas/fullcit?p3037015.

Full text
APA, Harvard, Vancouver, ISO, and other styles
28

Singh, Manjeet. "Mathematical Models, Heuristics and Algorithms for Efficient Analysis and Performance Evaluation of Job Shop Scheduling Systems Using Max-Plus Algebraic Techniques." Ohio University / OhioLINK, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1386087325.

Full text
APA, Harvard, Vancouver, ISO, and other styles
29

Lundqvist, Samuel. "Computational algorithms for algebras." Doctoral thesis, Stockholm : Department of Mathematics, Stockholm University, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:su:diva-31552.

Full text
Abstract:
Diss. (sammanfattning) Stockholm : Stockholms universitet, 2009.
At the time of doctoral defence, the following papers were unpublished and had a status as follows: Paper 3: Manuscript. Paper 4: Manuscript. Paper 5: Manuscript. Paper 6: Manuscript. Härtill 6 uppsatser.
APA, Harvard, Vancouver, ISO, and other styles
30

Gibbons, Jeremy. "Algebras for tree algorithms." Thesis, University of Oxford, 1991. http://ora.ox.ac.uk/objects/uuid:50ed112d-411d-486f-8631-6064138f4bf7.

Full text
Abstract:
This thesis presents an investigation into the properties of various algebras of trees. In particular, we study the influence that the structure of a tree algebra has on the solution of algorithmic problems about trees in that algebra. The investigation is conducted within the framework provided by the Bird-Meertens formalism, a calculus for the construction of programs by equational reasoning from their specifications. We present three different tree algebras: two kinds of binary tree and a kind of general tree. One of the binary tree algebras, called "hip trees", is new. Instead of being built with a single ternary operator, hip trees are built with two binary operators which respectively add left and right children to trees which do not already have them; these operators enjoy a kind of associativity property. Each of these algebras brings with it with a class of "structure-respecting" functions called catamorphisms; the definition of a catamorphism and a number of its properties come for free from the definition of the algebra, because the algebra is chosen to be initial in a class of algebras induced by a (cocontinuous) functor. Each algebra also brings with it, but not for free, classes of "structure-preserving" functions called accumulations. An accumulation is a function that preserves the shape of a structured object such as a tree, but replaces each element of that object with some catamorphism applied to some of the other elements. The two classes of accumulation that we study are the "upwards" and "downwards" accumulations, which pass information from the leaves of a tree towards the root and from the root towards the leaves, respectively. Upwards and downwards accumulations turn out to be the key to the solution of many problems about trees. We derive accumulation-based algorithms for a number of problems; these include the parallel prefix algorithm for the prefix sums problem, algorithms for bracket matching and for drawing binary and general trees, and evaluators for decorating parse trees according to an attribute grammar.
APA, Harvard, Vancouver, ISO, and other styles
31

Alves, Rafael Santos de Oliveira 1982. "Algebra geometrica e o algoritmo de Grover." [s.n.], 2008. http://repositorio.unicamp.br/jspui/handle/REPOSIP/306805.

Full text
Abstract:
Orientador: Carlile Campos Lavor
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica
Made available in DSpace on 2018-08-11T07:27:34Z (GMT). No. of bitstreams: 1 Alves_RafaelSantosdeOliveira_M.pdf: 2108746 bytes, checksum: 26f9217f1127ef34f9a7ae1692c995b8 (MD5) Previous issue date: 2008
Resumo: O Algoritmo de Grover é um algoritmo quântico de busca em um conjunto desordenado. Com o uso de propriedades da mecânica quântica, ele apresenta um ganho quadrático em relação a um algoritmo clássico. Neste trabalho, apresentamos uma outra visão deste algoritmo, através da Álgebra Geométrica, motivados pela interpretação geométrica dos operadores, e verificamos que é possível escrevê-lo com uma nova linguagem, e ainda apresentar uma expressão mais simples para o operador de Grover (G) além de expressões gerais para estados resultantes de aplicações sucessivas deste operador
Abstract: Grover¿s algorithm is a quantum algorithm for searching in unstructured databases. Due to the properties of quantum mechanics, it provides a quadratic speedup over their classical counterparts. Using the Geometric Algebra, we present a new way to understand and simplify the operators of Grover¿s algorithm
Mestrado
Computação Quantica
Mestre em Matemática Aplicada
APA, Harvard, Vancouver, ISO, and other styles
32

Rashed, Shawki al [Verfasser], and Gerhard [Akademischer Betreuer] Pfister. "Numerical Algorithms in Algebraic Geometry with Implementation in Computer Algebra System SINGULAR / Shawki Al-Rashed. Betreuer: Gerhard Pfister." Kaiserslautern : Universitätsbibliothek Kaiserslautern, 2011. http://d-nb.info/1017757763/34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
33

Li, Wenda. "Towards justifying computer algebra algorithms in Isabelle/HOL." Thesis, University of Cambridge, 2019. https://www.repository.cam.ac.uk/handle/1810/289389.

Full text
Abstract:
As verification efforts using interactive theorem proving grow, we are in need of certified algorithms in computer algebra to tackle problems over the real numbers. This is important because uncertified procedures can drastically increase the size of the trust base and under- mine the overall confidence established by interactive theorem provers, which usually rely on a small kernel to ensure the soundness of derived results. This thesis describes an ongoing effort using the Isabelle theorem prover to certify the cylindrical algebraic decomposition (CAD) algorithm, which has been widely implemented to solve non-linear problems in various engineering and mathematical fields. Because of the sophistication of this algorithm, people are in doubt of the correctness of its implementation when deploying it to safety-critical verification projects, and such doubts motivate this thesis. In particular, this thesis proposes a library of real algebraic numbers, whose distinguishing features include a modular architecture and a sign determination algorithm requiring only rational arithmetic. With this library, an Isabelle tactic based on univariate CAD has been built in a certificate-based way: external, untrusted code delivers solutions in the form of certificates that are checked within Isabelle. To lay the foundation for the multivariate case, I have formalised various analytical results including Cauchy's residue theorem and the bivariate case of the projection theorem of CAD. During this process, I have also built a tactic to evaluate winding numbers through Cauchy indices and verified procedures to count complex roots in some domains. The formalisation effort in this thesis can be considered as the first step towards a certified computer algebra system inside a theorem prover, so that various engineering projections and mathematical calculations can be carried out in a high-confidence framework.
APA, Harvard, Vancouver, ISO, and other styles
34

Solomonik, Edgar. "Provably Efficient Algorithms for Numerical Tensor Algebra." Thesis, University of California, Berkeley, 2015. http://pqdtopen.proquest.com/#viewpdf?dispub=3686016.

Full text
Abstract:

This thesis targets the design of parallelizable algorithms and communication-efficient parallel schedules for numerical linear algebra as well as computations with higher-order tensors. Communication is a growing bottleneck in the execution of most algorithms on parallel computers, which manifests itself as data movement both through the network connecting different processors and through the memory hierarchy of each processor as well as synchronization between processors. We provide a rigorous theoretical model of communication and derive lower bounds as well as algorithms in this model. Our analysis concerns two broad areas of linear algebra and of tensor contractions. We demonstrate the practical quality of the new theoretically-improved algorithms by presenting results which show that our implementations outperform standard libraries and traditional algorithms.

We model the costs associated with local computation, interprocessor communication and synchronization, as well as memory to cache data transfers of a parallel schedule based on the most expensive execution path in the schedule. We introduce a new technique for deriving lower bounds on tradeoffs between these costs and apply them to algorithms in both dense and sparse linear algebra as well as graph algorithms. These lower bounds are attained by what we refer to as 2.5D algorithms, which we give for matrix multiplication, Gaussian elimination, QR factorization, the symmetric eigenvalue problem, and the Floyd-Warshall all-pairs shortest-paths algorithm. 2.5D algorithms achieve lower interprocessor bandwidth cost by exploiting auxiliary memory. Algorithms employing this technique are well known for matrix multiplication, and have been derived in the BSP model for LU and QR factorization, as well as the Floyd-Warshall algorithm. We introduce alternate versions of LU and QR algorithms which have measurable performance improvements over their BSP counterparts, and we give the first evaluations of their performance. We also explore network-topology-aware mapping on torus networks for matrix multiplication and LU, showing how 2.5D algorithms can efficiently exploit collective communication, as well as introducing an adaptation of Cannon's matrix multiplication algorithm that is better suited for torus networks with dimension larger than two. For the symmetric eigenvalue problem, we give the first 2.5D algorithms, additionally solving challenges with memory-bandwidth efficiency that arise for this problem. We also give a new memory-bandwidth efficient algorithm for Krylov subspace methods (repeated multiplication of a vector by a sparse-matrix), which is motivated by the application of our lower bound techniques to this problem.

The latter half of the thesis contains algorithms for higher-order tensors, in particular tensor contractions. The motivating application for this work is the family of coupled-cluster methods, which solve the many-body Schrödinger equation to provide a chemically-accurate model of the electronic structure of molecules and chemical reactions where electron correlation plays a significant role. The numerical computation of these methods is dominated in cost by contraction of antisymmetric tensors. We introduce Cyclops Tensor Framework, which provides an automated mechanism for network-topology-aware decomposition and redistribution of tensor data. It leverages 2.5D matrix multiplication to perform tensor contractions communication-efficiently. The framework is capable of exploiting symmetry and antisymmetry in tensors and utilizes a distributed packed-symmetric storage format. Finally, we consider a theoretically novel technique for exploiting tensor symmetry to lower the number of multiplications necessary to perform a contraction via computing some redundant terms that allow preservation of symmetry and then cancelling them out with low-order cost. We analyze the numerical stability and communication efficiency of this technique and give adaptations to antisymmetric and Hermitian matrices. This technique has promising potential for accelerating coupled-cluster methods both in terms of computation and communication cost, and additionally provides a potential improvement for BLAS routines on complex matrices.

APA, Harvard, Vancouver, ISO, and other styles
35

Kung, Chun Pang. "Intelligent algorithms for an algebra tutoring system." Thesis, Liverpool John Moores University, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.402846.

Full text
APA, Harvard, Vancouver, ISO, and other styles
36

Holloway, Nick. "Parallel algorithms in graph theory and algebra." Thesis, University of Warwick, 1994. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.338724.

Full text
APA, Harvard, Vancouver, ISO, and other styles
37

Yelkenci, Serhat. "Algorithmic Music Composition Using Linear Algebra." Thesis, Southern Illinois University at Edwardsville, 2017. http://pqdtopen.proquest.com/#viewpdf?dispub=10275073.

Full text
Abstract:

Sound, in its all forms, is a source of energy whose capabilities humankind is not yet fully aware of. Composition - the way of aggregating sounds into the form of music - still holds to be an unperceived methodology with lots of unknowns. Methodologies used by composers are generally seem as being innate talent, something that cannot be used or shared by others. Yet, as any other form of art, music actually is and can be interpreted with mathematics and geometry. The focus of this thesis is to propose a generative algorithm to compose structured music pieces using linear algebra as the mathematical language for the representation of music. By implementing the linear algebra as the scientific framework, a practical data structure is obtained for analysis and manipulation. Instead of defining a single structure from a certain musical canon, which is a type of limiting the frame of music, the generative algorithm proposed in this paper is capable of learning all kinds of musical structures by linear algebra operations. The algorithm is designed to build musical knowledge (influence) by analyzing music pieces and receive a new melody as the inspirational component to produce new unique and meaningful music pieces. Characteristic analysis features obtained from analyzing music pieces, serves as constraints during the composition process. The proposed algorithm has been successful in generating unique and meaningful music pieces. The process time of the algorithm varies due to complexity of the influential aspect. Yet, the free nature of the generative algorithm and the capability of matrical representation offer a practical linkage between unique and meaningful music creation and any other concept containing a mathematical foundation.

APA, Harvard, Vancouver, ISO, and other styles
38

Hein, Birgit. "Quantum search algorithms." Thesis, University of Nottingham, 2010. http://eprints.nottingham.ac.uk/11512/.

Full text
Abstract:
In this thesis two quantum search algorithms on two different graphs, a hypercube and a d-dimensional square lattice, are analysed and some applications of the lattice search are discussed. The approach in this thesis generalises a picture drawn by Shenvi, Kempe and Whaley, which was later adapted by Ambainis, Kempe and Rivosh. It defines a one parameter family of unitary operators U_λ with parameter λ. It will be shown that two eigenvalues of U_λ form an avoided crossing at the λ-value where U_λ is equal to the old search operator. This generalised picture opens the way for a construction of two approximate eigen- vectors at the crossing and gives rise to a 2×2 model Hamiltonian that is used to approximate the operator U_λ near the crossing. The thus defined Hamiltonian can be used to calculate the leading order of search time and success probability for the search. To the best of my knowledge only the scaling of these quantities has been known. For the algorithm searching the regular lattice, a generalisation of the model Hamiltonian for m target vertices is constructed. This algorithm can be used to send a signal from one vertex of the graph to a set of vertices. The signal is transmitted between these vertices exclusively and is localised only on the sender and the receiving vertices while the probability to measure the signal at one of the remaining vertices is significantly smaller. However, this effect can be used to introduce an additional sender to search settings and send a continuous signal to all target vertices where the signal will localise. This effect is an improvement compared to the original search algorithm as it does not need to know the number of target vertices.
APA, Harvard, Vancouver, ISO, and other styles
39

Struble, Craig Andrew. "Analysis and Implementation of Algorithms for Noncommutative Algebra." Diss., Virginia Tech, 2000. http://hdl.handle.net/10919/27393.

Full text
Abstract:
A fundamental task of algebraists is to classify algebraic structures. For example, the classification of finite groups has been widely studied and has benefited from the use of computational tools. Advances in computer power have allowed researchers to attack problems never possible before. In this dissertation, algorithms for noncommutative algebra, when ab is not necessarily equal to ba, are examined with practical implementations in mind. Different encodings of associative algebras and modules are also considered. To effectively analyze these algorithms and encodings, the encoding neutral analysis framework is introduced. This framework builds on the ideas used in the arithmetic complexity framework defined by Winograd. Results in this dissertation fall into three categories: analysis of algorithms, experimental results, and novel algorithms. Known algorithms for calculating the Jacobson radical and Wedderburn decomposition of associative algebras are reviewed and analyzed. The algorithms are compared experimentally and a recommendation for algorithms to use in computer algebra systems is given based on the results. A new algorithm for constructing the Drinfel'd double of finite dimensional Hopf algebras is presented. The performance of the algorithm is analyzed and experiments are performed to demonstrate its practicality. The performance of the algorithm is elaborated upon for the special case of group algebras and shown to be very efficient. The MeatAxe algorithm for determining whether a module contains a proper submodule is reviewed. Implementation issues for the MeatAxe in an encoding neutral environment are discussed. A new algorithm for constructing endomorphism rings of modules defined over path algebras is presented. This algorithm is shown to have better performance than previously used algorithms. Finally, a linear time algorithm, to determine whether a quotient of a path algebra, with a known Gröbner basis, is finite or infinite dimensional is described. This algorithm is based on the Aho-Corasick pattern matching automata. The resulting automata is used to efficiently determine the dimension of the algebra, enumerate a basis for the algebra, and reduce elements to normal forms.
Ph. D.
APA, Harvard, Vancouver, ISO, and other styles
40

Kaur, Amandeep. "Analytic and numerical aspects of isospectral flows." Thesis, University of Cambridge, 2018. https://www.repository.cam.ac.uk/handle/1810/270631.

Full text
Abstract:
In this thesis we address the analytic and numerical aspects of isospectral flows. Such flows occur in mathematical physics and numerical linear algebra. Their main structural feature is to retain the eigenvalues in the solution space. We explore the solution of Isospectral flows and their stochastic counterpart using explicit generalisation of Magnus expansion. \par In the first part of the thesis we expand the solution of Bloch--Iserles equations, the matrix ordinary differential system of the form $ X'=[N,X^{2}],\ \ t\geq0, \ \ X(0)=X_0\in \textrm{Sym}(n),\ N\in \mathfrak{so}(n), $ where $\textrm{Sym}(n)$ denotes the space of real $n\times n$ symmetric matrices and $\mathfrak{so}(n)$ denotes the Lie algebra of real $n\times n$ skew-symmetric matrices. This system is endowed with Poisson structure and is integrable. Various important properties of the flow are discussed. The flow is solved using explicit Magnus expansion and the terms of expansion are represented as binary rooted trees deducing an explicit formalism to construct the trees recursively. Unlike classical numerical methods, e.g.\ Runge--Kutta and multistep methods, Magnus expansion respects the isospectrality of the system, and the shorthand of binary rooted trees reduces the computational cost of the exponentially growing terms. The desired structure of the solution (also with large time steps) has been displayed. \par Having seen the promising results in the first part of the thesis, the technique has been extended to the generalised double bracket flow $ X^{'}=[[N,X]+M,X], \ \ t\geq0, \ \ X(0)=X_0\in \textrm{Sym}(n),$ where $N\in \textrm{diag}(n)$ and $M\in \mathfrak{so}(n)$, which is also a form of an Isospectral flow. In the second part of the thesis we define the generalised double bracket flow and discuss its dynamics. It is noted that $N=0$ reduces it to an integrable flow, while for $M=0$ it results in a gradient flow. We analyse the flow for various non-zero values of $N$ and $M$ by assigning different weights and observe Hopf bifurcation in the system. The discretisation is done using Magnus series and the expansion terms have been portrayed using binary rooted trees. Although this matrix system appears more complex and leads to the tri-colour leaves; it has been possible to formulate the explicit recursive rule. The desired structure of the solution is obtained that leaves the eigenvalues invariant in the solution space.
APA, Harvard, Vancouver, ISO, and other styles
41

Shibalovich, Paul. "Fundamental theorem of algebra." CSUSB ScholarWorks, 2002. https://scholarworks.lib.csusb.edu/etd-project/2203.

Full text
Abstract:
The fundamental theorem of algebra (FTA) is an important theorem in algebra. This theorem asserts that the complex field is algebracially closed. This thesis will include historical research of proofs of the fundamental theorem of algebra and provide information about the first proof given by Gauss of the theorem and the time when it was proved.
APA, Harvard, Vancouver, ISO, and other styles
42

Weihrauch, Christian. "Analysis of Monte Carlo algorithms for linear algebra problems." Thesis, University of Reading, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.515747.

Full text
APA, Harvard, Vancouver, ISO, and other styles
43

Jain, Kamal. "Enhancing techniques in LP based approximation algorithms." Diss., Georgia Institute of Technology, 2000. http://hdl.handle.net/1853/8188.

Full text
APA, Harvard, Vancouver, ISO, and other styles
44

Wallgren, Anton. "Treewidth of Graphs and Algorithmic Implications." Thesis, Uppsala universitet, Algebra och geometri, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-428635.

Full text
APA, Harvard, Vancouver, ISO, and other styles
45

Iakymchuk, Roman [Verfasser]. "Performance modeling and prediction for linear algebra algorithms / Roman Iakymchuk." Aachen : Hochschulbibliothek der Rheinisch-Westfälischen Technischen Hochschule Aachen, 2012. http://d-nb.info/1026308690/34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
46

Milne, Philip S. "On the algorithms and implementation of a geometric algebra system." Thesis, University of Bath, 1990. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.236564.

Full text
APA, Harvard, Vancouver, ISO, and other styles
47

Sato, Hiroyuki. "Riemannian Optimization Algorithms and Their Applications to Numerical Linear Algebra." 京都大学 (Kyoto University), 2013. http://hdl.handle.net/2433/180615.

Full text
APA, Harvard, Vancouver, ISO, and other styles
48

Ferrari, Luca <1985&gt. "Permutation classes, sorting algorithms, and lattice paths." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2013. http://amsdottorato.unibo.it/6032/.

Full text
Abstract:
A permutation is said to avoid a pattern if it does not contain any subsequence which is order-isomorphic to it. Donald Knuth, in the first volume of his celebrated book "The art of Computer Programming", observed that the permutations that can be computed (or, equivalently, sorted) by some particular data structures can be characterized in terms of pattern avoidance. In more recent years, the topic was reopened several times, while often in terms of sortable permutations rather than computable ones. The idea to sort permutations by using one of Knuth’s devices suggests to look for a deterministic procedure that decides, in linear time, if there exists a sequence of operations which is able to convert a given permutation into the identical one. In this thesis we show that, for the stack and the restricted deques, there exists an unique way to implement such a procedure. Moreover, we use these sorting procedures to create new sorting algorithms, and we prove some unexpected commutation properties between these procedures and the base step of bubblesort. We also show that the permutations that can be sorted by a combination of the base steps of bubblesort and its dual can be expressed, once again, in terms of pattern avoidance. In the final chapter we give an alternative proof of some enumerative results, in particular for the classes of permutations that can be sorted by the two restricted deques. It is well-known that the permutations that can be sorted through a restricted deque are counted by the Schrӧder numbers. In the thesis, we show how the deterministic sorting procedures yield a bijection between sortable permutations and Schrӧder paths.
APA, Harvard, Vancouver, ISO, and other styles
49

Simard, Carole. "Relational algebra on a parallel-sort database machine." Thesis, McGill University, 1985. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=63225.

Full text
APA, Harvard, Vancouver, ISO, and other styles
50

Brunet, Paul. "Algebras of Relations : from algorithms to formal proofs." Thesis, Lyon, 2016. http://www.theses.fr/2016LYSE1198/document.

Full text
Abstract:
Les algèbres de relations apparaissent naturellement dans de nombreux cadres, en informatique comme en mathématiques. Elles constituent en particulier un formalisme tout à fait adapté à la sémantique des programmes impératifs. Les algèbres de Kleene constituent un point de départ : ces algèbres jouissent de résultats de décidabilités très satisfaisants, et admettent une axiomatisation complète. L'objectif de cette thèse a été d'étendre les résultats connus sur les algèbres de Kleene à des extensions de celles-ci.Nous nous sommes tout d'abord intéressés à une extension connue : les algèbres de Kleene avec converse. La décidabilité de ces algèbres était déjà connue, mais l'algorithme prouvant ce résultat était trop compliqué pour être utilisé en pratique. Nous avons donné un algorithme plus simple, plus efficace, et dont la correction est plus facile à établir. Ceci nous a permis de placer ce problème dans la classe de complexité PSpace-complete.Nous avons ensuite étudié les allégories de Kleene. Sur cette extension, peu de résultats étaient connus. En suivant des résultats sur des algèbres proches, nous avons établi l'équivalence du problème d'égalité dans les allégories de Kleene à l'égalité de certains ensembles de graphes. Nous avons ensuite développé un modèle d'automate original (les automates de Petri), basé sur les réseaux de Petri, et avons établi l'équivalence de notre problème original avec le problème de comparaison de ces automates. Nous avons enfin développé un algorithme pour effectuer cette comparaison dans le cadre restreint des treillis de Kleene sans identité. Cet algorithme utilise un espace exponentiel. Néanmoins, nous avons pu établir que la comparaison d'automates de Petri dans ce cas est ExpSpace-complète. Enfin, nous nous sommes intéressés aux algèbres de Kleene Nominales. Nous avons réalisé que les descriptions existantes de ces algèbres n'étaient pas adaptées à la sémantique relationnelle des programmes. Nous les avons donc modifiées pour nos besoins, et ce faisant avons trouvé diverses variations naturelles de ce modèle. Nous avons donc étudié en détails et en Coq les ponts que l'on peut établir entre ces variantes, et entre le modèle “classique” et notre nouvelle version
Algebras of relations appear naturally in many contexts, in computer science as well as in mathematics. They constitute a framework well suited to the semantics of imperative programs. Kleene algebra are a starting point: these algebras enjoy very strong decidability properties, and a complete axiomatisation. The goal of this thesis was to export known results from Kleene algebra to some of its extensions. We first considered a known extension: Kleene algebras with converse. Decidability of these algebras was already known, but the algorithm witnessing this result was too complicated to be practical. We proposed a simpler algorithm, more efficient, and whose correctness is easier to establish. It allowed us to prove that this problem lies in the complexity class PSpace-complete.Then we studied Kleene allegories. Few results were known about this extension. Following results about closely related algebras, we established the equivalence between equality in Kleene allegories and equality of certain sets of graphs. We then developed an original automaton model (so-called Petri automata), based on Petri nets. We proved the equivalence between the original problem and comparing these automata. In the restricted setting of identity-free Kleene lattices, we also provided an algorithm performing this comparison. This algorithm uses exponential space. However, we proved that the problem of comparing Petri automata lies in the class ExpSpace-complete.Finally, we studied Nominal Kleene algebras. We realised that existing descriptions of these algebra were not suited to relational semantics of programming languages. We thus modified them accordingly, and doing so uncovered several natural variations of this model. We then studied formally the bridges one could build between these variations, and between the existing model and our new version of it. This study was conducted using the proof assistant Coq
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the bibliographies on the topic 'Algorithm algebra' for other source types:
Journal articles Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography