Search

With this paper we present an extension of our recent ISSAC paper about computations of Gröbner(-Shirshov) bases over free associative algebras Z 〈 X 〉. We present all the needed proofs in details, add a part on the direct treatment of the ring Z / m Z as well as new examples and applications to e.g. Iwahori-Hecke algebras. 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 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 behaviour of Gröbner bases between free algebras and algebras, which are close to commutative. Even the process of the formation of critical pairs has to be reengineered, together with 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 Gröbner bases), due to La Scala and Levandovskyy. Interesting examples and applications accompany our presentation. [ABSTRACT FROM AUTHOR]

Considering a multivariate polynomial ideal over a given field as a vector space, we investigate for such an ideal a particular linear basis, a so-called staggered linear basis, which contains a Gröbner basis as well. In this paper, we present a simple and efficient algorithm to compute a staggered linear basis. The new framework is equipped with some novel criteria (including both Buchberger's criteria) to detect superfluous reductions. The proposed algorithm has been implemented in Maple, and we provide an illustrative example to show how it works. Finally, the efficiency of this algorithm compared to the existing methods is discussed via a set of benchmark polynomials. [ABSTRACT FROM AUTHOR]

Sparse polynomial interpolation, sparse linear system solving or modular rational reconstruction are fundamental problems in Computer Algebra. They come down to computing linear recurrence relations of a sequence with the Berlekamp–Massey algorithm. Likewise, sparse multivariate polynomial interpolation and multidimensional cyclic code decoding require guessing linear recurrence relations of a multivariate sequence. Several algorithms solve this problem. The so-called Berlekamp–Massey–Sakata algorithm (1988) uses polynomial additions and shifts by a monomial. The Scalar-FGLM algorithm (2015) relies on linear algebra operations on a multi-Hankel matrix, a multivariate generalization of a Hankel matrix. The Artinian Gorenstein border basis algorithm (2017) uses a Gram-Schmidt process. We propose a new algorithm for computing the Gröbner basis of the ideal of relations of a sequence based solely on multivariate polynomial arithmetic. This algorithm allows us to both revisit the Berlekamp–Massey–Sakata algorithm through the use of polynomial divisions and to completely revise the Scalar-FGLM algorithm without linear algebra operations. A key observation in the design of this algorithm is to work on the mirror of the truncated generating series allowing us to use polynomial arithmetic modulo a monomial ideal. It appears to have some similarities with Padé approximants of this mirror polynomial. As an addition from the paper published at the ISSAC conference, we give an adaptive variant of this algorithm taking into account the shape of the final Gröbner basis gradually as it is discovered. The main advantage of this algorithm is that its complexity in terms of operations and sequence queries only depends on the output Gröbner basis. All these algorithms have been implemented in Maple and we report on our comparisons. [ABSTRACT FROM AUTHOR]

Consider an action of a connected solvable group G on an affine variety X. This paper presents an algorithm that constructs a semi-invariant f ∈ K [ X ] = : R and computes the invariant ring (R f) G together with a presentation. The morphism X f → Spec ((R f) G) obtained from the algorithm is a universal geometric quotient. In fact, it is even better than that: a so-called excellent quotient. If R is a polynomial ring, the algorithm requires no Gröbner basis computations. If R is a complete intersection, then so is (R f) G. [ABSTRACT FROM AUTHOR]

The W-characteristic set of a polynomial ideal is the minimal triangular set contained in the reduced lexicographical Gröbner basis of the ideal. A pair (G , C) of polynomial sets is a strong regular characteristic pair if G is a reduced lexicographical Gröbner basis, C is the W-characteristic set of the ideal 〈 G 〉 , the saturated ideal sat (C) of C is equal to 〈 G 〉 , and C is regular. In this paper, we show that for any polynomial ideal I with given generators one can either detect that I is unit, or construct a strong regular characteristic pair (G , C) by computing Gröbner bases such that I ⊆ sat (C) = 〈 G 〉 and sat (C) divides I , so the ideal I can be split into the saturated ideal sat (C) and the quotient ideal I : sat (C). Based on this strategy of splitting by means of quotient and with Gröbner basis and ideal computations, we devise a simple algorithm to decompose an arbitrary polynomial set F into finitely many strong regular characteristic pairs, from which two representations for the zeros of F are obtained: one in terms of strong regular Gröbner bases and the other in terms of regular triangular sets. We present some properties about strong regular characteristic pairs and characteristic decomposition and illustrate the proposed algorithm and its performance by examples and experimental results. [ABSTRACT FROM AUTHOR]

In this paper we present new techniques for improving the computation of strong Gröbner bases over a principal ideal ring R. More precisely, we describe how to lift a strong Gröbner basis along a canonical projection R → R / n , n ≠ 0 , and along a ring isomorphism R → R 1 × R 2. We then apply this to the computation of strong Gröbner bases over a non-trivial quotient of a principal ideal domain R / n R. The idea is to run a standard Gröbner basis algorithm pretending R / n R to be field. If we discover a non-invertible leading coefficient c , we use this information to try to split n = a b with coprime a , b. If this is possible, we recursively reduce the original computation to two strong Gröbner bases computations over R / a R and R / b R respectively. If no such c is discovered, the returned Gröbner basis is already a strong Gröbner basis for the input ideal over R / n R. [ABSTRACT FROM AUTHOR]

Given n ⩾ 2 and a 1 , ... , a n ∈ N. Let S = 〈 a 1 , ... , a n 〉 be a semigroup. The aim of this paper is to give an effective pseudo-polynomial algorithm on a 1 , which computes the Apéry set and the Frobenius number of S. We also find the Gröbner basis of the toric ideal defined by S , for the weighted degree reverse lexicographical order ≺ w to x 1 , ... , x n , without using Buchberger's algorithm. As an application we introduce and study some special classes of semigroups. Namely, when S is generated by generalized arithmetic progressions and generalized almost arithmetic progressions with the ratio a positive or a negative number. We determine symmetric and almost symmetric semigroups generated by a generalized arithmetic progression. [ABSTRACT FROM AUTHOR]

In this paper we state and explain techniques useful for the computation of strong Gröbner and standard bases over Euclidean domains: First we investigate several strategies for creating the pair set using an idea by Lichtblau. Then we explain methods for avoiding coefficient growth using syzygies. We give an in-depth discussion on normal form computation resp. a generalized reduction process with many optimizations to further avoid large coefficients. These are combined with methods to reach GCD-polynomials at an earlier stage of the computation. Based on various examples we show that our new implementation in the computer algebra system Singular is, in general, more efficient than other known implementations. [ABSTRACT FROM AUTHOR]

Two new efficient algorithms for computing greatest common divisors (gcds) of parametric multivariate polynomials over k [ U ] [ X ] are presented. The key idea of the first algorithm is that the gcd of two non-parametric multivariate polynomials can be obtained by dividing their product by the generator of the intersection of two principal ideals generated by the polynomials. The second algorithm is based on another simple insight that the gcd can be extracted using the generator of the ideal quotient of a polynomial with respect to the second polynomial. Since the ideal intersection and ideal quotient in these cases are also principal ideals, their generators can be obtained by computing minimal Gröbner bases of the ideal intersection and ideal quotient, respectively. To avoid introducing new variables which can adversely affect the efficiency, minimal Gröbner bases computations are performed on modules. Both of these constructions generalize to the parametric case as shown in the paper. Comprehensive Gröbner system constructions are used for the parametric ideal intersection and ideal quotient using the Kapur-Sun-Wang's algorithm. It is proved that whether in a minimal comprehensive Gröbner system of a parametric ideal intersection or in that of a parametric ideal quotient, each branch of the specializations corresponds to a principal parametric ideal with a single generator. Using this generator, the parametric gcd of that branch is obtained by division. For the case of more than two parametric polynomials, we can use the above two algorithms to compute gcds recursively, and get an extended algorithm by generalizing the idea of the second algorithm. Algorithms do not suffer from having to apply expensive steps such as ensuring whether parametric polynomials are primitive w.r.t. the main variable as used in both the algorithms proposed by Nagasaka (ISSAC, 2017). The resulting algorithms are not only conceptually simple to understand but are more efficient in practice. The proposed algorithms and both of Nagasaka's algorithms have been implemented in Singular, and their performance is compared on a number of examples. [ABSTRACT FROM AUTHOR]

The Berlekamp–Massey–Sakata algorithm and the Scalar-FGLM algorithm both compute the ideal of relations of a multidimensional linear recurrent sequence. Whenever quering a single sequence element is prohibitive, the bottleneck of these algorithms becomes the computation of all the needed sequence terms. As such, having adaptive variants of these algorithms, reducing the number of sequence queries, becomes mandatory. A native adaptive variant of the Scalar-FGLM algorithm was presented by its authors, the so-called Adaptive Scalar-FGLM algorithm. In this paper, our first contribution is to make the Berlekamp–Massey–Sakata algorithm more efficient by making it adaptive to avoid some useless relation testings. This variant allows us to divide by four in dimension 2 and by seven in dimension 3 the number of basic operations performed on some sequence family. Then, we compare the two adaptive algorithms. We show that their behaviors differ in a way that it is not possible to tweak one of the algorithms in order to mimic exactly the behavior of the other. We detail precisely the differences and the similarities of both algorithms and conclude that in general the Adaptive Scalar-FGLM algorithm needs fewer queries and performs fewer basic operations than the Adaptive Berlekamp–Massey–Sakata algorithm. We also show that these variants are always more efficient than the original algorithms. [ABSTRACT FROM AUTHOR]