Search

In this paper, we present an algorithm that, given a differential operator of order 2, detects if this operator comes from a simpler operator under a non-trivial change of variables. [ABSTRACT FROM AUTHOR]

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]

This paper introduces an algorithmic approach to the analysis of bifurcation of limit cycles from the centers of nonlinear continuous differential systems via the averaging method. We develop three algorithms to implement the averaging method. The first algorithm allows one to transform the considered differential systems to the normal form of averaging. Here, we restricted the unperturbed term of the normal form of averaging to be identically zero. The second algorithm is used to derive the computational formulae of the averaged functions at any order. The third algorithm is based on the first two algorithms and determines the exact expressions of the averaged functions for the considered differential systems. The proposed approach is implemented in Maple and its effectiveness is shown by several examples. Moreover, we report some incorrect results in published papers on the averaging method. [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]

Holonomic sequences are widely studied as many objects interesting to mathematicians and computer scientists are in this class. In the univariate case, these are the sequences satisfying linear recurrences with polynomial coefficients and also referred to as D -finite sequences. A subclass are C -finite sequences satisfying a linear recurrence with constant coefficients. We investigate the set of sequences which satisfy linear recurrence equations with coefficients that are C -finite sequences and call them C 2 -finite sequences. These sequences are a natural generalization of holonomic sequences. In this paper, we show that C 2 -finite sequences form a difference ring and provide methods to compute in this ring. Furthermore, we provide an analogous construction for D 2 -finite sequences, i.e., sequences satisfying a linear recurrence with holonomic coefficients. We show that these constructions can be iterated and obtain an increasing chain of difference rings. [ABSTRACT FROM AUTHOR]

In this paper we analyze the computational costs of various operations and algorithms in algebraic number fields using exact arithmetic. Let K be an algebraic number field. In the first half of the paper, we calculate the running time and the size of the output of many operations in K in terms of the size of the input and the parameters of K. We include some earlier results about these, but we go further than them, e.g. we also analyze some R -specific operations in K like less-than comparison. In the second half of the paper, we analyze two algorithms: the Bareiss algorithm, which is an integer-preserving version of the Gaussian elimination, and the LLL algorithm, which is for lattice basis reduction. In both cases, we extend the algorithm from Z n to K n , and give a polynomial upper bound on the running time when the computations in K are performed exactly (as opposed to floating-point approximations). [ABSTRACT FROM AUTHOR]

Approximate polynomial GCD (greatest common divisor) of polynomials with a priori errors on their coefficients, is one of interesting problems in Symbolic-Numeric Computations. In fact, there are many known algorithms: QRGCD, UVGCD, STLN based methods, Fastgcd and so on. The fundamental question of this paper is "which is the best?" from the practical point of view, and subsequently "is there any better way?" by any small extension, any effect by pivoting, and any combination of sub-routines along the algorithms. In this paper, we consider a framework that covers those algorithms and their sub-routines, and makes their sub-routines being interchangeable between the algorithms (i.e. disassembling the algorithms and reassembling their parts). By this framework along with/without small new extensions and a newly adapted refinement sub-routine, we have done many performance tests and found the current answer. In summary, 1) UVGCD is the best way to get smaller tolerance, 2) modified Fastgcd is better for GCD that has one or more clusters of zeros with large multiplicity, and 3) modified ExQRGCD is better for GCD that has no cluster of zeros. [ABSTRACT FROM AUTHOR]

In recent years there has been increased use of machine learning (ML) techniques within mathematics, including symbolic computation where it may be applied safely to optimise or select algorithms. This paper explores whether using explainable AI (XAI) techniques on such ML models can offer new insight for symbolic computation, inspiring new implementations within computer algebra systems that do not directly call upon AI tools. We present a case study on the use of ML to select the variable ordering for cylindrical algebraic decomposition. It has already been demonstrated that ML can make the choice well, but here we show how the SHAP tool for explainability can be used to inform new heuristics of a size and complexity similar to those human-designed heuristics currently commonly used in symbolic computation. [ABSTRACT FROM AUTHOR]

