Search

Abstract This paper provides new equivalence theorems for regular chains and regular differential chains, which are generalizations of Ritt's characteristic sets. These theorems focus on regularity properties of elements of residue class rings defined by these chains, which are revealed by resultant computations. New corollaries to these theorems have quite simple formulations. [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]

In this paper we deal with a problem of Pethő related to existence of a quartic algebraic integer α for which β = 4 α 4 α 4 − 1 − α α − 1 is a quadratic algebraic number. By studying rational solutions of certain Diophantine system we prove that there are infinitely many α 's such that the corresponding β is quadratic. Moreover, we present a description of quartic numbers α such that the corresponding β is a quadratic real number. [ABSTRACT FROM AUTHOR]

This paper presents a new algorithm for implicitizing tensor product surfaces of bi-degree ( m , n ) with no base points, assuming that there are no moving planes of bi-degree ( m − 1 , n − 1 ) following the surface. The algorithm is based on some structural results: (1) There are exactly 2 n linearly independent moving planes of bi-degree ( m , n − 1 ) following the surface; (2) mn linearly independent moving quadrics of bi-degree ( m − 1 , n − 1 ) following the surface can be constructed from the 2 n linearly independent moving planes; (3) The mn linearly independent moving quadrics form a compact determinant of order mn which exactly gives the implicit equation of the rational surface. Complexity analysis and experimental results show that the new algorithm is significantly more efficient than the previous methods. [ABSTRACT FROM AUTHOR]

The linearization problem of a third-order ordinary differential equation by the tangent transformation is considered in the present paper. This is the first application of tangent (essentially) transformations to the linearization problem of third-order ordinary differential equations. Necessary and sufficient conditions for a third-order ordinary differential equation to be linearizable are obtained. [ABSTRACT FROM AUTHOR]

Abstract: This paper studies separating subsets of an invariant ring or, more generally, of any set consisting of functions. We prove that a subset of a finitely generated algebra always contains a finite separating subset. We also show that a general version of Noether’s degree bound holds for separating invariants, independently of the characteristic. While the general finiteness result is non-constructive, the Noether bound provides an easy algorithm for computing separating invariants of finite groups. The paper also contains a conceptual investigation of the difference between separating and generating subsets. [Copyright &y& Elsevier]

Abstract: In this paper we describe software for an efficient factorization of polynomials over global fields . The algorithm for function fields was recently incorporated into our system KANT. The method is based on a generic algorithm developed by the second author in an earlier paper in this journal. Besides algorithmic aspects not contained in that paper we give details about the current implementation and about some complexity issues as well as a few illustrative examples. Also, a generalization of the application of LLL reduction for factoring polynomials over arbitrary global fields is developed. [Copyright &y& Elsevier]

The aim of this paper is to exploit the algorithms of paper Experimental Math. 8 (1999) in order to produce a new algebraic method for computing efficiently absolute Lagrange resolvent, a fundamental tool in constructive algebraic Galois theory. This article is composed of two parts.The main idea of the first part is to break up the calculation of absolute resolvent into smaller computations. Since a multi-resolvent is a factor of a resolvent, the whole resolvent may be computed by means of several multi-resolvents.The idea of the second part is that an irreducible polynomial over Z might be reducible over Z /pZ for certain integer p. So the first part can be applied and then, the Chinese remainder theorem allows to lift up the resolvent over Z. [Copyright &y& Elsevier]

The main question of this paper is: What is the dense (Macaulay) resultant of composed polynomials? By a composed polynomial f∘(g1,…,gn), we mean the polynomial obtained from a polynomial f in the variables y1,…,yn by replacing yj by some polynomial gj. Cheng, McKay and Wang and Jouanolou have provided answers for two particular subcases. The main contribution of this paper is to complete these works by providing a uniform answer for all subcases. In short, it states that the dense resultant is the product of certain powers of the dense resultants of the component polynomials and of some of their leading forms. It is expected that these results can be applied to compute dense resultants of composed polynomials with improved efficiency. We also state a lemma of independent interest about the dense resultant under vanishing of leading forms. [Copyright &y& Elsevier]

