Algorithms for zero-dimensional ideals

Session at ACA 2018, conference held in Santiago de Compostela (Spain) from June 18 to June 22, 2018.

Program and abstracts of the session: PDF

Organizers:

Speakers (final list):

  • Mariemi Alonso, Complutense University of Madrid, Spain
    Border basis, Hilbert Scheme of points and flat deformations (Slides PDF)
    (joint work with Jerome Brachat and Bernard Mourrain)
  • Daniel Augot, Inria Saclay – Île-de-France, France
    On the decoding of interleaved and folded Reed-Solomon codes
  • Anna M. Bigatti, University of Genoa, Italy
    Computing and using minimal polynomials (Slides PDF)
    (joint work with John Abbott, Elisa Palezzato, Lorenzo Robbiano)
  • Michela Ceria, Department of Computer Science, University of Milan, Italy
    Combinatorics of ideals of points: a Cerlienco-Mureddu-like approach for an iterative lex game (Slides PDF)
    (joint work with Teo Mora)
  • Martin Kreuzer, University of Passau, Germany
    Computing Subschemes of the Border Basis Scheme (Slides PDF)
    (joint work with Le Ngoc Long and Lorenzo Robbiano)
  • Robin Larrieu, Laboratoire d’informatique de l’École polytechnique, France
    Fast Gröbner basis computation and polynomial reduction in the generic bivariate case (Slides PDF)
    (joint work with Joris van der Hoeven)
  • Teo Mora, University of Genoa, Italy
    De Nugis Groebnerialium 5: Noether, Macaulay, Jordan (Slides PDF)
  • Teo Mora, University of Genoa, Italy
    Solving and bonding 0-dimensional ideals: Möller Algorithm and Macaulay Bases (Slides PDF)
  • Simone Naldi, XLIM — University of Limoges, France
    On the computation of algebraic relations of bivariate polynomials (Slides PDF)
    (joint work with Vincent Neiger and Grace Younes)
  • Hamid Rahkooy, University of Waterloo, Canada
    Computing Recurrence Relations of n-dimensional Sequences Using Dual of Ideals
    (joint work with Angelos Mantzaflaris and Éric Schost)
  • Lorenzo Robbiano, University of Genoa, Italy
    Special Properties of Zero-Dimensional Ideals: new Algorithms (Slides PDF)
    (joint work with Martin Kreuzer and Le Ngoc Long)
  • Thibaut Verron, Johannes Kepler University, Linz, Austria
    Signature-based Criteria for Möller’s Algorithm for Computing Gröbner Bases over PIDs (Slides PDF)
    (joint work with Maria Francis)

Submission of talks (updated dates):

Early submission is encouraged, and early notification will follow.
If you are interested in giving a talk, please send an abstract to the organizers listed below, using this LaTeX template. More than one abstract may be submitted.
April 16th, 2018: deadline for submission of talks.
April 28th, 2018: notification of acceptance.

Aim and scope:

In the last decades, a lot of progress has been made on the study of efficient algorithms related to zero-dimensional ideals, including for solving polynomial systems, i.e. determining the finite set of roots common to a given collection of multivariate polynomials. During this process, it has turned out that these algorithms heavily rely on some routines from linear algebra. This session will focus on the design and the implementation of algorithms specifically tailored for the particular linear algebra problems encountered in this kind of computations. Applications of these techniques will also be considered, such as algebraic cryptanalysis and decoding algorithms for algebraic geometry codes.

Polynomial system solving often involves computing a first Groebner basis, typically with the F5 algorithm, and then working on finding a representation of the sought roots, using for example the FGLM algorithm. In the first step, one has to deal with matrices of large dimension which are sparse and exhibit a noticeable structure. The second step corresponds to finding the nullspace of a matrix with a multi-Krylov structure: the matrix is formed by some vector and its images by successive powers of the so-called multiplication matrices.

It has been observed that these multiplication matrices are most often sparse, a feature that one wants to exploit to obtain faster algorithms. So far, two approaches have been used to achieve this. One is inspired from the block Wiedemann algorithm, involving the computation of the generator for a linearly recurrent matrix sequence; the other one relies on the computation of generators for a multi-dimensional linearly recurrent sequence. This revived interest into the latter problem, with the goal of designing algorithms which outperform the Sakata algorithm, known for its applications to the decoding of algebraic geometry codes. Some approaches have already been described, involving computations with matrices that have a multi-layered block-Hankel structure.

This session aims at gathering the main actors behind the recent advances, and naturally all researchers interested in this topic and its future developments.