Fast resolution of integer Vandermonde systems
The resolution of polynomial interpolation problems with integer coefficients directly involves the open issue of the integer inversion of a general Vandermonde matrix defined over the field Z/pZ, for p prime number. The purpose of this paper is to demonstrate the possibility to invert a Vandermonde...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Accademia Peloritana dei Pericolanti
2014-10-01
|
| Series: | Atti della Accademia Peloritana dei Pericolanti : Classe di Scienze Fisiche, Matematiche e Naturali |
| Online Access: |
http://dx.doi.org/10.1478/AAPP.921A2
|
| _version_ | 1818756392612265984 |
|---|---|
| author | Rosa di Salvo Luigia Puccio |
| author_facet | Rosa di Salvo Luigia Puccio |
| author_sort | Rosa di Salvo |
| collection | DOAJ |
| description | The resolution of polynomial interpolation problems with integer coefficients directly involves the open issue of the integer inversion of a general Vandermonde matrix defined over the field Z/pZ, for p prime number. The purpose of this paper is to demonstrate the possibility to invert a Vandermonde matrix with integer mod p coefficients and exactly compute the integer inverse matrix in the ring Mat(Z/pZ) of square matrices over Z/pZ through the new fast algorithm InVanderMOD. The explicit formula derived for the integer inversion of Vandermonde matrices entirely develops inside the field of the integers mod p, with due consideration to the operation of integer division. The inversion procedure InVanderMOD is valid for any prime number p and competitive in terms of computational effort, since its computational cost is less than O(n^3). |
| first_indexed | 2024-12-18T05:54:19Z |
| format | Article |
| id | doaj.art-7bd88f60c91f44ab86da120a7425bd08 |
| institution | Directory Open Access Journal |
| issn | 0365-0359 1825-1242 |
| language | English |
| last_indexed | 2024-12-18T05:54:19Z |
| publishDate | 2014-10-01 |
| publisher | Accademia Peloritana dei Pericolanti |
| record_format | Article |
| series | Atti della Accademia Peloritana dei Pericolanti : Classe di Scienze Fisiche, Matematiche e Naturali |
| spelling | doaj.art-7bd88f60c91f44ab86da120a7425bd082022-12-21T21:18:50ZengAccademia Peloritana dei PericolantiAtti della Accademia Peloritana dei Pericolanti : Classe di Scienze Fisiche, Matematiche e Naturali0365-03591825-12422014-10-01921A210.1478/AAPP.921A2AAPP.921A2Fast resolution of integer Vandermonde systemsRosa di Salvo0Luigia Puccio1 Dipartimento di Matematica e Informatica, Universita' degli Studi di Messina, Messina, Italy Dipartimento di Matematica e Informatica, Universita' degli Studi di Messina, Messina, Italy The resolution of polynomial interpolation problems with integer coefficients directly involves the open issue of the integer inversion of a general Vandermonde matrix defined over the field Z/pZ, for p prime number. The purpose of this paper is to demonstrate the possibility to invert a Vandermonde matrix with integer mod p coefficients and exactly compute the integer inverse matrix in the ring Mat(Z/pZ) of square matrices over Z/pZ through the new fast algorithm InVanderMOD. The explicit formula derived for the integer inversion of Vandermonde matrices entirely develops inside the field of the integers mod p, with due consideration to the operation of integer division. The inversion procedure InVanderMOD is valid for any prime number p and competitive in terms of computational effort, since its computational cost is less than O(n^3). http://dx.doi.org/10.1478/AAPP.921A2 |
| spellingShingle | Rosa di Salvo Luigia Puccio Fast resolution of integer Vandermonde systems Atti della Accademia Peloritana dei Pericolanti : Classe di Scienze Fisiche, Matematiche e Naturali |
| title | Fast resolution of integer Vandermonde systems |
| title_full | Fast resolution of integer Vandermonde systems |
| title_fullStr | Fast resolution of integer Vandermonde systems |
| title_full_unstemmed | Fast resolution of integer Vandermonde systems |
| title_short | Fast resolution of integer Vandermonde systems |
| title_sort | fast resolution of integer vandermonde systems |
| url |
http://dx.doi.org/10.1478/AAPP.921A2
|
| work_keys_str_mv | AT rosadisalvo fastresolutionofintegervandermondesystems AT luigiapuccio fastresolutionofintegervandermondesystems |