In this work, we extend modular techniques for computing Gröbner bases involving rational coefficients to (two-sided) ideals in free algebras. We show that the infinite nature of Gröbner bases in this setting renders the classical approach infeasible. Therefore, we propose a new method that relies on signature-based algorithms. Using the data of signatures, we can overcome the limitations of the classical approach and obtain a practical modular algorithm. Moreover, the final verification test in this setting is both more general and more efficient than the classical one. We provide a first implementation of our modular algorithm in SageMath . Initial experiments show that the new algorithm can yield significant speedups over the non-modular approach. We note that our approach can also be applied in more traditional settings, such as commutative polynomial rings.

With this paper we present an extension of our recent ISSAC paper about computations of Groebner(-Shirshov) bases over free associative algebras Z . We present all the needed proofs in details, add a part on the direct treatment of the ring Z/mZ as well as new examples and applications to e.g. Iwahori-Hecke algebras.The extension of Groebner bases concept from polynomial algebras over fields to polynomial rings over rings allows to tackle numerous applications, both of theoretical and of practical importance.Groebner and Groebner-Shirshov bases can be defined for various non-commutative and even non-associative algebraic structures. We study the case of associative rings and aim at free algebras over principal ideal rings. We concentrate ourselves on the case of commutative coefficient rings without zero divisors (i.e. a domain). Even working over Z allows one to do computations, which can be treated as universal for fields of arbitrary characteristic. By using the systematic approach, we revisit the theory and present the algorithms in the implementable form. We show drastic differences in the behavior of Groebner bases between free algebras and algebras, close to commutative.Even the process of the formation of critical pairs has to be reengineered, together with the implementing the criteria for their quick discarding.We present an implementation of algorithms in the Singular subsystem called Letterplace, which internally uses Letterplace techniques (and Letterplace Groebner bases), due to La Scala and Levandovskyy. Interesting examples and applications accompany our presentation.

The symmetries of a finite graph are described by its automorphism group; in the setting of Woronowicz's quantum groups, a notion of a quantum automorphism group has been defined by Banica capturing the quantum symmetries of the graph. In general, there are more quantum symmetries than symmetries and it is a non-trivial task to determine when this is the case for a given graph: The question is whether or not the associative algebra associated to the quantum automorphism group is commutative. We use noncommutative Gröbner bases in order to tackle this problem; the implementation uses Gap and Singular:Letterplace. We determine the existence of quantum symmetries for all connected, undirected graphs without multiple edges and without self-edges, for up to seven vertices. As an outcome, we infer within our regime that a classical automorphism group of order one or two is an obstruction for the existence of quantum symmetries.

The extension of Gröbner bases concept from polynomial algebras over fields to polynomial rings over rings allows to tackle numerous applications, both of theoretical and of practical importance. Gröbner and Gröbner-Shirshov bases can be defined for various non-commutative and even non-associative algebraic structures. We study the case of associative rings and aim at free algebras over principal ideal rings. We concentrate ourselves on the case of commutative coefficient rings without zero divisors (i.e. a domain). Even working over Z allows one to do computations, which can be treated as universal for fields of arbitrary characteristic. By using the systematic approach, we revisit the theory and present the algorithms in the implementable form. We show drastic differences in the behavior of Gröbner bases between free algebras and algebras, close to commutative. Even the formation of critical pairs has to be reengineered, together with the criteria for their quick discarding. We present an implementation of algorithms in the Singular subsystem called Letterplace, which internally uses Letterplace techniques (and Letterplace Gröbner bases), due to La Scala and Levandovskyy. Interesting examples accompany our presentation.

