Improvements of convex-dense factorization of bivariate polynomials
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916561379393536 |
|---|---|
| author | Weimann, Martin |
| author_facet | Weimann, Martin |
| contents | We develop a new algorithm for factoring a bivariate polynomial $F\in \mathbb{K}[x,y]$ which takes fully advantage of the geometry of the Newton polygon of $F$. Under a non degeneracy hypothesis, the complexity is $\tilde{\mathcal{O}}(Vr_0^{ω-1} )$ where $V$ is the volume of the polygon and $r_0$ is its minimal lower lattice length. This improves the complexity $\tilde{\mathcal{O}}(d^{ω+1})$ of the classical algorithms which consider the total degree $d$ of $F$ as the main complexity indicator. The integer $r_0\le d$ reflects some combinatorial constraints imposed by the Newton polygon, giving a reasonable and easy-to-compute upper bound for the number of its indecomposable Minkovski summands of positive volume. The proof is based on a new fast factorization algorithm in $\mathbb{K}[[x]][y]$ with respect to a slope valuation, a result which has its own interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_06028 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improvements of convex-dense factorization of bivariate polynomials Weimann, Martin Commutative Algebra 13P05, 68W30 We develop a new algorithm for factoring a bivariate polynomial $F\in \mathbb{K}[x,y]$ which takes fully advantage of the geometry of the Newton polygon of $F$. Under a non degeneracy hypothesis, the complexity is $\tilde{\mathcal{O}}(Vr_0^{ω-1} )$ where $V$ is the volume of the polygon and $r_0$ is its minimal lower lattice length. This improves the complexity $\tilde{\mathcal{O}}(d^{ω+1})$ of the classical algorithms which consider the total degree $d$ of $F$ as the main complexity indicator. The integer $r_0\le d$ reflects some combinatorial constraints imposed by the Newton polygon, giving a reasonable and easy-to-compute upper bound for the number of its indecomposable Minkovski summands of positive volume. The proof is based on a new fast factorization algorithm in $\mathbb{K}[[x]][y]$ with respect to a slope valuation, a result which has its own interest. |
| title | Improvements of convex-dense factorization of bivariate polynomials |
| topic | Commutative Algebra 13P05, 68W30 |
| url | https://arxiv.org/abs/2501.06028 |