The Chow ring of the moduli space of stable marked curves is generated by Keel's divisor classes. The top graded part of this Chow ring is isomorphic to the integers, generated by the class of a single point. In this paper, we give an equivalent graphical characterization on the monomials in this Chow ring, as well as the characterization on the algebraic reduction on such monomials. Moreover, we provide an algorithm for computing the intersection degree of tuples of Keel's divisor classes — we call it the forest algorithm; the complexity of which is O (n 3) in the worst case, where n refers to the number of marks on the stable curves in the ambient moduli space. Last but not least, we introduce three identities on multinomial coefficients which naturally came into play, showing that they are all equivalent to the correctness of the base case of the forest algorithm. [ABSTRACT FROM AUTHOR]

In this paper we study the Shor relaxation of quadratic programs by fixing a feasible set and considering the space of objective functions for which the Shor relaxation is exact. We first give conditions under which this region is invariant under the choice of generators defining the feasible set. We then describe this region when the feasible set is invariant under the action of a subgroup of the general linear group. We conclude by applying these results to quadratic binary programs. We give an explicit description of objective functions where the Shor relaxation is exact and use this knowledge to design an algorithm that produces candidate solutions for binary quadratic programs. [ABSTRACT FROM AUTHOR]

This paper continues a research program on constructive investigations of non-commutative Ore localizations, initiated in our previous papers, and particularly touches the constructiveness of arithmetics within such localizations. Earlier 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, and present an algorithm for the computation of the symbolic power of a given ideal in a commutative ring. We also provide algorithms to compute local closures for certain non-commutative rings with respect to Ore sets with enough commutativity. [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]

In algebraic geometry, the Frobenius map (or called Frobenius action , or Frobenius operator) F ⁎ on cohomology groups plays an important role in the classification of algebraic varieties over a field of positive characteristic. In particular, representation matrices for F ⁎ give rise to many important invariants such as p -rank and a -number. Several methods for computing representation matrices for F ⁎ have been proposed for specific curves. In this paper, we present an algorithm to compute representation matrices for F ⁎ of general projective schemes over a perfect field of positive characteristic. We also propose an efficient algorithm specific to complete intersections; it requires to compute only certain coefficients in a power of a multivariate polynomial. Our algorithms shall derive fruitful applications such as computing Hasse-Witt matrices, and enumerating superspecial curves. In particular, the second algorithm for complete intersections provides a useful tool to judge the superspeciality of an algebraic curve, which is a key ingredient to prove main results in Kudo and Harashita (2017a,b, 2020) on the enumeration of superspecial genus-4 curves. [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]

We develop the first algorithm for computing rational solutions of scalar integro-differential equations with polynomial coefficients. It starts by finding the possible poles of a rational solution. Then, bounding the order of each pole and solving an algebraic linear system, we compute the singular part of rational solutions at each possible pole. Finally, using partial fraction decomposition, the polynomial part of rational solutions is obtained by computing polynomial solutions of a non-homogeneous scalar integro-differential equation with a polynomial right-hand side. The paper is illustrated by examples where the computations are done with our Maple implementation. [ABSTRACT FROM AUTHOR]