We present the newest release of the subsystem of Singular called Letterplace which exists since 2009. It is devoted to computations with finitely presented associative algebras over fields and offers Gröbner(-Shirshov) bases over free algebras via the Letterplace correspondence of La Scala and Levandovskyy. This allows to use highly tuned commutative data structures internally and to reuse parts of existing algorithms in the non-commutative situation. The present version has been deeply reengineered, based on the experience with earlier and experimental versions. We offer an unprecedented functionality, some of which for the first time in the history of computer algebra. In particular, we present tools for elimination theory (via truncated Gröbner bases and via supporting several kinds of elimination orderings), dimension theory (Gel'fand-Kirillov and global dimension), and for homological algebra (such as syzygy bimodules and lifts for ideals and bimodules) to name a few. Another article in this issue is devoted to the extension of Gröbner bases to the coefficients in principal ideal rings including Z, which is also a part of this release. We report on comparison with other systems and on some advances in the theory. Quite nontrivial examples illustrate the abilities of the system.

We continue the investigations of the constructivity of arithmetics within non-commutative Ore localizations, initiated in our 2017 ISSAC paper, where we have introduced monoidal, geometric and rational types of localizations of domains as objects of our studies. Here we extend this classification to rings with zero divisors and consider Ore sets of the mentioned types which are commutative enough: such a set either belongs to a commutative algebra or it is central or its elements commute pairwise. By using the systematic approach we have developed before, we prove that arithmetic within the localization of a commutative polynomial algebra is constructive and give the necessary algorithms. We also address the important question of computing the local closure of ideals which is also known as the desingularization. We provide algorithms to compute such closures for certain non-commutative rings with respect to Ore sets with enough commutativity.

Classical results of Ore from the 1930's show that a localization of a domain R with respect to a multiplicatively closed set S exists if S satisfies the left Ore property. We investigate the arithmetics of the localized ring S-1R from both theoretical and practical points of view. A major obstacle is the computation of the intersection of a left ideal with a submonoid S of R, which can be overcome by requiring S to be equipped with additional structure. Therefore we distill three most frequently occurring types of Ore sets and provide partial solutions to the mentioned problem for these types. We provide an implementation of arithmetics over the ubiquitous G-algebras in Singular:Plural and discuss algorithmic and theoretic questions in this context.

It has been recently discovered by Bell, Heinle and Levandovskyy that a large class of algebras, including the ubiquitous G-algebras, are finite factorization domains (FFD for short).

In this paper, we present a new algorithm and an experimental implementation for factoring elements in the polynomial nth Weyl algebra, the polynomial nth shift algebra, and Zn-graded polynomials in the nth q-Weyl algebra.

Recently, the notion of "letterplace correspondence" between ideals in the free associative algebra KX and certain ideals in the so-called letterplace ring KXP has evolved. We continue this research direction, started by La Scala and Levandovskyy, and present novel ideas, supported by the implementation, for effective computations with ideals in the free algebra by utilizing the generalized letterplace correspondance. In particular, we provide a direct algorithm to compute Gröbner bases of non-graded ideals. Surprizingly we realize its behavior as "homogenizing without a homogenization variable". Moreover, we develop new shift-invariant data structures for this family of algorithms and discuss about them.

Algebraic Analysis has been coined as a term in the mid 50's by the Japanese group led by Mikio Sato. In recent years many constructions of Algebraic Analysis have been approached from a computer-algebraic point of view, with algorithms and their implementations. Extension of such an interaction from linear differential operators to linear difference, q-difference, q-differential and other linear operators we call Computer-Algebraic Analysis. The major object of study are systems of linear functional equations, their properties, solutions (including those in terms of generalized functions) and behaviour.

We present a general algorithm for computing an intersection of a left ideal of an associative algebra over a field with a subalgebra, generated by a single element. We show applications of this algorithm in different algebraic situations and describe our implementation in Singular. Among other, we use this algorithm in computational D-module theory for computing e.g. the Bernstein-Sato polynomial of a single polynomial with several approaches. We also present a new method, having no analogues yet, for the computation of the Bernstein-Sato polynomial of an affine variety. Also, we provide a new proof of the algorithm by Briançon-Maisonobe for the computation of the s-parametric annihilator of a polynomial.

We present the new implementation of core functions for the computational D-module theory. It is realized as a library dmod.lib in the computer algebra system Singular. We show both theoretical advances, such as the LOT and checkRoot algorithms as well as the comparison of our implementation with other packages for D-modules in computer algebra systems kan/sm1, Asir and Macaulay. The comparison indicates, that our implementation is among the fastest ones. With our package we are able to solve several challenges in D-module theory and we demonstrate the answers to these problems.

Computation of an intersection of a left ideal with a subalgebra, which is not fully investigated until now, is important for different areas of mathematics.We present an algorithm for the computation of the preimage of a left ideal under a morphism of non-commutative GR-algebras, and show both its abilities and limitations.The main computational tools are the elimination of variables by means of Gröbner bases together with the constructive treatment of opposite algebras and the utilization of a special bimodule structure.

Singular is a computer algebra system developed for efficient computations with polynomials. We describe Plural as an extension of Singular to noncommutative polynomial rings (G--/GR--algebras): to which structures does it apply, the prerequisites to monomial orderings, left- and two--sided Grobner bases. The usual criteria to avoid useless pairs are revisited for their applicability in the case of G--/GR--algebras. Benchmark tests are used to evaluate the concepts compare them with other systems.