ICMS 2016 Session: Software of Polynomial Systems

ICMS 2016: Home, Sessions Page


Aim and Scope

Polynomial systems appear in commutative algebra, algebraic geometry, geometric reasoning, cryptography, coding theory, biology, and many other areas of science and engineering. The study of structures, properties, and representations of mathematical objects defined by polynomial systems may involve heavy computations, for which advanced software need be developed and used. This session aims at bringing together interested researchers, software developers, and software users to present and to discuss recent work and progress on the design, implementation, analysis, and application of software for computations with polynomial systems. Specific topics for the session include, but are not limited to:


Submission Guidelines


  • On the Implementation of CGS Real QE

    Ryoya Fukasaku (Tokyo University of Science, Japan)
    Hidenao Iwane (Fujitsu Laboratories LTD / National Institute of Informatics, Japan)
    Yosuke Sato (Tokyo University of Science, Japan)

    Abstract: A real quantifier elimination method (CGS Real QE) based on the theory of real root counting and the computation of comprehensive Groebner systems (CGSs) originally introduced by Weispfenning in 1998 was improved by us with a simpler and more intuitive algorithm in 2015. Our algorithm eliminates all possible quantifiers from a given basic first order formula using equalities which are contained in the given quantified formula not only explicitly but also implicitly. It returns an equivalent quantifier free formula if the equalities generate a zero dimensional ideal, otherwise it transforms the given formula into an equivalent first order formula such that any atomic sub-formula containing some quantified variable is a strict inequality. Our method is implemented in the computer algebra system Maple and released as open software which still continue to be developing. It is satisfactorily efficient for formulas containing many equalities.
    In this talk, we introduce several key issues which are important for practical implementation of our method. To be more precise, we focus on the following issues.
    - Several simplification techniques.
    - Optimization of CGS computations for CGS Real QE.
    - How to deal with strict inequalities and weak inequalities.

  • Need Polynomial Systems be Doubly-exponential?

    James H. Davenport (University of Bath, UK)
    Matthew England (Coventry University, UK)

    Abstract: Polynomial Systems, or at least their algorithms, have the reputation of being doubly-exponential in the number of variables [MayrMayer1982, DavenportHeintz1988]. Nevertheless, the Bezout bound tells us that that number of zeros of a zero-dimensional system is singly-exponential in the number of variables. How should this contradiction be reconciled?
    We first note that [MayrRitscher2013] shows that the doubly exponential nature of Groebner bases is doubly exponential in the dimension of the ideal, not (as in [MayrMayer1982]) the number of variables. The Cylindrical Algebraic Decomposition method of Collins produces a doubly-exponential number of polynomials of doubly-exponential degree.
    In ISSAC 2015 we showed how, under suitable assumptions, notably about the lack of non-trivial contents, the number of polynomials could be shown to be only doubly-exponential in the (complex) dimension. Here we present some preliminary results for the degree, essentially by using Groebner-base methods.

  • NDEmathema: An Innovative Web-based Automated Symbolic Computing Platform for Nonlinear Differential Equations

    Yinping Liu (East China Normal University, China)
    Ruoxia Yao (Shaanxi Normal University, China)
    Zhibin Li (East China Normal University, China)
    Le Yang (East China Normal University, China)
    Xiaoyan Tang (East China Normal University, China)

    Abstract: A Web-based knowledge database and computing platform for nonlinear differential equations is presented, which could provide com- puting and graphing based on symbolic computing system Maple and some of its built-in packages. Users can not only calculate specific types of analytical solutions of nonlinear differential systems by calling the packages, but also carry out any symbolic computations associated with equations and other kinds of simple computations in an interactive mode with visual output. The knowledge database of differential equations has all functions of the general database. Furthermore, each equation has a web page to show its properties and research results. In addition, each mathematica formula is stored in its infix form in the knowledge database and can be displayed visually.

  • Fault-Tolerant Rational Reconstruction Applied to Implicitization of Hypersurfaces

    John Abbott (University of Genoa, Italy)

    Abstract: It is well known that computations on polynomials with rational coefficients can be very costly. Moreover, in many computations the sizes of the coefficients in the final result are far smaller than those encountered in the intermediate steps. Therefore, for faster computation in such cases, a modular approach can be adopted: perform the computation modulo several primes, and then use rational reconstruction to obtain the coefficients of the true, non-modular answer.
    Two important aspects must be addressed when using a modular approach: how many different primes are needed to permit reconstruction of the true result; and how to handle "bad primes", i.e. those where the modular computation yields an answer which is not the reduction of the true result.
    In the case of implicitization of hypersurfaces there is no useful coefficient bound, and only a partial criterion for detecting bad primes. We present a technique for fault-tolerant rational reconstruction (based on continued fractions), and show how it can be used to overcome our limited knowledge about bad primes and final coefficient size, and thus to compute quickly the implicit polynomial with rational coefficients.
    This algorithm is implemented and available in CoCoALib and CoCoA-5.

  • New, Practical Algorithms for Implicitization of Hypersurfaces

    Anna M. Bigatti (University of Genoa, Italy)
    with J. Abbott and L. Robbiano

    Abstract: The literature about implicitization is so vast that it is almost impossible to mention the entire body of research on this topic. The elegance of solving this problem via elimination with Groebner Bases is however afflicted by its well known poor execution speed.
    We present new, practical algorithms for the hypersurface implicitization problem: namely, given a parametric description in terms of polynomials or rational functions of a hypersurface, find its implicit equation.
    We present two new algorithms for the case of polynomial parametrizations: the first, ``ElimTH'', has as main step the computation of an elimination ideal via a degree-truncated, homogeneous Groebner basis. The other algorithm, ``Direct'', computes the implicitization directly using an approach inspired by the generalized Buchberger-Moeller algorithm.
    Either of these new algorithms, or indeed any other algorithm for the implicitization of polynomial parametrizations, may be used by the third algorithm, ``RatPar'', for computing the implicitization of parametrizations expressed by rational functions.
    These new algorithms are implemented and available in CoCoALib and CoCoA-5.

  • Epsilon 1: A Software Library for Triangular Decomposition

    Dongming Wang*, Chenqi Mou, and Rina Dong (Beihang University, China)
    *On leave from CNRS, France

    Abstract: Epsilon is a library of functions implemented in Maple and Java for polynomial elimination and triangular decomposition with applications. Its first version, Epsilon 0.618 (http://wang.cc4cm.org/epsilon/), was developed by the first author and has been distributed with his book "Elimination Practice: Software Tools and Applications" since 2004. It is capable of triangularizing systems of multivariate polynomials or ordinary differential polynomials and decomposing (differential) polynomial systems into (differential) triangular systems of various kinds, with applications to irreducible or unmixed decomposition of algebraic varieties, primary decomposition of polynomial ideals, and automated geometric reasoning.
    Epsilon 1 is an enhanced version of Epsilon 0.618, with incompatible routines updated and two new modules integrated: one module contains functions for triangular decomposition of polynomial systems over finite fields and the other contains functions for normal and comprehensive triangular decomposition of polynomial systems. In this talk, we give a brief introduction to Epsilon 1 and present the main functionalities of the two new modules. Implementation issues will be discussed and experimental results will be provided to show the remarkable performance of Epsilon functions in terms of computational efficiency and quality of output, in comparison with similar functions in other software packages.

  • GBLA - A Groebner Basis Linear Algebra Package

    Christian Eder (University of Kaiserslautern, Germany)
    Jean-Charles Faugere (INRIA-UPMC-CNRS, France)

    Abstract: GBLA (Groebner Basis Linear Algebra) and is the first plain C open source package available for specialized linear algebra in Groebner basis-like computations.
    Starting from the ideas of Faugere and Lachartre (FL) we further exploit underlying structures of those taking advantage of block patterns by using a special data structure called multilines. Moreover, we discuss a new order of operations for the reduction process. Multiline data structures are also very convenient to manage efficiently the cache while at the same time reducing memory overhead.
    The code is optimized for prime fields of various size using SIMD vectorization. In various different experimental results we show that GBLA performs better than FL or Magma in sequential computations (up to 40% faster) and scales much better than FL for a higher number of CPU cores: On 32 cores we reach a scaling of up to 26, GBLA is up to 7 times faster than FL. Further, GBLA can be used with different parallel schedulers.
    We also developed a new advanced storage format that exploits the fact that our matrices are coming from Groener basis computation, shrinking storage by a large factor. A huge database of our matrices is freely available with GBLA.

  • Common Divisors of Solvable Polynomials in JAS

    Heinz Kredel (University of Mannheim, Germany)

    Abstract: We present generic, type safe (non-unique) common divisors of solvable polynomials software. The solvable polynomial rings are defined with non-commuting variables, moreover, in case of parametric (solvable) coefficients the main variables may not commute with the coefficients. The interface, class organization is described in the object-oriented programming environment of the Java Algebra System (JAS). The implemented algorithms can be applied, for example, in solvable extension field and root construction. We show the design and feasibility of the implementation in the mentioned applications.