Factoring sparse polynomials fast
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910843465105408 |
|---|---|
| author | Demin, Alexander van der Hoeven, Joris |
| author_facet | Demin, Alexander van der Hoeven, Joris |
| contents | Consider a sparse polynomial in several variables given explicitly as a sum of non-zero terms with coefficients in an effective field. In this paper, we present several algorithms for factoring such polynomials and related tasks (such as gcd computation, square-free factorization, content-free factorization, and root extraction). Our methods are all based on sparse interpolation, but follow two main lines of attack: iteration on the number of variables and more direct reductions to the univariate or bivariate case. We present detailed probabilistic complexity bounds in terms of the complexity of sparse interpolation and evaluation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_17380 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Factoring sparse polynomials fast Demin, Alexander van der Hoeven, Joris Symbolic Computation Commutative Algebra Consider a sparse polynomial in several variables given explicitly as a sum of non-zero terms with coefficients in an effective field. In this paper, we present several algorithms for factoring such polynomials and related tasks (such as gcd computation, square-free factorization, content-free factorization, and root extraction). Our methods are all based on sparse interpolation, but follow two main lines of attack: iteration on the number of variables and more direct reductions to the univariate or bivariate case. We present detailed probabilistic complexity bounds in terms of the complexity of sparse interpolation and evaluation. |
| title | Factoring sparse polynomials fast |
| topic | Symbolic Computation Commutative Algebra |
| url | https://arxiv.org/abs/2312.17380 |