Logo Università degli Studi di Milano



 
 
Notizie  

Towards Degroebnerization. efficient computation of squarefree separator polynomials.

9 novembre 2018 alle 11.00

via Saldini 50, aula C - Milano

Relatrice: Dott.ssa: Michela Ceria

Persona di riferimento: Andrea Visconti

Abstract

Dato un insieme finito di punti distinti, una famiglia di separatori è un insieme di polinomi, ognuno corrispondente a un punto dell'insieme dato, tali che ciascuno di essi prende valore uno se valutato nel punto corrispondente e zero in tutti gli altri.
I separatori sono elementi costitutivi per l'interpolazione polinomiale e possono essere usati in varie applicazioni quali statistica algebrica, reverse engineering, etc.
Ceria e Mora hanno recentemente sviluppato un algoritmo che calcola polinomi separatori squarefree ed evita la moltiplicazione per fattori ridondanti, cosa che invece caratterizzava le formule per i separatori che si ritrovano comunemente in letteratura.
Per evitare questo genere di ridondanza, l'algoritmo utilizza come strumento la struttura detta point trie (definita da Felszeghy-Ráth-Rónyai nell'algoritmo Lex Game) che dà una rappresentazione compatta delle relazioni tra le coordinate dei punti.
In questo seminario, esaminiamo l'algoritmo di Ceria e Mora e ne proponiamo una implementazione efficiente nel linguaggio C. Tale implementazione si basa su una lettura e memorizzazione efficiente del point trie.
A partire da questo, diamo anche una panoramica sui progressi attuali relativi a questa attività di ricerca: infatti è possibile implementare una versione migliorata, che utilizza questo algoritmo combinato con l'iterative Lex Game di Ceria-Mora, allo scopo di dare anche le forme normali dei polinomi separatori (che sono in effetti le forme usate nelle applicazioni) senza passare attraverso il computo delle basi di Groebner (tale computo è piuttosto inefficiente), differentemente da quanto fatto in genere in letteratura.
La Degroebnerizzazione ha inizio...

07 novembre 2018
Torna ad inizio pagina