In 1994 Lazard proposed an improved projection operation for cylindrical algebraic decomposition (CAD). For the proof he introduced a certain notion of valuation of a multivariate Puiseux series at a point. However a gap in one of the key supporting results for the improved projection was subsequently noticed. In this paper we show that Lazard's projection is valid for CAD construction for so-called well-oriented polynomial sets. Our proof does not make use of Lazard's notion of valuation, however. [ABSTRACT FROM AUTHOR]

Abstract: Over the past 20 years, the use of Computer Algebra Systems (CAS) has helped with the teaching of mathematics in engineering schools. However the traditional use of CAS only in math labs has led to a narrow view by the student: the CAS is an additional work, not included in the learning process. The didactic guidelines of the European Higher Education Area (EHEA) propose a new teaching–learning model based on competencies. We suggest the use of the CAS be adapted to the new rules. In this paper, we present a model for the integrated use of the CAS, and we describe and analyze two experiments carried out in the academic year 2011–2012. Our analysis suggests that the use of CAS in all learning and assessment activities has the potential to positively influence the development of competencies. [Copyright &y& Elsevier]

Abstract: This paper describes an algorithm which produces all ideals compatible with a given surjective Frobenius near-splitting. [Copyright &y& Elsevier]

Abstract: This paper introduces some relations about Cayley graphs and -graphs. We present a sufficient condition to recognize when a -graph is a Cayley graph. The relation between -graphs and Cayley graphs allows us to consider some applications to the hamiltonicity of Cayley graphs. In the last section we illustrate our results by showing that some new classes of Cayley graphs are hamiltonian. [Copyright &y& Elsevier]

Abstract: We present a new algorithm for computing the topology of a real algebraic surface in a ball , even in singular cases. We use algorithms for 2D and 3D algebraic curves and show how one can compute a topological complex equivalent to , and even a simplicial complex isotopic to by exploiting properties of the contour curve of . The correctness proof of the algorithm is based on results from stratification theory. We construct an explicit Whitney stratification of , by resultant computation. Using Thom’s isotopy lemma, we show how to deduce the topology of from a finite number of characteristic points on the surface. An analysis of the complexity of the algorithm and effectiveness issues conclude the paper. [Copyright &y& Elsevier]

Abstract: Every coherent system has a monomial ideal associated with it and the knowledge of its multigraded Betti numbers provides reliability bounds for the corresponding system, which are the tightest among a certain class of such bounds. Some alternative methods for computing the multigraded Betti numbers are used in this paper and applied in the study of reliability. We obtain special results for well known examples and show that computational commutative algebra techniques can be used beneficially in the reliability analysis of systems of different types. [Copyright &y& Elsevier]

Abstract: A connected algebraic group in characteristic is uniquely determined by its Lie algebra. In this paper algorithms are given for constructing an algebraic group in characteristic , given its Lie algebra. In particular, this leads to an algorithm for finding a maximal reductive subgroup and the unipotent radical of an algebraic group. [Copyright &y& Elsevier]

Abstract: This paper presents a new algorithm that computes the local algebras of the roots of a zero-dimensional polynomial equation system, with a number of operations in the coefficient field that is polynomial in the number of variables, in the evaluation cost of the equations and in a Bézout number. [Copyright &y& Elsevier]

Abstract: This paper explores the certification of properties of an efficient functional program in the area of symbolic computation: the calculation of Gröbner basis of a set of multivariate polynomials. Our experience in the development of industrial systems and the certification of some of its relevant properties has led us to use a methodology consisting of functional programs to write the code and the formal verification of fundamental properties. The functional language objective caml has been chosen to implement the program. To verify the properties two approaches are explored: manual proofs that reason directly over the source code of the algorithms, applying techniques like equational reasoning, and theorem provers that are used as a tool to help us certify a model of the real system. The chosen proof assistant is coq. Not only will the certification of the software be taken into consideration but also its efficiency. In addition, we present a graphical interface which eases the use of the program. [Copyright &y& Elsevier]

