Abstract : Polynomial systems are fundamental mathematical objects in algebraic geometry, automated geometric reasoning, cryptography, coding theory, biology, and many other areas of science and engineering, and thus finding the solutions of polynomial systems algorithmically is also of both theoretical and practical importance. This minisymposium aims at bringing together interested researchers to present and to discuss recent work and progress on the theories, algorithms, software, and applications of solving polynomial systems.
Abstract : In this introductory talk of the minisympoisum “Recent Advances on Polynomial System Solving”, I will give a brief overview of the problem of solving polynomial systems, including its theories, methods, softwares, and applications. In particular, basic concepts of three typical methods of Gröbner bases, triangular decomposition, and homotopy continuation for solving polynomial systems will be presented, serving as an introduction of other talks in this minisympoisum to a wider audience of different backgrounds.
[04394] Signature-based algorithm and change of ordering for Groebner basis
Format : Talk at Waseda University
Author(s) :
Masayuki Noro (Rikkyo University)
Abstract : Although the termination is not guaranteed, signature-based algorithm under non-compatible term orderings may give good performance for computing Groebner bases. In such cases, we can apply the notion of Hilbert function for guaranteeing the termination. The Hilbert function is given by a Groebner basis with respect to another term ordering and thus this algorithm is a kind of change of ordering. We compare its performance with the usual Hilbert driven algorithm.
[03913] Dimension results for polynomial systems over complete toric varieties
Abstract : A common computational approach to study affine varieties is to first homogenize the input defining equations. Among other reasons, we do so because the new equations have an associated grading that allows us to reduce our computations to a linear algebra problem. However, the homogenization process might introduce higher components at infinity, changing drastically the geometry of the affine object that we want to study. This is what happens when we homogenize, in the classical sense, sparse polynomials. To overcome this issue, a possible approach is to homogenize the input equations, using their Newton polytopes, over a Cox ring or a polytopal graded subring of it. However, other simpler homogenizations might be possible. In this work, we prove a combinatorial criterion to decide when a candidate homogenization is good, in the sense that it does not introduce higher components at infinity. Additionally, we use our criterion to decide which families of degrees on polytopal algebras lead to regular sequences.
[03633] On the computation of staggered linear bases
Format : Talk at Waseda University
Author(s) :
Amir Hashemi (Isfahan University of Technology)
Hans Michael Moller (Technical University Dortmund)
Abstract : Grobner bases are a powerful tool in polynomial ideal theory with many applications in various areas of science and engineering. Considering an ideal as a vector space, we investigate for such an ideal a particular linear basis, so-called staggered linear basis, which contains a Grobner basis as well. This notion was first introduced by Gebauer and Moller in 1988, however the algorithm that they described for computing these bases was not complete. In this talk, we present a simple and efficient algorithm to compute an staggered linear basis. The new framework is equipped with some novel criteria (including both Buchberger's criteria) to detect superfluous reductions. Finally, we discuss the efficiency of this algorithm compared to the existing methods using a set of benchmark polynomials.
[03688] Square-Free Pure Triangular Decomposition of Zero-Dimensional Polynomial Systems
Format : Talk at Waseda University
Author(s) :
Haokun Li (Peking University)
Bican Xia (Peking University)
Tianqi Zhao (Peking University)
Abstract : The concepts of pure chains and square-free pure triangular decomposition (SFPTD) of zero-dimensional polynomial systems are defined. We propose an algorithm for computing SFPTD and prove its arithmetic complexity can be single exponential in the square of the number of variables. We show experimentally that, on most examples in the literature, the algorithm is more efficient than a triangular-decomposition method in Maple, and the real solution isolation method based on SFPTD is very efficient.
[05286] On the bit complexity of roadmap algorithms
Format : Talk at Waseda University
Author(s) :
Eric Schost (University of Waterloo)
Abstract : Roadmaps were introduced by Canny in order to reduce connectivity queries on semi-algebraic sets to similar questions on curves. In the last ten years, with Mohab Safey El Din, we proposed randomized algorithms with an improved complexity - in an algebraic cost model; the bit-complexity analysis remained to be done. I will report on recent work done in this direction with Jesse Elliott.
[03750] Solving semi-algebraic systems arising in applications
Format : Talk at Waseda University
Author(s) :
Changbo Chen (Chongqing Institute of Green and Intelligent Technology, Chinese Academy of Sciences)
Abstract : Semi-algebraic systems, which are systems consisting of polynomial equations and inequalities, naturally appear in many applications. To solve them efficiently, it is important to exploit their particular structures. In this talk, I will present specialized algorithms designed for solving semi-algebraic systems arising in several applications, namely computing the steady states of parametric biological systems, automatic parallelization of loops, and detecting quantum correlations.
[04993] Root Separation Bounds
Format : Talk at Waseda University
Author(s) :
Vikram Sharma (The Institute of Mathematical Sciences Chennai)
Abstract : Root separation bounds are a classical topic in algebraic number theory. They also play an important role in the analysis of algorithms for finding the roots of polynomials. In this talk, we will start with some classical results of Mignotte and Davenport and trace the recent development that has occurred in this area.