Mixed trigonometric-polynomials (MTPs) are functions of the form f (x , sin ⁡ x , cos ⁡ x) where f is a trivariate polynomial with rational coefficients, and the argument x ranges over the reals. In this paper, an algorithm "isolating" all the real roots of an MTP is provided and implemented. It automatically divides the real roots into two parts: one consists of finitely many roots in an interval [ μ − , μ + ] while the other consists of countably many roots in R ﹨ [ μ − , μ + ]. For the roots in [ μ − , μ + ] , the algorithm returns isolating intervals and corresponding multiplicities while for those greater than μ + , it returns finitely many mutually disjoint small intervals I i ⊂ [ − π , π ] , integers c i > 0 and multisets of root multiplicity { m j , i } j = 1 c i such that any root > μ + is in the set (∪ i ∪ k ∈ N (I i + 2 k π)) and any interval I i + 2 k π ⊂ (μ + , ∞) contains exactly c i distinct roots with multiplicities m 1 , i ,... , m c i , i , respectively. The efficiency of the algorithm is shown by experiments. The method used to isolate the roots in [ μ − , μ + ] is applicable to any other bounded interval as well. The algorithm takes advantages of the weak Fourier sequence technique and deals with the intervals period-by-period without scaling the coordinate so to keep the length of the sequence short. The new approaches can easily be modified to decide whether there is any root, or whether there are infinitely many roots in unbounded intervals of the form (− ∞ , a) or (a , ∞) with a ∈ Q. [ABSTRACT FROM AUTHOR]

Let G be a finite solvable group, given through a refined consistent polycyclic presentation, and α an automorphism of G , given through its images of the generators of G. In this paper, we discuss algorithms for computing the order of α as well as the cycle length of a given element of G under α. We give correctness proofs and discuss the theoretical complexity of these algorithms. Along the way, we carry out detailed complexity analyses of several classical algorithms on finite polycyclic groups. [ABSTRACT FROM AUTHOR]

In this paper, we prove a supercongruence via the Wilf–Zeilberger method and symbolic summation algorithms in the setting of difference rings. That is, for any prime p > 3 , ∑ n = 0 (p − 1) / 2 3 n + 1 (− 8) n ( 2 n n ) 3 ≡ p (− 1 p) + p 3 4 (2 p) E p − 3 (1 4) (mod p 4) , where (⋅ p) stands for the Legendre symbol, and E n (x) are the Euler polynomials. This confirms a special case of a recent conjecture of Z.-W. Sun (Sun, 2019 , (2.18)). [ABSTRACT FROM AUTHOR]

We show how the classical notions of cohomology with local coefficients, CW-complex, covering space, homeomorphism equivalence, simple homotopy equivalence, tubular neighbourhood, and spinning can be encoded on a computer and used to calculate ambient isotopy invariants of continuous embeddings N ↪ M of one topological manifold into another. More specifically, we describe an algorithm for computing the homology H n (X , A) and cohomology H n (X , A) of a finite connected CW-complex X with local coefficients in a Z π 1 X -module A when A is finitely generated over Z. It can be used, in particular, to compute the integral cohomology H n ( X ˜ H , Z) and induced homomorphism H n (X , Z) → H n ( X ˜ H , Z) for the covering map p : X ˜ H → X associated to a finite index subgroup H < π 1 X , as well as the corresponding homology homomorphism. We illustrate an open-source implementation of the algorithm by using it to show that: (i) the degree 2 homology group H 2 ( X ˜ H , Z) distinguishes between the homotopy types of the complements X ⊂ R 4 of the spun Hopf link and Satoh's tube map of the welded Hopf link (these two complements having isomorphic fundamental groups and integral homology); (ii) the degree 1 homology homomorphism H 1 (p − 1 (B) , Z) → H 1 ( X ˜ H , Z) distinguishes between the homeomorphism types of the complements X ⊂ R 3 of the granny knot and the reef knot, where B ⊂ X is the knot boundary (these two complements again having isomorphic fundamental groups and integral homology). Our open source implementation allows the user to experiment with further examples of knots, knotted surfaces, and other embeddings of spaces. We conclude the paper with an explanation of how the cohomology algorithm also provides an approach to computing the set [ W , X ] ϕ of based homotopy classes of maps f : W → X of finite CW-complexes over a fixed group homomorphism π 1 f = ϕ in the case where dim ⁡ W = n , π 1 X is finite and π i X = 0 for 2 ≤ i ≤ n − 1. [ABSTRACT FROM AUTHOR]

