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