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.

O objetivo deste trabalho e computar, em alguns casos espec cos, os geradores do radical de um ideal no anel de polinômios K[x1, ..., xn]. Para isso, utilizamos a teoria das bases de Groebner. Primeiramente, usamos o Lema de Seidenberg para computar os geradores do radical de um ideal zero-dimensional onde K e um corpo perfeito e depois utilizamos os resultados de R. Matsumoto para um corpo K de caracter stica positiva e perfeito. / The goal of this work is to compute in some speci c cases the generators of the radical ideal in a polynomial ring K[x1, ..., xn]. For this, we use the theory of Groebner bases. First, we use Lemma Seidenberg to compute the generators of the radical of an zero-dimensional ideal, where K is a perfect eld and then we used the results of R. Matsumoto for a eld K of positive characteristic and perfect.

O objetivo deste trabalho e computar, em alguns casos espec cos, os geradores do radical de um ideal no anel de polinômios K[x1, ..., xn]. Para isso, utilizamos a teoria das bases de Groebner. Primeiramente, usamos o Lema de Seidenberg para computar os geradores do radical de um ideal zero-dimensional onde K e um corpo perfeito e depois utilizamos os resultados de R. Matsumoto para um corpo K de caracter stica positiva e perfeito. / The goal of this work is to compute in some speci c cases the generators of the radical ideal in a polynomial ring K[x1, ..., xn]. For this, we use the theory of Groebner bases. First, we use Lemma Seidenberg to compute the generators of the radical of an zero-dimensional ideal, where K is a perfect eld and then we used the results of R. Matsumoto for a eld K of positive characteristic and perfect.

O objetivo deste trabalho e computar, em alguns casos espec cos, os geradores do radical de um ideal no anel de polinômios K[x1, ..., xn]. Para isso, utilizamos a teoria das bases de Groebner. Primeiramente, usamos o Lema de Seidenberg para computar os geradores do radical de um ideal zero-dimensional onde K e um corpo perfeito e depois utilizamos os resultados de R. Matsumoto para um corpo K de caracter stica positiva e perfeito. / The goal of this work is to compute in some speci c cases the generators of the radical ideal in a polynomial ring K[x1, ..., xn]. For this, we use the theory of Groebner bases. First, we use Lemma Seidenberg to compute the generators of the radical of an zero-dimensional ideal, where K is a perfect eld and then we used the results of R. Matsumoto for a eld K of positive characteristic and perfect.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / In this work, we present a special class of linear codes: parameterized affine codes. We show that these codes are easy to construct and that given a parameterized affine code one can easily obtain an equivalent projective parameterized code equivalent to it. We also studied some topics which served as the theoretical foundations for the work, such as the theory of Groebner Bases, the footprint of an ideal and some topics of algebraic geometry and commutative algebra. This work has as main goal to obtain the basic parameters (length, dimension and minimum distance) of parameterized codes related and also to relate them to the projective parameterized codes, as done in [7]. We finish by applying the theory of Groebner Bases to the footprint of a certain ideal in order to obtain the basic parameters of the parameterized code over an affine torus. / Neste trabalho apresentamos uma classe especial de códigos lineares: os códigos parametrizados afins. Mostramos que esses códigos são de fácil construção e que, dado um código parametrizado afim, pode-se facilmente obter um código parametrizado projetivo equivalente a ele. Também estudamos algumas teorias que nos serviram como base teórica tais como: a teoria de Bases de Groebner e a Pegada de um ideal e alguns tópicos de geometria algébrica e álgebra comutativa. Este trabalho tem por objetivo principal obter os parâmetros básicos (comprimento, dimensão e distância mínima) dos códigos parametrizados afins e relacioná-los com os códigos parametrizados projetivos, assim como na referência [7]. Encerramos aplicando a teoria de Bases de Groebner a Pegada de um ideal para obter os parâmetros básicos do código parametrizado no toro afim. / Mestre em Matemática