The sparse difference resultant introduced in Li et al. (2015b) is a basic concept in difference elimination theory. In this paper, we show that the sparse difference resultant of a generic Laurent transformally essential system can be computed via the sparse resultant of a simple algebraic system arising from the difference system. Moreover, new order bounds of sparse difference resultant are found. Then we propose an efficient algorithm to compute sparse difference resultant which is the quotient of two determinants whose elements are the coefficients of the polynomials in the algebraic system. The complexity of the algorithm is analyzed and experimental results show the efficiency of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper we study matching in equational theories that specify counterparts of associativity and commutativity for variadic function symbols. We design a procedure to solve a system of matching equations and prove its termination, soundness, completeness, and minimality. The minimal complete set of matchers for such a system can be infinite, but our algorithm computes its finite representation in the form of solved set. From the practical side, we identify two finitary cases and impose restrictions on the procedure to get an incomplete algorithm, which, based on our experiments, describes the input-output behavior and properties of Mathematica's flat and orderless pattern matching. [ABSTRACT FROM AUTHOR]

Given symmetric matrices A 0 , A 1 , ... , A n of size m with rational entries, the set of real vectors x = (x 1 , ... , x n) such that the matrix A 0 + x 1 A 1 + ⋯ + x n A n has non-negative eigenvalues is called a spectrahedron. Minimization of linear functions over spectrahedra is called semidefinite programming. Such problems appear frequently in control theory and real algebra, especially in the context of nonnegativity certificates for multivariate polynomials based on sums of squares. Numerical software for semidefinite programming are mostly based on interior point methods, assuming non-degeneracy properties such as the existence of an interior point in the spectrahedron. In this paper, we design an exact algorithm based on symbolic homotopy for solving semidefinite programs without assumptions on the feasible set, and we analyze its complexity. Because of the exactness of the output, it cannot compete with numerical routines in practice. However, we prove that solving such problems can be done in polynomial time if either n or m is fixed. [ABSTRACT FROM AUTHOR]

In this paper, we study unirational differential curves and the corresponding differential rational parametrizations. We first investigate basic properties of proper differential rational parametrizations for unirational differential curves. Then we show that the implicitization problem of proper linear differential rational parametric equations can be solved by means of differential resultants. Furthermore, for linear differential curves, we give an algorithm to determine whether an implicitly given linear differential curve is unirational, and in the affirmative case, to compute a proper differential rational parametrization for the differential curve. [ABSTRACT FROM AUTHOR]

Square-free decomposition is one of fundamental computations for polynomials. However, any conventional algorithm may not work for polynomials with a priori errors on their coefficients. There are mainly two approaches to overcome this empirical situation: approximate polynomial GCD (greatest common divisor) and the nearest singular polynomial. In this paper, we show that these known approaches are not enough for detecting the nearest square-free part (which has no multiple roots) within the given upper bound of perturbations (a priori errors), and we propose a new definition and a new method to detect a square-free part and its decomposition numerically by following a recent framework of approximate polynomial GCD. [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]

Multiplicative relations between the roots of a polynomial in Q [ x ] have drawn much attention in the field of arithmetic and algebra, while the problem of computing these relations is interesting to researchers in many other fields. In this paper, a sufficient condition is given for a polynomial f ∈ Q [ x ] to have only trivial multiplicative relations between its roots, which is a generalization of those sufficient conditions proposed in Smyth (1986) , Baron et al. (1995) and Dixon (1997). Based on the new condition, a subset E ⊂ Q [ x ] is defined and proved to be generic (i.e. , the set Q [ x ] \ E is very small). We develop an algorithm deciding whether a given polynomial f ∈ Q [ x ] is in E and returning a basis of the lattice consisting of the multiplicative relations between the roots of f whenever f ∈ E. The numerical experiments show that the new algorithm is very efficient for the polynomials in E. A large number of polynomials with much higher degrees, which were intractable before, can be handled successfully with the algorithm. [ABSTRACT FROM AUTHOR]

