Gröbner bases offer a conceptual technology for dealing with nonlinear problems in various contexts. Appearing ubiquitously in the science and technology, they often constitute the only possibility to solve a concrete problem. Dealing with the high computational complexity in practical implementations need advances in theory. In this session, we will discuss the range of applicability of modern Gröbner bases, addressing generalizations to the coefficient rings, to the non-commutative and even non-associative algebras and rings, to name a few.
Since this year ICMS is an online (or virtual) conference, only discussion sessions will be live.
Our session has three slots on Monday, July 13th
Noriyuki Horigome, Akira Terui, and Masahiko Mikawa
Matías Bender
Teo Mora and Michela Ceria (three subslots in one)
Christian Eder et al.
Tobias Metzlaff et al.
Viktor Levandovskyy
and one subslot on Thursday, July 16th jointly with Session D Computational Algebraic Analysis
Francisco Jesús Castro Jiménez.
Matías Bender, TU Berlin, Germany (joint with Jean-Charles Faugère and Elias Tsigaridas). Gröbner bases and sparse polynomial systems.
Gröbner bases are one the most powerful tools in algorithmic nonlinear algebra and a standard tool to solve polynomial systems. Their computation is an intrinsically hard problem with complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. For example, several problems in computer-aided design, robotics, vision, biology, kinematics, cryptography, and optimization involve sparse systems where the input polynomials have a few non-zero terms. In this talk, we discuss how to solve polynomial systems faster by exploiting their sparsity. We do so by introducing tools coming from toric geometry to the Gröbner-basis framework. Our strategy is to perform our computations over multigraded semigroup algebras associated to the Newton polytopes of the input systems. We present the first algorithm to compute Gröbner bases for sparse systems that, under regularity assumptions, performs no redundant computations. Additionally, we discuss the complexity of our approach and its dependence on the combinatorics of the input polytopes. Our complexity bounds generalize the classical results regarding dense systems.
Francisco Jesús Castro Jiménez, University of Seville, Spain. Echelons of multivariate power series and nested linear Artin Approximation.
This talk is based on a joint work with M.E. Alonso, H. Hauser and Ch. Koutschan. We first introduce the notion of echelon of a multivariate power series ring with coefficients in a field. This notion generalizes the one of ideal. We then prove a division theorem for echelons, analogous to the Weierstrass-Grauert-Hironaka division theorem for power series ideals, and, as a consequence, we describe a method to construct a (possibly infinite) standard basis for any given echelon. As an application we will revisit Gabrielov's famous example for the failure of nested analytic Artin Approximation.Noriyuki Horigome, Akira Terui, and Masahiko Mikawa, University of Tsukuba, Japan. A Design and an implementation of an Inverse Kinematics Computation in Robotics using Gröbner Basis.
The solution and efficient implementation of the inverse kinematics computation of a 3 degree-of-freedom (DOF) robot manipulator using Gröbner basis is presented. After formulating the forward kinematic problem using the Denavit–Hartenberg Convention, the inverse kinematic problem is derived as a system of algebraic equations by conversion of trigonometric expression to polynomials. Then, the system is triangularized by computing the Gröbner basis with respect to the lexicographic order and solved by appropriate solvers. The manipulator has been constructed using LEGO Mindstorms EV3, and the main system has been implemented with the programming language Python. Gröbner bases are computed with the computer algebra system Risa/Asir, called from Python via OpenXM, an infrastructure for communicating mathematical information among different software/languages. SymPy is used for solving the triangular system, in which different methods have been tested: the exact solver, the multivariate Newton’s method and the univariate Newton’s method with successive substitution, for comparison of the accuracy of the solution and the efficiency. Since our implementation is written in Python, it is portable and can be incorporated with robotics simulators such as the Robot Operating System (ROS).Teo Mora, University of Genoa, Italy and Michela Ceria, University of Milan, Italy. Do It Yourself: Buchberger and Janet bases over effective rings.
Abstract (pdf).Tobias Metzlaff, INRIA Sophia Antipolis, France, et al. Gröbner bases over K<X> and Z<X> in theory and practice.
We report on the recent theoretical adoption and implementation of non-commutative Gröbner bases both over fields and over the ring Z with more principal ideal rings in mind, which was accomplished in parallel. In both cases we are based on the Letterplace correspondance of La Scala and Levandovskyy. The corresponding subsystem of SINGULAR is called LETTERPLACE. In addition to division with remainder algorithm, we also provide algorithms for syzygy bimodules and lifting. Despite a certain similarity, the case of rings as coefficients demostrates crucial intrinsic differences, compared to the case of fields. We also remark on models of computation and on decidability. This is a joint work with Karim Abou Zeid, Viktor Levandovskyy (RWTH Aachen,Germany) and Hans Schönemann (TU Kaiserslautern, Germany).Christian Eder, TU Kaiserslautern, Germany et al. New Software for Symbolic Solving.
In this talk we present work-in-progress on a new symbolic solver based on the fast F4 implementation in the GB library. We present different, partly new methods and show the current status of the project. We also give insight on fast specialized linear algebra we use for our attempt. This is a joint project with Mohab Safey El-Din, Jean-Charles Faugère and Jeremy Berthomieu from the PolSys Team in Paris, Franz-Josef Pfreundt from the Fraunhofer ITWM in Kaiserslautern and Bernd Sturmfels from the MPI Leipzig.Viktor Levandovskyy, RWTH Aachen, Germany. The state of the art of Gröbner bases and technology in mid-2020.
We will overview the recent achievements in all fields: theory, algorithmics, implementation and complexity, connected to Gröbner bases in associative algebras.A short abstract will appear on the permanent conference web page (see below) as soon as accepted.
An extended abstract may be submitted for the conference proceedings that will be distributed during the meeting.
A journal special issue consisting of full papers will be organized immediately after the meeting.
If you would like to give a talk at ICMS, you need to submit first a short abstract and then later an extended abstract. See the guidelines for the details.
After the meeting, the submission guideline for a journal special issue will be communicated to you by the session organizers.
© 2020. All rights reserved.
