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 条

[1] A fast parallel sparse polynomial GCD algorithm
Hu, Jiaxiong
Monagen, Michael
JOURNAL OF SYMBOLIC COMPUTATION, 2021, 105 : 28 - 63
[2] BIT COMPLEXITY OF POLYNOMIAL GCD ON SPARSE REPRESENTATION
Huang, Qiao-long
Gao, Xiao-shan
MATHEMATICS OF COMPUTATION, 2025,
[3] A Fast Parallel Sparse Polynomial GCD Algorithm
Hu, Jiaxiong
Monagan, Michael
PROCEEDINGS OF THE 2016 ACM INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION (ISSAC 2016), 2016, : 271 - 278
[4] Computing Sparse GCD of Multivariate Polynomials via Polynomial Interpolation
Min Tang
Bingyu Li
Zhenbing Zeng
Journal of Systems Science and Complexity, 2018, 31 : 552 - 568
[5] Computing Sparse GCD of Multivariate Polynomials via Polynomial Interpolation
Tang, Min
Li, Bingyu
Zeng, Zhenbing
JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY, 2018, 31 (02) : 552 - 568
[6] Computing Sparse GCD of Multivariate Polynomials via Polynomial Interpolation
TANG Min
LI Bingyu
ZENG Zhenbing
JournalofSystemsScience&Complexity, 2018, 31 (02) : 552 - 568
[7] Polynomial GCD
Bruckman, PS
FIBONACCI QUARTERLY, 1998, 36 (05): : 472 - 472
[8] 3 NEW ALGORITHMS FOR MULTIVARIATE POLYNOMIAL GCD
SASAKI, T
SUZUKI, M
JOURNAL OF SYMBOLIC COMPUTATION, 1992, 13 (04) : 395 - 411
[9] APPROXIMATE POLYNOMIAL GCD
Elias, Jan
Zitko, Jan
PROGRAMS AND ALGORITHMS OF NUMERICAL MATHEMATICS 16, 2013, : 63 - 68
[10] NEW LOOK AT CLASSICAL ALGORITHMS FOR POLYNOMIAL RESULTANT AND GCD CALCULATION
BARNETT, S
SIAM REVIEW, 1974, 16 (02) : 193 - 206

← 1 2 3 4 5 →