Identifiability is a crucial property for a statistical model since distributions in the model uniquely determine the parameters that produce them. In phylogenetics, the identifiability of the tree parameter is of particular interest since it means that phylogenetic models can be used to infer evolutionary histories from data. In this paper we introduce a new computational strategy for proving the identifiability of discrete parameters in algebraic statistical models that uses algebraic matroids naturally associated to the models. We then use this algorithm to prove that the tree parameters are generically identifiable for 2-tree CFN and K3P mixtures. We also show that the k-cycle phylogenetic network parameter is identifiable under the K2P and K3P models. [ABSTRACT FROM AUTHOR]

Powers of (monomial) ideals is a subject that still calls attraction in various ways. In this paper we present a nice presentation of high powers of ideals in a certain class in K [ x 1 , ... , x n ] and K [ [ x 1 , ... , x n ] ]. As an interesting application it leads to an algorithm for computation of the Ratliff–Rush operation on ideals in that class. The Ratliff–Rush operation itself has several applications, for instance, if I is a regular m -primary ideal in a local ring (R , m) , then the Ratliff–Rush associated ideal I ˜ is the unique largest ideal containing I with the same Hilbert polynomial as I. [ABSTRACT FROM AUTHOR]

The XL algorithm is an algorithm for solving overdetermined systems of multivariate polynomial equations, which was initially introduced for quadratic equations. However, the algorithm works for polynomials of any degree, and in this paper we will focus on the performance of XL for polynomials of degree ≥3, where the optimal termination value of the parameter D is still unknown. We prove that the XL algorithm terminates at a certain value of D in the case that the number of equations exceeds the number of variables by 1 or 2. We also give strong evidence that this value is best possible, and we show that this value is smaller than the degree of regularity. Part of our analysis requires proving that ordinary multinomials are strongly unimodal, and this result may be of independent interest. [ABSTRACT FROM AUTHOR]

This paper presents fundamental algorithms for the computational theory of quadratic forms over number fields. In the first part of the paper, we present algorithms for checking if a given non-degenerate quadratic form over a fixed number field is either isotropic (respectively locally isotropic) or hyperbolic (respectively locally hyperbolic). Next we give a method of computing the dimension of an anisotropic part of a quadratic form. The second part of the paper is devoted to algorithms computing two field invariants: the level and the Pythagoras number. Ultimately we present an algorithm verifying whether two number fields have isomorphic Witt rings (i.e. are Witt equivalent). [ABSTRACT FROM AUTHOR]

In this paper, we study the notion of special ideals. We generalize the results on those as well as the algorithm obtained for finite dimensional power series rings by Mordechai Katzman and Wenliang Zhang to finite dimensional polynomial rings. [ABSTRACT FROM AUTHOR]

The ring of covariants of binary form is isomorphic to the ring of regular symmetric bracket polynomials in homogenized roots, which are obtained by symmetrization of regular bracket polynomials. In this paper, we give an algorithm for computing all cyclically standard bracket monomials of arbitrary degree. These monomials form a basis of the vector space of the regular bracket polynomials of a given degree. We also characterize the elemental bracket monomial of degree 2 in terms of graph theory. [ABSTRACT FROM AUTHOR]

