Algorithms for zero-dimensional ideals

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

Program and abstracts of the session: PDF

Organizers:

Speakers (final list):

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.