A New Sparse Polynomial GCD by Separating Terms

被引：0

作者：

Huang, Qiao-Long ^{[1
]}

Monagan, Michael ^{[2
]}

机构：

[1] Shandong Univ, Sch Math, Jinan, Peoples R China

[2] Simon Fraser Univ, Dept Math, Burnaby, BC, Canada

来源：

PROCEEDINGS OF THE 2024 INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION, ISSAC 2024 | 2024年

基金：

国家重点研发计划; 加拿大自然科学与工程研究理事会;

关键词：

Polynomial GCD; Sparse Polynomial; Kronecker Substitution; GREATEST COMMON DIVISORS; EUCLIDS ALGORITHM;

D O I：

10.1145/3666000.3669684

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We propose a new sparse GCD algorithm for multivariate polynomials over finite fields. Our algorithm uses a new type of substitution to recover the terms of the GCD in batches. We present a detailed complexity analysis and experimental results which show that our algorithm is faster than Zippel's GCD algorithm and competitive with the Monagan-Hu GCD algorithm.

引用

页码：134 / 142

页数：9

共 50 条

[41] On the number of terms of a composite polynomial
Zannier, Umberto
ACTA ARITHMETICA, 2007, 127 (02) : 157 - 167
[42] A Note on Sparse Polynomial Interpolation in Dickson Polynomial Basis
Imamoglu, Erdal
Kaltofen, Erich L.
ACM COMMUNICATIONS IN COMPUTER ALGEBRA, 2020, 54 (04): : 125 - 128
[43] Sparse polynomial exponential sums
Cochrane, T
Pinner, C
Rosenhouse, J
ACTA ARITHMETICA, 2003, 108 (01) : 37 - 52
[44] On the number of terms of a power of a polynomial
Schinzel, Andrzej
Zannier, Umberto
RENDICONTI LINCEI-MATEMATICA E APPLICAZIONI, 2009, 20 (01) : 95 - 98
[45] Sparse Polynomial Interpolation With Arbitrary Orthogonal Polynomial Bases
Imamoglu, Erdal
Kaltofen, Erich L.
Yang, Zhengfeng
ISSAC'18: PROCEEDINGS OF THE 2018 ACM INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION, 2018, : 223 - 230
[46] Sparse bivariate polynomial factorization
WU WenYuan
CHEN JingWei
FENG Yong
Science China(Mathematics), 2014, 57 (10) : 2123 - 2142
[47] Sparse polynomial interpolation in practice
Van Der Hoeven, Joris
Lecerf, Grégoire
ACM Communications in Computer Algebra, 2015, 48 (3-4): : 187 - 191
[48] Sparse noncommutative polynomial optimization
Igor Klep
Victor Magron
Janez Povh
Mathematical Programming, 2022, 193 : 789 - 829
[49] Sparse bivariate polynomial factorization
Wu WenYuan
Chen JingWei
Feng Yong
SCIENCE CHINA-MATHEMATICS, 2014, 57 (10) : 2123 - 2142
[50] Sparse bivariate polynomial factorization
WenYuan Wu
JingWei Chen
Yong Feng
Science China Mathematics, 2014, 57 : 2123 - 2142

← 1 2 3 4 5 →