𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Three new algorithms for multivariate polynomial GCD

✍ Scribed by Tateaki Sasaki; Masayuki Suzuki

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
885 KB
Volume
13
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

✦ Synopsis

Three new algorithms for multivariate polynomial GCD (greatest common divisor) are given. The first is to calculate a GrSbner basis with a certain term ordering. The second is to calculate the subresultant by treating the coefficients w.r.t, the main variable as truncated power series. The third is to calculate a PRS (polynomial remainder sequence) by treating the coefficients as truncated power series. The first algorithm is not important praetioaUy, but the second and third ones are efficient and seem to be useful practically. The third algorithm has been implemented naively and compared with the trial-division PRS algorithm and the EZGCD algorithm. Although it is too early to derive a definite conclusion, the PRS method with power series coefficients is very efficient for calculating low degree GCD of high degree non-sparse polynomials.

πŸ“œ SIMILAR VOLUMES

Polynomial time algorithms for three-lab
Polynomial time algorithms for three-label point labeling
✍ Rob Duncan; Jianbo Qian; Antoine Vigneron; Binhai Zhu πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 155 KB

In this paper, we present an O(n 2 log n) time solution for the following multi-label map labeling problem: given a set S of n distinct sites in the plane, place at each site a triple of uniform squares of maximum possible size such that all the squares are axis-parallel and a site is on the boundar

Modular Algorithm for Sparse Multivariat
Modular Algorithm for Sparse Multivariate Polynomial Interpolationand its Parallel Implementation
✍ HIROKAZU MURAO; TETSURO FUJISE πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 885 KB

A new algorithm for sparse multivariate polynomial interpolation is presented. It is a multi-modular extension of the Ben-Or and Tiwari algorithm, and is designed to be a practical method to construct symbolic formulas from numeric data produced by vector or massively-parallel processors. The main i

New fast algorithms for polynomial inter
New fast algorithms for polynomial interpolation and evaluation on the Chebyshev node set
✍ V.Y. Pan πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 250 KB

For a polynomial p(x) of a degree n, we study its interpolation and evaluation on a set of Chebyshev nodes, x k = cos((2k + 1)~r/(2n + 2)), k = 0,1,... ,n. This is easily reduced to applying discrete Fourier transforms (DFTs) to the auxiliary polynomial q(w) = w'~p(x), where 2x = ~w + (aw) -1, a ---