Abstract: The classification of naturally graded quasi-filiform Lie algebras is known; they have the characteristic sequence where is the dimension of the algebra. In the present paper we deal with naturally graded quasi-filiform non-Lie–Leibniz algebras which are described by the characteristic sequence or . The first case has been studied in [Camacho, L.M., Gómez, J.R., González, A.J., Omirov, B.A., 2006. Naturally graded 2-filiform Leibniz Algebra and its applications, preprint, MA1-04-XI06] and now, we complete the classification of naturally graded quasi-filiform Leibniz algebras. For this purpose we use the software (the program used is explained in the last section). [Copyright &y& Elsevier]

Abstract: In this paper we give an algorithm that detects real singularities, including singularities at infinity, and counts local branches and multiplicities of real rational curves in the affine -space without knowing an implicitization. The main idea behind this is a generalization of the -resultant (see [van den Essen, A., Yu, J.-T., 1997. The -resultant, singularities and the degree of unfaithfulness. Proc. Amer. Math. Soc. 25 (3), 689–695]) to rational functions. This allows us to find all real parameters corresponding to the real singularities between the solutions of a system of polynomials in one variable. [Copyright &y& Elsevier]

Abstract: Lawrence semigroups arise as a tool to compute Graver bases of semigroup ideals. It is known that the minimal free resolution of semigroup ideals is characterized by the reduced homologies of certain simplicial complexes. In this paper we study the minimal degrees of a Lawrence semigroup ideal and its first syzygy given a combinatorial characterization of the nonvanishing cycles in their associated reduced homologies. We specialize the results that appeared in [Briales, E., Campillo, A., Marijuán, C., Pisón, P., 1998. Minimal systems of generators for ideals of semigroups. J. Pure Appl. Algebra, 127, 7–30] and [Pisón-Casares, P., Vigneron-Tenorio, A., 2001. First syzygies of toric varieties and diophantine equations in congruence. Comm. Alg. 29 (4), 1445–1466] to the Lawrence semigroups. [Copyright &y& Elsevier]

Abstract: In this paper we study standard bases for submodules of respectively of their localisation with respect to a -local monomial ordering. The main step is to prove the existence of a division with remainder generalising and combining the division theorems of Grauert–Hironaka and Mora. Everything else then translates naturally. Setting either or we get standard bases for polynomial rings respectively for power series rings as a special case. We then apply this technique to show that the -initial ideal of an ideal over the Puiseux series field can be read of from a standard basis of its generators. This is an important step in the constructive proof that each point in the tropical variety of such an ideal admits a lifting. [Copyright &y& Elsevier]

Abstract: The Gröbner walk is an algorithm for conversion between Gröbner bases for different term orders. It is based on the polyhedral geometry of the Gröbner fan and involves tracking a line between cones representing the initial and target term order. An important parameter is the explicit numerical perturbation of this line. This usually involves both time and space, demanding arithmetic of integers much larger than the input numbers. In this paper we show how the explicit line may be replaced by a formal line using Robbiano’s characterization of group orders on . This gives rise to the generic Gröbner walk involving only Gröbner basis conversion over facets and computations with marked polynomials. The infinite precision integer arithmetic is replaced by term order comparisons between (small) integral vectors. This makes it possible to compute with infinitesimal numbers and perturbations in a consistent way without introducing unnecessary long integers. The proposed technique is closely related to the lexicographic (symbolic) perturbation method used in optimization and computational geometry. We report on an implementation of our algorithm specifically tailored to computations with lattice ideals. [Copyright &y& Elsevier]

Abstract: An algorithm is presented that computes explicit generators for the ring of differential operators on an orbifold, the quotient of a complex vector space by a finite group action. The algorithm also describes the relations among these generators. The algorithm presented in this paper is based on Schwarz’s study of a map carrying invariant operators to operators on the orbifold and on an algorithm to compute rings of invariants using Gröbner bases due to Derksen [Derksen, Harm, 1999. Computation of invariants for reductive groups. Adv. Math. 141 (2), 366–384]. It is also possible to avoid using Derksen’s algorithm, instead relying on the Reynolds operator and the Molien series. [Copyright &y& Elsevier]

