A faster square-free factorization algorithm for multivariable polynomials
Weile Huang
BASIS International School Guangzhou
DOI: https://doi.org/10.59429/esta.v12i4.12675
Keywords: multivariate polynomial; square-free decomposition; sparse polynomial
Abstract
This paper provides a faster algorithm for multivariate square-free decomposition, using random primes as coefficients of univariate substituting variables instead of p-adic construction, and returning to the multivariate expression using the unique prime factorization property of integers.
References
[1] Yun, D. (1976). On square-free decomposition algorithms. In Proceedings of the third ACM symposium on Symbolic and Algebraic Computation (pp. 26-35).
[2] Thiemann, R., Yamada, A. (2016). Polynomial Factorization. Archive of Formal Proofs.
[3] Gathen, J. von zur, Gerhard, J. (2013). Modern computer algebra. Cambridge University Press.
[4] J. Hu and M. Monagan. A fast parallel sparse polynomial GCD algorithm. Journal of Symbolic Computation, 105:28-63, 2021.