Search

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]

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 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: 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: 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: 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]

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]

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 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]

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]

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]

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]