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 条

[21] Polynomial gcd computations over towers of algebraic extensions
Maza, MM
Rioboo, R
APPLIED ALGEBRA, ALGEBRAIC ALGORITHMS AND ERROR-CORRECTING CODES, 1995, 948 : 365 - 382
[22] Polynomial GCD and Factorization Via Approximate Grobner Bases
Lichtblau, Daniel
12TH INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND NUMERIC ALGORITHMS FOR SCIENTIFIC COMPUTING (SYNASC 2010), 2011, : 29 - 36
[23] SYSTOLIC VLSI ARRAYS FOR POLYNOMIAL GCD COMPUTATION.
Brent, Richard P.
Kung, H.T.
IEEE Transactions on Computers, 1984, C-33 (08) : 731 - 736
[24] Sparse polynomial prediction
Hugo Maruri-Aguilar
Henry Wynn
Statistical Papers, 2023, 64 : 1233 - 1249
[25] Sparse polynomial prediction
Maruri-Aguilar, Hugo
Wynn, Henry
STATISTICAL PAPERS, 2023, 64 (04) : 1233 - 1249
[26] New Sparse Multivariate Polynomial Factorization Algorithms over Integers
Huang, Qiao-Long
Gao, Xiao-Shan
PROCEEDINGS OF THE INTERNATIONAL SYMPOSIUM ON SYMBOLIC & ALGEBRAIC COMPUTATION, ISSAC 2023, 2023, : 315 - 324
[27] On terms in a dynamical divisibility sequence having a fixed GCD with their indices
Jha, Abhishek
NEW YORK JOURNAL OF MATHEMATICS, 2022, 28 : 1152 - 1171
[28] Computation of GCD of Sparse Multivariate Polynomials by Extended Hensel Construction
Sanuki, Masaru
Inaba, Daiju
Sasaki, Tateaki
2015 17TH INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND NUMERIC ALGORITHMS FOR SCIENTIFIC COMPUTING (SYNASC), 2016, : 34 - 41
[29] A new approach to parallel computation of polynomial GCD and to related parallel computations over fields and integer rings
Pan, VY
PROCEEDINGS OF THE SEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 1996, : 518 - 527
[30] AN EXTENDED POLYNOMIAL GCD ALGORITHM USING HANKEL-MATRICES
SENDRA, JR
LLOVET, J
JOURNAL OF SYMBOLIC COMPUTATION, 1992, 13 (01) : 25 - 39

← 1 2 3 4 5 →