Abstract: One of the main contributions which Volker Weispfenning made to mathematics is related to Gröbner bases theory. In this paper we present an algorithm for computing all algebraic intermediate subfields in a separably generated unirational field extension (which in particular includes the zero characteristic case). One of the main tools is Gröbner bases theory. Our algorithm also requires computing primitive elements and factoring over algebraic extensions. Moreover, the method can be extended to finitely generated -algebras. [Copyright &y& Elsevier]

Abstract: Consider the class of exp–log constants, which is constructed from the integers using the field operations, exponentiation and logarithm. Let be such an exp–log constant and let be its size as an expression. Witness conjectures attempt to give bounds for the number of decimal digits which need to be evaluated in order to test whether equals zero. For this purpose, it is convenient to assume that exponentials are only applied to arguments with absolute values bounded by 1. In that context, several witness conjectures have appeared in the literature and the strongest one states that it is possible to choose . In this paper we give a counterexample to this conjecture. We also extend it so as to cover similar, polynomial witness conjectures. [Copyright &y& Elsevier]

Abstract: This paper presents some fundamental aspects of the design and the implementation of an automated prover for Zermelo–Fraenkel set theory within the Theorema system. The method applies the “Prove–Compute–Solve” paradigm as its major strategy for generating proofs in a natural style for statements involving constructs from set theory. [Copyright &y& Elsevier]

Abstract: In statistical inference, mixture models consisting of several component subpopulations are used widely to model data drawn from heterogeneous sources. In this paper, we consider maximum likelihood estimation for mixture models in which the only unknown parameters are the component proportions. By applying the theory of multivariable polynomial equations, we derive bounds for the number of isolated roots of the corresponding system of likelihood equations. If the component densities belong to certain familiar continuous exponential families, including the multivariate normal or gamma distributions, then our upper bound is, almost surely, the exact number of solutions. [Copyright &y& Elsevier]

Abstract: Let be a field and a finite directed multi-graph. The focus of this paper is to offer a complete description of all path algebras and admissible orders with the property that all of their finitely generated ideals have finite Gröbner bases and of those which contain a finitely generated ideal whose Gröbner bases are all infinite. [Copyright &y& Elsevier]

Abstract: Algebraic function fields of positive characteristic are non-perfect fields, and many standard algorithms for solving some fundamental problems in commutative algebra simply do not work over these fields. This paper presents practical algorithms for the first time for (1) computing the primary decomposition of ideals of polynomial rings defined over such fields and (2) factoring arbitrary multivariate polynomials over such fields. Difficulties involving inseparability and the situation where the transcendence degree is greater than one are completely overcome, while the algorithms avoid explicit construction of any extension of the input base field. As a corollary, the problem of computing the primary decomposition of a positive-dimensional ideal over a finite field is also solved. The algorithms perform very effectively in an implementation within the Magma Computer Algebra System, and an analysis of their practical performance is given. [Copyright &y& Elsevier]

Abstract: One approach for computations with special functions in computer algebra is the systematic use of analytic functions whenever possible. This naturally leads to problems of how to answer questions about analytic functions in a fully effective way. Such questions comprise the determination of the radius of convergence or the evaluation of the analytic continuation of the function at the endpoint of a broken line path. In this paper, we propose a first definition for the notion of an effective analytic function and we show how to effectively solve several types of differential equations in this context. We will limit ourselves to functions in one variable. [Copyright &y& Elsevier]

Abstract: In this paper, we present different results related to bezoutian and residue theory. We consider, in particular, the problem of computing the structure of the quotient ring by an affine complete intersection, and an algorithm to obtain it, as conjectured in [Cardinal, J.-P., 1993. Dualité et algorithmes itératifs pour la résolution de systèmes polynomiaux. Ph.D. Thesis, Univ. de Rennes]. We analyze it in detail and prove the validity of the conjecture, for a modification of the initial method. Direct applications of the results in effective algebraic geometry are given. [Copyright &y& Elsevier]

Abstract: In this paper we introduce an intermediate representation of surfaces that we call semi-implicit. We give a general definition in the language of projective complex algebraic geometry, and we begin its systematic study with an effective view-point. Our last section will apply this representation to investigate the intersection of two bi-cubic surfaces; these surfaces are widely used in Computer Aided Geometric Design. [Copyright &y& Elsevier]

