ICMS 2014 Session: Software, design and practice, in Parametric polynomial systems

ICMS 2014: Home, Sessions

Organizers

Aim and Scope

Symbulic computations are indispensable touls for exact calculations. For example, we can sulve a system of multivariate pulynomial equations without error using a Groebner basis computation. In engineering applications, however, we usually do not need precise sulutions. We can apply alternative numerical computations such as homotopy method. In case the system contains some parameters, the situation undergoes a complete change. We can not apply any numerical methods. Symbulic computations have a great effect on such a case. Above all, parametric pulynomial manipulations are especially of importance. This session would bring together experts developing softwares in parametric pulynomial systems and allow disseminating new and ongoing results on parametric pulynomial manipulations.

Topics (including, but not limited to)

Publications

Submission Guidelines

Talks/Abstracts

  1. An algorithm for computing Tjurina stratifications of mu-constant deformations using algebraic local cohomology

    Katsusuke Nabeshima(The University of Tokushima, Japan) and Shinichi Tajima (Tsukuba University, Japan)

    In this talk, algebraic local cohomology classes attached to semi-quasihomogeneous hypersurface isolated singularities are considered. A new effective method to compute Tjurina stratifications associated with mu-constant deformation of weighted homogeneous isolated singularities is proposed.
    In 1989, B. Martin and G. Pfister constructed an algorithm of computing parameter dependency of Tjurina numbers of mu-constant deformations of quasi-homogeneous hypersurface isolated singularities. In this talk, we propose an alternative approach, in a context of computational algebraic analysis, to compute Tjurina stratifications of mu-constant deformations. The proposed method also computes on each stratum, via Grothendieck local duality, a parametric standard basis of the relevant ideal quotient J : f, where J stands for the Jacobi ideal of the function f in the local ring of germs of holomorphic functions. The key idea in this approach is the use of algebraic local cohomology classes with parameters. In our previous work, we introduced an efficient algorithm for computing a basis of algebraic local cohomology classes with parameters. By using the algorithm, one can easily compute the ideal quotient J:f for each stratum. Therefore, we can construct an algorithm for computing Tjurina stratifications associated with mu-constant deformation of weighted homogeneous isolated singularities.
    The proposed method has already been implemented in a computer algebra system Risa/Asir. A demonstration of the program is given in the talk.

  2. An implementation method of Boolean Groebner bases and comprehensive Boolean Groebner bases on general computer algebra systems

    Akira Nagai and Shutaro Inoue(Dept. of Mathematical Information Science,Tokyo University of Science, Japan)

    We propose an efficient implementation method to compute a Groebner basis in a polynomial ring over a Boolean ring that is defined as the power set algebra of a finite set. It can be easily implemented on most computer algebra system with a facility to compute Groebner bases in polynomial rings over GF(2).
    In general, a Groebner basis in a polynomial ring over a general Boolean ring (Boolean Groebner basis) can be computed by a modified Buchberger algorithm using a special monomial reduction. In order to implement this algorithm, we have to use a special data structure which is not embedded in most computer algebra systems.
    When a Boolean ring is finite, it is isomorphic to a direct product of GF(2), the simplest Galois field with characteristic 2. This rather obvious observation enables us to have a simple but efficient implementation to compute Boolean Groebner basis on most computer algebra system which has a facility to compute a Groebner basis in a polynomial ring over GF(2).
    Our method divides the computation of a Boolean Groebner basis into many independent computations of Groebner bases in a polynomial ring over GF(2), hence it contains parallel computations in nature and receives much benefit from multi-core architectures of recent computers.
    Our method can also be applied to compute a comprehensive Boolean Groebner basis.

  3. Mathematical hierarchies of Sudoku puzzles and its computation by Boolean Groebner bases

    Shutaro Inoue (Dept. of Mathematical Information Science,Tokyo University of Science, Japan)

    Sudoku that is one of the most popular puzzles in the world can be considered as a kind of combinatorial problem. Any Sudoku puzzle can be solved by propositional calculus. Actually there exist several fast Sudoku solvers based on SAT solver.
    When we solve a Sudoku puzzle as a human, i.e. without a computer, we usually use several techniques such as naked pair/triple, hidden pair/triple, X-wing, XY-wing, etc. Those technique are categorized from the easiest level to the highest level. Most Sudoku puzzle books or web sites of Sudoku puzzles assign the level of difficulty to each puzzle, which is usually given by a heuristic analysis of the applicable techniques. Hence, it might happen that different analyses assign different levels of difficulty to one puzzle.
    Any Sudoku solver based on propositional calculus can not determine the level of difficulty, since we do not have a precise mathematical definition of "the level of difficulty" of Sudoku puzzles.
    Considering a Sudoku puzzle as a singleton set constraint, we define purely mathematical hierarchies of Sudoku puzzles in terms of a general Boolean polynomial ring. We introduce an efficient parametric algorithm using Boolean Groebner bases to determine the hierarchy for a given Sudoku puzzle. According to our experiments through our implementation on the computer algebra system Risa/Asir, there exists a strong positive correlation between our purely mathematical hierarchies of Sudoku puzzles and the levels of difficulty of Sudoku puzzles assigned by a heuristic analysis. The definition of our mathematical hierarchies could be a universal tool which shows mathematical correctness of the level of difficulty given by some heuristic analysis.

  4. A method to determine if two parametric polynomial systems are equal

    Dingkang Wang and Jie Zhou (Academy of Mathematics and Systems Science, CAS, China)

    In this talk, the problem if two parametric polynomial systems are equal will be investigated. Comprehensive Groebner systems (CGS) of parametric polynomial ideal were introduced by Volker Weispfenning in 1992. Since then, many improvements have been made to improve these algorithms to make them useful for different applications.
    An algorithm for discussing Groebner bases with parameters was proposed by Montes, and it was improved using discriminant ideal by Manubens and Montes himself. Suzuki and Sato showed that how traditional implementations of Groebner basis algorithms for polynomial rings over a field could be exploited for computing comprehensive Groebner systems. A speed-up of the algorithm was given by Nabeshima. A newest version for computing CSG was provided by Kapur, Sun and Wang by removing redundant segments. In contract to reduced Groebner bases, which is uniquely determined by the polynomial ideal and the term ordering, however, comprehensive Groebner systems do not have such a good property. Different algorithm may give different results even for a same parametric polynomial ideal. In order to treat this issue, we give a decision method to determine whether two comprehensive Groebner systems are equal. The polynomial ideal membership problem has been solved for the non-parametric case by the classical Groebner bases method, but there is little progress on this problem for the parametric case until now. An algorithm is given for solving this problem through computing comprehensive Groebner systems. What's more, for two parametric polynomial ideals and a constraint over the parameters defined by a constructible set, an algorithm will be given to decide whether one ideal contains the other under the constraint.

  5. QE software based on comprehensive Groebner systems

    Ryoya Fukasaku(Graduate School of Science, Tokyo University of Science, Japan)

    In recent years several drastic improvements have been achieved for the computation of a comprehensive Groebner system(CGS). We now have satisfactorily practical algorithms to compute a concise CGS.
    In this talk, we introduce our two QE implementations, one is in the domain of an algebraically closed field(ACF) and the other is of a real closed field(RCF). Both implementations are based on comprehensive Groebner systems.
    In AFC, it is rather straightforward to construct a QE algorithm using CGS computations. As long as a corresponding CGS computation terminates, we can immediately obtain an equivalent quantifier free formula, which is also in a concise form in most cases. In case the corresponding CGS computation does not terminate in a realistic length of time, we have to abandon this approach if we use a CGS computation as a black box tool. Looking at the recent CGS algorithms in deep, we have found that we can replace a component of the CGS computation by another computation. This observation leads us to a new QE algorithm which consists of hybrid computations of CGS's and parametric unary GCD's. Our implementation on the computer algebra system Risa/Asir is superior to other existing QE implementations such as Projection of Maple or Reduce of Mathematica in most cases.
    In RFC, we have also implemented QE algorithm on Risa/Asir. Our algorithm is essentially based on the QE algorithm of Weispfenning introduced in the early 1990's. Since his algorithm is based on comprehensive Groebner bases and there existed no efficient algorithm to compute comprehensive Groebner systems at that time, there have been very few implementation to date. Though our work on RFC-QE is still ongoing, our implementation is superior to other existing QE implementations in many cases.

  6. SyNRAC: A toolbox for solving real algebraic constraints

    Hidenao IWANE (National Institute of Informatics/Fujitsu Laboratories LTD., Japan), Hitoshi Yanami (Fujitsu Laboratories LTD., Japan) and Hirokazu Anai (Fujitsu Laboratories LTD./Kyushu University, Japan)

    We introduce various aspects of the design and the implementation of a symbolic/symbolic-numeric computation toolbox, called SyNRAC. SyNRAC is a package of commands written in the Maple language and the C language. This package indeed provides an environment for dealing with first-order formulas over the reals. SyNRAC stands for a Symbolic-Numeric toolbox for Real Algebraic Constraints.
    We started the development of SyNRAC in 2002, first appeared in a literature in 2003, with a focus on the implementation of purely symbolic quantifier elimination (QE). One of the big advantages of this approach is that it can deal with parametric and non-convex constraints. The solver to be addressed includes several symbolic-numeric QE algorithms that have recently been implemented to improve the efficiency of its symbolic counterparts without loss of exactness.
    The focus of the implemented algorithms is on practically effective QE for certain industrial/engineering problems and simplification of Tarski formulas.
    Currently the following algorithms are available in SyNRAC:
    - special QE by the Sturm-Habicht sequence for sign definite conditions,
    - special QE by virtual substitution for linear and quadratic formulas,
    - general QE by cylindrical algebraic decomposition,
    - simplification of Tarski formulas, and
    - drawing feasible regions of Tarski formulas.

  7. Software using the Groebner Cover for geometrical loci computation and classification

    Miguel A. Abanades (Universidad Complutense de Madrid, Spain) Francisco Botana (Universidad de Vigo, Spain) Antonio Montes (Universitat Polit├Ęcnica de Catalunya, Spain) Tomas Recio (Universidad de Cantabria, Spain)

    The automatic determination of geometric loci is an important issue in Dynamic Geometry. In Dynamic Geometry systems, it is often the case that locus determination is purely graphical, producing an output that is not robust enough and not reusable by the given software. Moreover, extraneous objects are frequently appended to the true locus as side products of the locus determination process.
    Based on the Groebner Cover algorithm for dicussing parametric polynomial systems, implemented in the Singular grobcov.lib library, we have developed a new method for locus computation. It provides an analytic, exact description of the sought locus, making possible a subsequent precise manipulation of this object by the system.
    Moreover, a complete taxonomy, cataloging the potentially different kinds of geometric objects arising from the locus computation procedure, is introduced, allowing to easily discriminate these objects as either extraneous or as pertaining to the sought locus. The examples justify our choice for dynamic geometry relevant components.
    The software is included in the forthcoming version of the Singular grobcov.lib library.
    The proposed method is illustrated through a webbased application prototype of Geogebra, showing that it has reached enough maturity as to be considered a practical option to be included in the next generation of dynamic geometry environments.

  8. Using Maple's RegularChains library to automatically classify plane geometric loci

    Francisco Botana (Vigo University, Spain) and Tomas Recio (Cantabria University, Spain)

    A taxonomy for automatic computation and component classification of plane geometric loci, expressable through projections of algebraic geometry sets, has been recently proposed by A. Montes, M. Abanades and the authors. This taxonomy has been successfully implemented with the GroebnerCover library (see talk of Antonio Montes in this session), and it is behind the new GeoGebra commands LocusEquation and Envelope.
    Since we handle the loci computation problem in the general framework of parametric polynomial systems solving, we propose here to use, instead of the GroebnerCover approach, the RegularChains library of Maple (and, to be more specific, its ConstructibleSetTools and ParametricSystemTools modules). The implementation of our methods in these libraries shows almost identical results to those obtained with GroebnerCover, thus being an efficient competitor to the previous implementation by Montes et al.'s . Nevertheless, since our new approach is based on a commercial package such as Maple, it cannot be offered for free as a companion of educational interactive geometry environments. On the other side, the extensive list of available algorithms in the RegularChains library promises to be an open door to future enhancements, such as dealing with semialgebraic loci and envelopes.
    A demonstration of our code will be given, along a comparison with results obtained with GroebnerCover.

  9. Solving Parametric Polynomial Systems by RealComprehensiveTriangularize

    Changbo Chen (CIGIT, Chinese Academy of Sciences) and Marc Moreno Maza (University of Western Ontario)

    In the authors' previous work, the concept of comprehensive triangular decomposition of parametric semi-algebraic systems (RCTD for short) was introduced. For a given parametric semi-algebraic system, say S, an RCTD partitions the parametric space into disjoint semi-algebraic sets, above each of which the real solutions of S are described by a finite family of triangular systems.
    Such a decomposition permits to easily count the number of distinct real solutions depending on different parameter values as well as to conveniently describe the real solutions as continuous functions of the parameters. In this talk, we present the implementation of RCTD in the RegularChains library, namely the RealComprehensiveTriangularize command.
    The implementation of RCTD replies on several important functionality of the RegularChains library, including functions for manipulating constructible sets, isolating real roots of regular chains and computing cylindrical algebraic decompositions. It also supports functions for doing real root classification. The interaction of RCTD with these functions are discussed in detail. Other aspects of the implementation, such as the design of user interface, important optimizations are also explained. The use of RCTD is illustrated by solving examples from applications. In particular, we explain in detail how to use it to analyze the stability of several biological systems.