Fast interpolation and multiplication of unbalanced polynomials
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914979473522688 |
|---|---|
| author | Giorgi, Pascal Grenet, Bruno Cray, Armelle Perret du Roche, Daniel S. |
| author_facet | Giorgi, Pascal Grenet, Bruno Cray, Armelle Perret du Roche, Daniel S. |
| contents | We consider the classical problems of interpolating a polynomial given a black box for evaluation, and of multiplying two polynomials, in the setting where the bit-lengths of the coefficients may vary widely, so-called unbalanced polynomials. Writing s for the total bit-length and D for the degree, our new algorithms have expected running time $\tilde{O}(s \log D)$, whereas previous methods for (resp.) dense or sparse arithmetic have at least $\tilde{O}(sD)$ or $\tilde{O}(s^2)$ bit complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_10139 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast interpolation and multiplication of unbalanced polynomials Giorgi, Pascal Grenet, Bruno Cray, Armelle Perret du Roche, Daniel S. Symbolic Computation Computational Complexity We consider the classical problems of interpolating a polynomial given a black box for evaluation, and of multiplying two polynomials, in the setting where the bit-lengths of the coefficients may vary widely, so-called unbalanced polynomials. Writing s for the total bit-length and D for the degree, our new algorithms have expected running time $\tilde{O}(s \log D)$, whereas previous methods for (resp.) dense or sparse arithmetic have at least $\tilde{O}(sD)$ or $\tilde{O}(s^2)$ bit complexity. |
| title | Fast interpolation and multiplication of unbalanced polynomials |
| topic | Symbolic Computation Computational Complexity |
| url | https://arxiv.org/abs/2402.10139 |