In this paper we describe the method which we applied to successfully compute the primary decomposition of a certain ideal coming from applications in combinatorial algebra and algebraic statistics regarding conditional independence statements with hidden variables. While our method is based on the algorithm for primary decomposition by Gianni, Trager and Zacharias, we were not able to decompose the ideal using the standard form of that algorithm, nor by any other method known to us. [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 first prove that when the associated graph of a polynomial set is chordal, a particular triangular set computed by a general algorithm in top-down style for computing the triangular decomposition of this polynomial set has an associated graph as a subgraph of this chordal graph. Then for Wang's method and a subresultant-based algorithm for triangular decomposition in top-down style and for a subresultant-based algorithm for regular decomposition in top-down style, we prove that all the polynomial sets appearing in the process of triangular decomposition with any of these algorithms have associated graphs as subgraphs of this chordal graph. These theoretical results can be viewed as non-trivial polynomial generalization of existing ones for sparse Gaussian elimination, inspired by which we further propose an algorithm for sparse triangular decomposition in top-down style by making use of the chordal structure of the polynomial set. The effectiveness of the proposed algorithm for triangular decomposition, when the polynomial set is chordal and sparse with respect to the variables, is demonstrated by preliminary experimental results. [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]

We consider the problem of finding the isolated common roots of a set of polynomial functions defining a zero-dimensional ideal I in a ring R of polynomials over C. Normal form algorithms provide an algebraic approach to solve this problem. The framework presented in Telen et al. (2018) uses truncated normal forms (TNFs) to compute the algebra structure of R / I and the solutions of I. This framework allows for the use of much more general bases than the standard monomials for R / I. This is exploited in this paper to introduce the use of two special (non-monomial) types of basis functions with nice properties. This allows us, for instance, to adapt the basis functions to the expected location of the roots of I. We also propose algorithms for efficient computation of TNFs and a generalization of the construction of TNFs in the case of non-generic zero-dimensional systems. The potential of the TNF method and usefulness of the new results are exposed by many experiments. [ABSTRACT FROM AUTHOR]

This paper provides a new algorithm for the formal reduction of linear differential systems with Laurent series coefficients. We show how to obtain a decomposition of Balser, Jurkat and Lutz using eigenring techniques. This allows us to establish structural information on the obtained indecomposable subsystems and retrieve information on their invariants such as ramification. We show why classical algorithms then perform well on these subsystems. We also give precise estimates of the precision on the power series which is required in each step of our algorithm. The algorithm is implemented in Maple and examples are given in Saade (2018). [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]

In an earlier article (Bostan et al., 2017), with Carlos D'Andrea, we described explicit expressions for the coefficients of the order- d polynomial subresultant of (x − α) m and (x − β) n with respect to Bernstein's set of polynomials { (x − α) j (x − β) d − j , 0 ≤ j ≤ d } , for 0 ≤ d < min ⁡ { m , n }. The current paper further develops the study of these structured polynomials and shows that the coefficients of the subresultants of (x − α) m and (x − β) n with respect to the monomial basis can be computed in linear arithmetic complexity, which is faster than for arbitrary polynomials. The result is obtained as a consequence of the amazing though seemingly unnoticed fact that these subresultants are scalar multiples of Jacobi polynomials up to an affine change of variables. [ABSTRACT FROM AUTHOR]

In this paper, a symbolic, algorithmic procedure to compute an immersion that recasts a polynomial system into a linear one up to an output injection is proposed. Such a technique is based on computing, through algebraic geometry methods, the set of all the embeddings of the system and on matching the coefficients of these polynomials with the ones of the embeddings of a linear system up to an output injection. The given algorithm is then relaxed to compute an immersion that recasts a polynomial system into a form that is linear up to a finite order and an output injection and to compute an approximation of the immersion. [ABSTRACT FROM AUTHOR]

Let F be any characteristic zero field and let f ∈ F [ x ] be a univariate polynomial. A sum of affine powers is an expression of the form f (x) = ∑ i = 1 s α i (x − a i) e i . Although quite simple, this model is a generalization of two well-studied models: Waring decomposition and Sparsest Shift. We present structural results which compare the expressive power of the three models; and we propose algorithms that find the smallest decomposition of f in the first model (sums of affine powers) for an input polynomial f given in dense representation. This work could be extended in several directions. In particular, just as for Sparsest Shift and Waring decomposition, one could consider extensions to "supersparse" polynomials and study the multivariate version of the problem. We also point out that the basic univariate problem studied in the present paper is far from completely solved: our algorithms all rely on some assumptions for the exponents e i in a decomposition of f , and some algorithms also rely on a distinctness assumption for the shifts a i. It would be very interesting to weaken these assumptions, or even to remove them entirely. Another related and poorly understood issue is that of the bit size of the constants a i , α i in an optimal decomposition: is it always polynomially related to the bit size of the input polynomial f given in dense representation? [ABSTRACT FROM AUTHOR]

In this paper, we present an algorithm for computing the minimal reductions of m -primary ideals of Cohen–Macaulay local rings. Using this algorithm, we are able to compute the Hilbert–Samuel multiplicities and solve the membership problem for the integral closure of m -primary ideals. [ABSTRACT FROM AUTHOR]

This paper presents two new normal forms for fractions of differential polynomials, as well as algorithms for computing them. The first normal form allows to write a fraction as the derivative of a fraction plus a nonintegrable part. The second normal form is an extension of the first one, involving iterated differentiations. The main difficulty in this paper consists in defining normal forms which are linear operations over the field of constants, a property which was missing in our previous works. Our normal forms do not require fractions to be converted into polynomials, a key feature for further problems such as integrating differential fractions, and more generally solving differential equations. [ABSTRACT FROM AUTHOR]

Abstract The growth of tropical geometry has generated significant interest in the tropical semiring in the past decade. However, there are other semirings in tropical algebra that provide more information, such as the symmetrized (max ⁡ , +) , Izhakian's extended and Izhakian–Rowen's supertropical semirings. In this paper we identify in which of these upper-bound semirings we can express symmetric polynomials in terms of elementary ones. We show that in the case of idempotent semirings we can do this precisely when the Frobenius property is satisfied, that in the case of supertropical semirings this is always possible, and that in non-trivial symmetrized semirings this is never possible. Our results allow us to determine the tropical algebra semirings where an analogue of the Fundamental Theorem of Symmetric Polynomials holds and to what extent. [ABSTRACT FROM AUTHOR]

Pisot numbers are real algebraic integers bigger than 1, whose other conjugates all have modulus smaller than 1. In this paper we deal with the algorithmic problem of finding the smallest Pisot unit generating a given number field. We first solve this problem in all real fields, then we consider the analogous problem involving the so called complex Pisot numbers and we solve it in all number fields that admit such a generator, in particular this includes all fields without CM. [ABSTRACT FROM AUTHOR]

This paper contains three new algorithms for computing invariant rings. The first two apply to invariants of a finite group acting on a finitely generated algebra over a Euclidean ring. This may be viewed as a first step in “computational arithmetic invariant theory.” As a special case, the algorithms can compute multiplicative invariant rings. The third algorithm computes the invariant ring of a reductive group acting on a vector space, and often performs better than the algorithms known to date. The main tool upon which two of the algorithms are built is a generalized version of an ideal that was already used by Derksen in his algorithm for computing invariants of linearly reductive groups. As a further application, these so-called extended Derksen ideals give rise to invariantization maps, which turn an arbitrary ring element into an invariant. For the most part, the algorithms of this paper have been implemented. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm which, given a point and a set of polynomials, constructs a single cylindrical cell containing the point, such that the given polynomials are sign-invariant in the computed cell. To represent a single cylindrical cell, a novel data structure is introduced. The algorithm works with this representation and proceeds incrementally, i.e., first constructing a cell representing the whole real space, and then iterating over the input polynomials, refining the cell at each step to ensure the sign-invariance of the current input polynomial. A merge procedure realizing this refinement is described, and its correctness is proven. The merge procedure is based on McCallum's projection operator, but uses geometric information relative to the input point to reduce the number of projection polynomials computed. The use of McCallum's operator implies the incompleteness of the algorithm in general. However, the algorithm is complete for well-oriented sets of polynomials. Moreover, the incremental approach described in this paper can be easily adapted to a different projection operator. The cell construction algorithm presented in this paper is an alternative to the “model-based” method described by Jovanović and de Moura in a 2012 paper. It generalizes the algorithm described by the first author in a 2013 paper, which could only produce full-dimensional cells, to allow for the construction of cells of arbitrary dimension. While a thorough comparison, whether analytical or empirical, of the new algorithm and the “model-based” approach will be the subject of future work, this paper provides preliminary justification for asserting the superiority of the new method. [ABSTRACT FROM AUTHOR]