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 条

[31] SPARSE LOGICAL TERMS
FALL, A
APPLIED MATHEMATICS LETTERS, 1995, 8 (05) : 11 - 15
[32] DEFECTS AND REVISIONS OF ASYMPTOTICALLY FAST ALGORITHM FOR POLYNOMIAL GCD'S
衷仁保
ScienceBulletin, 1985, (02) : 170 - 171
[33] Approximate polynomial gcd: Small degree and small height perturbations
von zur Gathen, Joachim
Mignotte, Maurice
Shparlinski, Igor E.
JOURNAL OF SYMBOLIC COMPUTATION, 2010, 45 (08) : 879 - 886
[34] Separating Polynomial χ-Boundedness from χ-Boundedness
Brianski, Marcin
Davies, James
Walczak, Bartosz
COMBINATORICA, 2024, 44 (01) : 1 - 8
[35] Approximate polynomial gcd: Small degree and small height perturbations
von zur Catheni, Joachim
Shparlinski, Igor E.
LATIN 2008: THEORETICAL INFORMATICS, 2008, 4957 : 276 - +
[36] The Polynomial Euclidean Algorithm and the Linear Equation AX + BY = gcd(A, B)
Gove Effinger
Gary L. Mullen
The Mathematical Intelligencer, 2017, 39 : 22 - 25
[37] On the GCD-s of k consecutive terms of Lucas sequences
Hajdu, L.
Szikszai, M.
JOURNAL OF NUMBER THEORY, 2012, 132 (12) : 3056 - 3069
[38] A fully Bayesian sparse polynomial chaos expansion approach with joint priors on the coefficients and global selection of terms
Buerkner, Paul-Christian
Kroeker, Ilja
Oladyshkin, Sergey
Nowak, Wolfgang
JOURNAL OF COMPUTATIONAL PHYSICS, 2023, 488
[39] The Polynomial Euclidean Algorithm and the Linear Equation AX plus BY = gcd(A, B)
Effinger, Gove
Mullen, Gary L.
MATHEMATICAL INTELLIGENCER, 2017, 39 (01): : 22 - 25
[40] ON THE NUMBER OF TERMS OF A POWER OF A POLYNOMIAL
SCHINZEL, A
ACTA ARITHMETICA, 1987, 49 (01) : 55 - 70

← 1 2 3 4 5 →