Polynomial reduction is one of the main tools in computational algebra with innumerable applications in many areas, both pure and applied. Since many years both the theory and an efficient design of the related algorithm have been solidly established. This paper presents a definition of the generic concept of polynomial reduction structure, studies its features and highlights the aspects needed in order to grant and to efficiently test the main properties (Noetherianity, confluence, ideal membership). The most significant aspect of this analysis is a negative reappraisal of the role of the notion of term ordering which is usually considered a central and crucial tool in the theory. In fact, as it was already established in the computer science context in relation with termination of algorithms, most of the properties can be obtained simply considering a well founded order, while the classical requirement that it be preserved by multiplication is irrelevant. The last part of the paper shows how the polynomial basis concepts present in literature are interpreted in our language and their properties are consequences of the general results established in the first part of the paper.

A general framework for Noetherian well ordered polynomial reductions

Ceria Michela.;Roggero Margherita
2019-01-01

Abstract

Polynomial reduction is one of the main tools in computational algebra with innumerable applications in many areas, both pure and applied. Since many years both the theory and an efficient design of the related algorithm have been solidly established. This paper presents a definition of the generic concept of polynomial reduction structure, studies its features and highlights the aspects needed in order to grant and to efficiently test the main properties (Noetherianity, confluence, ideal membership). The most significant aspect of this analysis is a negative reappraisal of the role of the notion of term ordering which is usually considered a central and crucial tool in the theory. In fact, as it was already established in the computer science context in relation with termination of algorithms, most of the properties can be obtained simply considering a well founded order, while the classical requirement that it be preserved by multiplication is irrelevant. The last part of the paper shows how the polynomial basis concepts present in literature are interpreted in our language and their properties are consequences of the general results established in the first part of the paper.
2019
95
100
133
Ideal membership; Polynomial reduction; Well founded order
Ceria Michela.; Mora Teo; Roggero Margherita
File in questo prodotto:
File Dimensione Formato  
GeneralFrameworkWellOrdered(Stampata).pdf

Accesso riservato

Tipo di file: PDF EDITORIALE
Dimensione 783.3 kB
Formato Adobe PDF
783.3 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/1737323
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact