Strategie di Calcolo di Basi di Groebner

Le basi di Groebner sono state introdotte da Buchberger nel 1965 e forniscono un potente strumento teorico e computazionale in algebra commutativa. Dato un sistema di equazioni polinomiali in più variabili, una base di Groebner consiste in un insieme di rappresentanti canonici per l'ideale generato dai polinomi del sistema. Una volta nota la base di Groebner si hanno a disposizione diversi strumenti efficaci per investigare e analizzare le proprietà geometriche e algebriche del sistema, nonché per risolverlo. Tra le altre cose si può capire se il sistema ha un numero finito di soluzioni e, se non è così, qual è la dimensione dello spazio delle soluzioni, oppure trasformare delle equazioni parametriche in equazioni implicite. Per definire le basi di Groebner bisognerà prima introdurre alcuni particolari ordinamenti nell'insieme dei prodotti delle variabili (monomi), chiamati term orders. Fissato un term order, ogni polinomio in n indeterminate si scrive in modo unico con i monomi ordinati secondo l'ordinamento fissato. In particolare risulta ben definito il monomio più grande rispetto al term order, detto monomio iniziale. Una base di Groebner di un ideale I consiste in un insieme di generatori di I tale che i monomi iniziali dei suoi elementi generino l'ideale iniziale di I, cioè l'ideale monomiale generato dai monomi iniziali di tutti i polinomi di I. Si noti che la base di Groebner di un ideale I dipenderà dalla scelta del term order. Alcuni di essi hanno proprietà particolari molto utili per analizzare il sistema di polinomi, come citato in precedenza. Ad esempio il term order lessicografico permette di eliminare una o più variabili dal sistema. Purtroppo per questo term order risulta poco efficiente calcolare una base di Groebner con un metodo diretto, come ad esempio con l'algoritmo proposto da Buchberger. Una strategia vincente consiste nel calcolare la base di Groebner rispetto ad un diverso term order, e poi convertirla nella base di Groebner rispetto al term order lessicografico. In questo testo, dopo aver esposto i risultati teorici necessari, presenteremo due algoritmi per convertire una base di Groebner: l'algoritmo FGLM e il Groebner Walk. L'algoritmo FGLM è stato il primo proposto, funziona in particolare per ideali zero dimensionali ma può essere generalizzato in maniera abbastanza efficace al caso generale. Esso sfrutta metodi di algebra lineare nello spazio vettoriale costituito dall'anello quoziente dell'anello dei polinomi modulo un ideale I. Il secondo metodo invece sfrutta le proprietà geometriche di un fan formato da coni associati ad un ideale I, detto Groebner fan. Ogni cono del fan è essenzialmente la classe di equivalenza dei term orders che determinano la stessa base di Groebner di I. Partendo da una certa base di Groebner G e un term order che la individua, si cammina tra i diversi coni del fan, spezzando la conversione della base in più conversioni fra basi di Groebner rispetto ai term orders individuati da coni adiacenti. In questo modo si giunge al cono associato alla base di Groebner obiettivo cercata. Infine verrà presentata una nuova strategia per risolvere il problema dell'eliminazione di un insieme di variabili da un ideale che sfrutta in maniera efficace il Groebner Walk. L'idea fondamentale sta nel considerare non un metodo che valga in generale per qualunque ideale, ma disegnare un algoritmo che sfrutti le proprietà dell'ideale di volta in volta considerato.