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. Ceria and Mora recently developed a new algorithm for squarefree separator polynomials. The algorithm 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 relations among the points’ coordinates. In this paper, we propose a fast implementation in C of the aforementioned algorithm, based on an efficient storing and visiting of the point trie. We complete the implementation with tests on some sets of points, giving different configurations of the corresponding tries.

Efficient Computation of Squarefree Separator Polynomials / M. Ceria, T. Mora, A. Visconti (LECTURE NOTES IN COMPUTER SCIENCE). - In: Mathematical Software : ICMS 2018 / [a cura di] J.H. Davenport, M. Kauers, G. Labahn, J. Urban. - [s.l] : Springer, 2018. - ISBN 9783319964171. - pp. 98-104 (( Intervento presentato al 6. convegno International Congress on Mathematical Software tenutosi a South Bend nel 2018 [10.1007/978-3-319-96418-8_12].

Efficient Computation of Squarefree Separator Polynomials

M. Ceria;A. Visconti
2018

Abstract

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. Ceria and Mora recently developed a new algorithm for squarefree separator polynomials. The algorithm 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 relations among the points’ coordinates. In this paper, we propose a fast implementation in C of the aforementioned algorithm, based on an efficient storing and visiting of the point trie. We complete the implementation with tests on some sets of points, giving different configurations of the corresponding tries.
Separator polynomials; Point trie
Settore INF/01 - Informatica
Settore MAT/02 - Algebra
2018
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
11_MC_conf_ICMS_CMV.pdf

accesso riservato

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 345.87 kB
Formato Adobe PDF
345.87 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

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/2434/583927
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact