Towards Degroebnerization. efficient computation of squarefree separator polynomials.
2018-11-02 at 11.00a.m.
via Saldini 50, aula C - Milan
Speaker: dr. Michela Ceria
Reference people: Andrea Visconti
Given a finite set of distinct points, a separator family is a set of polynomials, each one corresponding to a point of the given set, such that each of them takes value one at the corresponding point, whereas it vanishes at any other point of the set. Separator polynomials are fundamental building blocks for polynomial interpolation and they can be employed in several practical applications, such that, for example, algebraic statistics or reverse engineering.
Ceria and Mora recently developed a new algorithm for separator polynomials, getting squarefree polynomials and avoiding the (redundant) multiplication by useless multiplicative factors, which characterizes the separator formulas usually found in literature. The algorithm, to avoid redundancy, employs as a tool the point trie structure, first defined by Felszeghy-Ráth-Rónyai in their Lex game algorithm, which gives a compact representation of the relation among the points' coordinates.
In this talk, we examine Ceria-Mora algorithm and we propose a fast implementation in C of the aforementioned algorithm, based on an efficient storing and visiting of the point trie.
Starting from this point, we give also an overview on the current progresses on this project: indeed it is possible to give an improvement, based on this algorithm and on Ceria-Mora iterative lex game, in order to give also normal forms of separator polynomials (which are actually used in practical applications) without passing through Groebner bases (whose computation is rather unefficient), differently from what usually done in literature.
Degroebnerization is coming...