The aim of this paper is to describe two new factorization algorithms for polynomials. The first factorizes polynomials modulo the prime ideal of a number field. The second factorizes polynomials over a number field. [Copyright &y& Elsevier]

This paper is an exposition of different methods for computing closed forms of definite sums. The focus is on recently-developed results on computing closed forms of definite sums of hypergeometric terms. A design and an implementation of a software package which incorporates these methods into the computer algebra system Maple are described in detail. [Copyright &y& Elsevier]

In the computation of a Gröbner basis using Buchberger’s algorithm, a key issue for improving the efficiency is to produce techniques for avoiding as many unnecessary critical pairs as possible. A good solution would be to avoid all non-minimal critical pairs, and hence to process only a minimal set of generators of the module generated by the critical syzygies. In this paper we show how to obtain that desired solution in the homogeneous case while retaining the same efficiency as with the classical implementation. As a consequence, we get a new optimized Buchberger algorithm. [Copyright &y& Elsevier]

In this paper we compare the approach of Brianc¸on and Maisonobe for computing Bernstein–Sato ideals—based on computations in a Poincare´–Birkhoff–Witt algebra—with the readily available method of Oaku and Takayama. We show that it can deal with interesting examples that have proved intractable so far. [Copyright &y& Elsevier]

The second-order matching problem is to determine whether or not a first-order term without variables is an instance of a second-order term that is allowed to contain not only individual variables but also function variables. It is well known that the second-order matching problem is NP-complete in general. In this paper, we first introduce the several restrictions for the second-order matching problems, such as the bounded number, arity and occurrence of function variables, ground that contains no individual variables, flat that contains no function constants, and predicate that no function variable occurs in the terms of arguments of each function variable. By combining the above restrictions, we give the sharp separations of tractable second-order matching problems from intractable ones. Finally, we compare them with the separations of decidable second-order unification problems from undecidable ones. [Copyright &y& Elsevier]

In this paper, we propose a semi-numerical algorithm for computing absolute factorization of multivariate polynomials. It is based on some properties appearing after a generic change of coordinate. Using numerical computation, Galois group action and rational approximation, this method provides an efficient probabilistic algorithm for medium degrees. Two implementations are presented and compared to other algorithms. [Copyright &y& Elsevier]

The short product of two power series is the meaningful part of the product of these objects, i.e., ∑i+j. Mulders (AAECC 11 (2000) 69) gives an algorithm to compute a short product faster than the full product in the case of Karatsuba’s multiplication (Karatsuba and Ofman, Dokl. Akad. Nauk SSSR 145 (1962) 293). This algorithm works by selecting a cutoff point k and performing a full k×k product and two (n−k)×(n−k) short products recursively. Mulders also gives a heuristically optimal cutoff point βn. In this paper, we determine the optimal cutoff point in Mulders’ algorithm. We also give a slightly more general description of Mulders’ method. [Copyright &y& Elsevier]

The purpose of this paper is to present an effective method of deciding the semidefiniteness of multivariate polynomials with coefficients in a computable ordered field, which admits an effective method of finding an isolating set for every non-zero univariate polynomial. Based on this method, the decision of the semidefiniteness of a multivariate polynomial may be reduced to testing some resulted polynomials in fewer variables, of which the total degrees and the term numbers do not exceed those of the given polynomial. With the aid of the computer algebra system Maple, our method is used to solve several examples. [Copyright &y& Elsevier]

The classical Dixon resultant formulation gives the exact A-resultant for the bi-degree rectangular monomial support. But the formulation gives a multiple of the A-resultant when the monomial support is a bi-degree rectangular support with some corner edges removed. Fortunately, here the extraneous factors can be easily identified a priori and the A-resultant can be expressed explicitly as a quotient: the determinant of a Dixon matrix divided by a product of brackets. All proofs in the paper are constructive. One of the proofs is mechanically done by a Maple program. [Copyright &y& Elsevier]