Le problème d’´équivalence de code joue un rôle important dans la théorie de code et la cryptographie basée sur le code. Cela est dû à son importance dans la classification des codes ainsi que dans la construction et la cryptanalyse des cryptosystèmes à base de codes. Il est également lié à un problème ouvert d’isomorphisme de graphes, un problème bien connu dans le domaine de la théorie de la complexité. Nous prouvons pour les codes ayant un hull trivial qu’il existe une réduction polynomiale de l’équivalence par permutation de codes à l’isomorphisme de graphes. Cela montre que cette sous-classe d’équivalence de permutation n’est pas plus dure que l’isomorphisme de graphes. Nous introduisons une nouvelle méthode pour résoudre le problème d’équivalence de code. Nous développons des approches algébriques pour résoudre le problème dans ses deux versions : en permutation et en diagonale. Nous construisons un système algébrique en établissant des relations entre les matrices génératrices et les matrices de parité des codes équivalents. Nous nous retrouvons avecun système plusieurs variables d’équations linéaires et quadratiques qui peut être résolu en utilisant des outils algébriques tels que les bases de Groebner et les techniques associées. Il est possible en théorie de résoudre l’équivalence de code avec des techniques utilisant des bases de Groebner. Cependant, le calcul en pratique devient complexe à mesure que la longueur du code augmente. Nous avons introduit plusieurs améliorations telles que la linéarisation par bloc et l’action de Frobenius. En utilisant ces techniques, nous identifions de nombreux cas où le problème d’équivalence de permutation peut être résolu efficacement. Notre méthode d’équivalence diagonale résout efficacement le problème dans les corps de petites tailles, à savoir F3 et F4. L’augmentation de la taille du corps entraîne une augmentation du nombre de variables dans notre système algébrique, ce qui le rend difficile à résoudre. Nous nous intéressons enfin au problème d’isomorphisme de graphes en considérant un système algébrique quadratique pour l’isomorphisme de graphes. Pour des instances tirées aléatoirement, le système possède des propriétés intéressantes en termes de rang de la partie linéaire et du nombre de variables. Nousrésolvons efficacement le problème d’isomorphisme de graphes pour des graphes aléatoires avec un grand nombre de sommets, et également pour certains graphes réguliers tels que ceux de Petersen, Cubical et Wagner.123 / Code equivalence problem plays an important role in coding theory and code based cryptography.That is due to its significance in classification of codes and also construction and cryptanalysis of code based cryptosystems. It is also related to the long standing problem of graph isomorphism, a well-known problem in the world of complexity theory. We introduce new method for solving code equivalence problem. We develop algebraic approaches to solve the problem in its permutation and diagonal versions. We build algebraic system by establishing relations between generator matrices and parity check matrices of the equivalent codes. We end up with system of multivariables of linear and quadratic equations which can be solved using algebraic tools such as Groebner basis and related techniques. By using Groebner basis techniques we can solve the code equivalence but the computation becomes complex as the length of the code increases. We introduced several improvements such as block linearization and Frobenius action. Using these techniques we identify many cases where permutation equivalence problem can be solved efficiently. Our method for diagonal equivalence solves the problem efficiently in small fields, namely F3 and F4. The increase in the field size results in an increase in the number of variables in our algebraic system which makes it difficult to solve. We introduce a new reduction from permutation code equivalence when the hull is trivial to graph isomorphism. This shows that this subclass of permutation equivalence is not harder than graph isomorphism.Using this reduction we obtain an algebraic system for graph isomorphism with interesting properties in terms of the rank of the linear part and the number of variables. We solve the graph isomorphism problem efficiently for random graphs with large number of vertices and also for some regular graphs such as Petersen, Cubical and Wagner Graphs.

Groebner-Shirshov bases, introduced independently by Shirshov in 1962 and Buchberger in 1965, are powerful computational tools in mathematics, science, engineering, and computer science. This thesis focuses on the theories, algorithms, and applications of Groebner-Shirshov bases for two classes of noncommutative algebras: differential difference algebras and skew solvable polynomial rings. This thesis consists of three manuscripts (Chapters 2--4), an introductory chapter (Chapter 1) and a concluding chapter (Chapter 5). In Chapter 1, we introduce the background and the goals of the thesis. In Chapter 2, we investigate the Gelfand-Kirillov dimension of differential difference algebras. We find lower and upper bounds of the Gelfand-Kirillov dimension of a differential difference algebra under some conditions. We also give examples to demonstrate that our bounds are sharp. In Chapter 3, we generalize the Groebner-Shirshov basis theory to differential difference algebras with respect to any left admissible ordering and develop the Groebner-Shirshov basis theory of finitely generated free modules over differential difference algebras. By using the theory we develop, we present an algorithm to compute the Gelfand-Kirillov dimensions of finitely generated modules over differential difference algebras. In Chapter 4, we first define skew solvable polynomial rings, which are generalizations of solvable polynomial algebras and (skew) PBW extensions. Then we present a signature-based algorithm for computing Groebner-Shirshov bases in skew solvable polynomial rings over fields. Our algorithm can detect redundant reductions and therefore it is more efficient than the traditional Buchberger algorithm. Finally, in Chapter 5, we summarize our results and propose possible future work.

The field of algebraic tropical geometry establishes a deep connection between algebraic geometry and combinatorics by associating to certain classical algebraic varieties so called tropical varieties, which are polyhedral complexes in some real vectorspaces. Tropical varieties are closely related to the Groebner complexes of the ideal defining the classical variety. In this thesis the tropical variety of an ideal is studied under a generic change of coodinates. Analogously to the existence of generic initial ideals the existence of generic Groebner complexes and generic tropical varieties is proved. Moreover, it is shown that in the constant coefficient case information on the invariants dimension, Hilbert-Samuel multiplicity and depth of the corresponding coordinate rings can be obtained from generic tropical varieties.

No description available.

We develop a public key cryptosystem whose security is based on the intractability of the ideal membership problem for a noncommutative algebra over a finite field. We show that this system, which is the noncommutative analogue of the Polly Cracker cryptosystem, is more secure than the commutative version. This is due to the fact that there are a number of ideals of noncommutative algebras (over finite fields) that have infinite reduced Groebner bases, and can be used to generate a public key. We present classes of such ideals and prove that they do not have a finite Groebner basis under any admissible order. We also examine various techniques to realize finite Groebner bases, in order to determine whether these ideals can be used effectively in the design of a public key cryptosystem. We then show how some of these classes of ideals, which have infinite reduced Groebner bases, can be used to design a public key cryptosystem. We also study various techniques of encryption. Finally, we study techniques of cryptanalysis that may be used to attack the cryptosystems that we present. We show how poorly constructed public keys can in fact, reveal the private key, and discuss techniques to design public keys that adequately conceal the private key. We also show how linear algebra can be used in ciphertext attacks and present a technique to overcome such attacks. This is different from the commutative version of the Polly Cracker cryptosystem, which is believed to be susceptible to "intelligent" linear algebra attacks. / Ph. D.