In this paper we prove that, for a given set of parametric primary surfaces and parametric clipping curves, all parametric blending solutions can be expressed as the addition of a particular parametric solution and a generic linear combination of the basis of a free module of rank 3. As a consequence, we present an algorithm that outputs a generic expression for all the parametric solutions for the blending problem. In addition, we also prove that the set of all polynomial parametric solutions (i.e. solutions that have polynomial parametrizations) for a parametric blending problem can also be expressed in terms of the basis of a free module of rank 3, and we prove an algorithmic criterion to decide whether there exist parametric polynomial solutions. As a consequence we also present an algorithm that decides the existence of polynomial solutions, and that outputs (if this type of solution exists) a generic expression for all polynomial parametric solutions for the problem. [Copyright &y& Elsevier]

The Kovacic algorithm and its improvements give explicit formulae for the Liouvillian solutions of second order linear differential equations. Algorithms for third order differential equations also exist, but the tools they use are more sophisticated and the computations more involved. In this paper we refine parts of the algorithm to find Liouvillian solutions of third order equations. We show that, except for four finite groups and a reduction to the second order case, it is possible to give a formula in the imprimitive case. We also give necessary conditions and several simplifications for the computation of the minimal polynomial for the remaining finite set of finite groups (or any known finite group) by extracting ramification information from the character table. Several examples have been constructed, illustrating the possibilities and limitations. [Copyright &y& Elsevier]

Let An(k) be the Weyl algebra, with k a field of characteristic zero. It is known that every projective finitely generated left module is free or isomorphic to a left ideal. Let M be a left submodule of a free module. In this paper we give an algorithm to compute the projective dimension of M. If M is projective and rank(M)≥2 we give a procedure to find a basis. [Copyright &y& Elsevier]

In this paper an algorithm is given to decide if a given polynomial in two variables with coefficients in a finitely generated K-algebra is a coordinate and if so, find a mate for this polynomial. [Copyright &y& Elsevier]

In this paper, we propose algorithms for the following problems in the implicitization of a set of differential rational parametric equations P. (1) To find a characteristic set for the implicit prime ideal of P. (2) To find a canonical representation for the image of P. (3) To decide whether the parameters of P are independent, and if not, to re-parameterize P so that the new parametric equations have independent parameters. (4) To compute the inversion maps of P, and as a consequence, to decide whether P is proper. If the implicit variety is of dimension one and P is not proper, to find a proper re-parameterization for P. [Copyright &y& Elsevier]

In this paper we establish the Cayley expansion theory on factored and shortest expansions of typical Cayley expressions in two- and three-dimensional projective geometry. We set up a group of Cayley factorization formulae based on the classification of Cayley expansions. We continue to establish three powerful simplification techniques in bracket computation. On top of the Cayley expansions and simplifications, together with a set of elimination rules, we design an algorithm that can produce extremely short proofs in two- and three-dimensional projective geometry. The techniques developed here can be immediately applied to other symbolic computation tasks involving brackets. [Copyright &y& Elsevier]

The μ-basis of a rational ruled surface P(s,t)=P0(s)+tP1(s) is defined in Chen et al. (Comput. Aided Geom. Design 18 (2001) 61) to consist of two polynomials p(x,y,z,s) and q(x,y,z,s) that are linear in x, y, z. It is shown there that the resultant of p and q with respect to s gives the implicit equation of the rational ruled surface; however, the parametric equation P(s,t) of the rational ruled surface cannot be recovered from p and q. Furthermore, the μ-basis thus defined for a rational ruled surface does not possess many nice properties that hold for the μ-basis of a rational planar curve (Comput. Aided Geom. Design 18 (1998) 803). In this paper, we introduce another polynomial r(x,y,z,s,t) that is linear in x, y, z and t such that p, q, r can be used to recover the parametric equation P(s,t) of the rational ruled surface; hence, we redefine the μ-basis to consist of the three polynomials p, q, r. We present an efficient algorithm for computing the newly-defined μ-basis, and derive some of its properties. In particular, we show that the new μ-basis serves as a basis for both the moving plane module and the moving plane ideal corresponding to the rational ruled surface. [Copyright &y& Elsevier]

We correct four typographical errors in the paper, “The F5 criterion revised.” [ABSTRACT FROM AUTHOR]