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.

Given a sparse polynomial represented by a black box, we aim to find its factors in the sparse representation. The authors have previously developed an efficient algorithm for the monic and square-free case. In this work, we contribute a new algorithm that also handles the non-monic, non-square-free and non-primitive cases. We give a worst case complexity analysis with failure probabilities. The required number of probes to the black box in our algorithm is much less than the previously best known algorithm by Rubinfeld and Zippel in 1994. We have also implemented our new algorithm in Maple with all major subroutines in C. Our benchmarks show that our algorithm is much faster than the current best determinant and factorization algorithms in Maple and Magma.

We present a new algorithm for performing linear Hensel lifting on bivariate polynomials over the finite field Zp for some prime p. Our algorithm lifts n monic, univariate polynomials to recover the factors of a polynomial A(x,y) in Zp[x,y] which is monic in x, and bounded by degrees dx = deg(A,x) and dy = deg(A,y). Our algorithm improves upon Bernardin's algorithm in [1] and reduces the number of arithmetic operations in Zp from O(n dx^2 dy^2) to O(dx^2 dy + dx dy^2) for p >= dx. Experimental results in C verify that our algorithm compares favorably with Bernardin's for large degree polynomials. Moreover, we've implemented a Quadratic Hensel lifting algorithm in Magma to show that our cubic Linear Hensel lifting algorithm outperforms Magma's Quadratic Hensel lifting for a wide range of input sizes.

Summary Two essential problems in computer algebra, namely polynomial factorization and polynomial greatest common divisor computation, can be efficiently solved thanks to multiple polynomial evaluations in two variables using modular arithmetic. In this article, we focus on the efficient computation of such polynomial evaluations on one single CPU core. We first show how to leverage SIMD (single instruction, multiple data) computing for modular arithmetic on AVX2 and AVX‐512 units, using both intrinsics and OpenMP compiler directives. Then we manage to increase the operational intensity and to exploit instruction‐level parallelism in order to increase the compute efficiency of these polynomial evaluations. All this results in the end to performance gains up to about 5x on AVX2 and 10x on AVX‐512.

Hensel lifting is a key tool that is used to factor polynomials and compute polynomial GCDs in Z[x], Z[x1,...,xn] and Fq[x1,...,xn]. There are two versions of Hensel lifting: Linear Hensel Lifting (LHL) and Quadratic Hensel Lifting (QHL). For polynomials in Z[x], if classical quadratic algorithms for multiplication and division are used, LHL and QHL both have a quartic complexity. If asymptotically fast arithmetic is used, up to logarithmic factors, LHL is cubic and QHL is quadratic. In this work we present cubic algorithms for LHL for Z[x] and Fp[x,y]. We present details of C implementations of our cubic algorithms for Z[x] and Fp[x,y]. We compare both with Magma implementations of QHL using fast arithmetic. For both cases, we find that our our cubic LHL outperforms Magma's fast QHL for a very wide range of input sizes.

A new efficient algorithm for computing a parametric greatest common divisor (GCD) of parametric multivariate polynomials over k[u][x] is presented. The algorithm is based on a well-known simple insight that the GCD of two multivariate polynomials (non-parametric as well as parametric) can be extracted using the generator of the quotient ideal of a polynomial with respect to the second polynomial. And, further, this generator can be obtained by computing a minimal Gröbner basis of the quotient ideal. The main attraction of this idea is that it generalizes to the parametric case for which a comprehensive Gröbner basis is constructed for the parametric quotient ideal. It is proved that in a minimal comprehensive Gröbner system of a parametric quotient ideal, each branch of specializations corresponds to a principal parametric ideal with a single generator. Using this generator, the parametric GCD of that branch is obtained by division. This algorithm does not need to consider whether parametric polynomials are primitive w.r.t. the main variable. This is in sharp contrast to two algorithms recently proposed by Nagasaka (ISSAC, 2017). The resulting algorithm is not only conceptually simple to understand but is considerably efficient. The proposed algorithm and both of Nagasaka's algorithms have been implemented in Singular (available at http://www.mmrc.iss.ac.cn/~dwang/software.html), and their performance is compared on a number of examples. For more than two polynomials, this process can be repeated by considering pairs of polynomials; the efficiency in that case becomes even more evident.

We present a parallel GCD algorithm for sparse multivariate polynomials with integer coefficients. The algorithm combines a Kronecker substitution with a Ben-Or/Tiwari sparse interpolation modulo a smooth prime to determine the support of the GCD. We have implemented our algorithm in Cilk C. We compare it with Maple and Magma's implementations of Zippel's GCD algorithm.

We present an efficient algorithm for factoring a multivariate polynomial f ∈ L[x1,...,xv] where L is an algebraic function field with k ≥0 parameters t1,...,tk and r ≥0 field extensions.

We present a high performance algorithm for multiplying sparse distributed polynomials using a multicore processor. Each core uses a heap of pointers to multiply parts of the polynomials using its local cache. Intermediate results are written to buffers in shared cache and the cores take turns combining them to form the result. A cooperative approach is used to balance the load and improve scalability, and the extra cache from each core produces a superlinear speedup in practice. We present benchmarks comparing our parallel routine to a sequential version and to the routines of other computer algebra systems.

We present a first sparse modular algorithm for computing a greatest common divisor of two polynomials f1, f2 ε L[x] where L is an algebraic function field in k ≥ 0 parameters with r ≥ 0 field extensions. Our algorithm extends the dense algorithm of Monagan and van Hoeij from 2004 to support multiple field extensions and to be efficient when the gcd is sparse. Our algorithm is an output sensitive Las Vegas algorithm.

Let F be a field, f, g E F[z] with rn = deg f > deg g > 0. Our problem is to find a rational f~mction n/d E F(x) where n / d = g mod f: gcd(f, d) = gcd(n, d) = 1 and deg n + deg d < m. If degree bounds N > deg 12 and D > deg d satisfying N + D < m are known, then bhe problem is solved by the Extended Euclidean Algorithm in F[z]. If degree bounds are not known it is still possible to find n/d with high probability. One way is to use rnaximal q~~otient rational f~mction reconstruction. We have implemented the algorithm for F[x] = Zp[x], with p a prime. To speed up the algorithm, our implementation uses Karatsuba's algorithm for multiplication in Z,[z] and a Fast Extended Euclidean Algorithm. As an application, we have modified Brown's modular GCD algorithm to use the maximal quotient algorithm. The modification reduces the number of evaluation points needed by the algorithm.

We present two algorithms for simplifying rational expressions modulo an ideal of the polynomial ring k[x1, . . . , xn]. The first method generates the set of equivalent expressions as amodule over k[x1, . . . , xn] and computes a reduced Gröbner basis. From this we obtain a canonical form for the expression up to our choice of monomial order for the ideal. The second method constructs equivalent expressions by solving systems of linear equations over k, and conducts a global search for an expression with minimal total degree. Depending on the ideal, the algorithms may or may not cancel all common divisors. We also provide some timings comparing the efficiency of the algorithms in Maple.

Let G = (4y2+2z)x2 + (10y2+6z) be the greatest common divisor (Gcd) of two polynomials A, B ∈ ℤ[x,y,z]. Because G is not monic in the main variable x, the sparse modular Gcd algorithm of Richard Zippel cannot be applied directly as one is unable to scale univariate images of G in x consistently. We call this the normalization problem.We present two new sparse modular Gcd algorithms which solve this problem without requiring any factorizations. The first, a modification of Zippel's algorithm, treats the scaling factors as unknowns to be solved for. This leads to a structured coupled linear system for which an efficient solution is still possible. The second algorithm reconstructs the monic Gcd x2 + (5y2+3z)/(2y2+z) from monic univariate images using a sparse, variable at a time, rational function interpolation algorithm.

Let A and B be two polynomials in ℤ [x,y] and let R = resx(A,B) denote the resultant of A and B taken wrt x. In this paper we modify Collins' modular algorithm for computing R to make it output sensitive. The advantage of our algorithm is that it will be faster when the bounds needed by Collins' algorithm for the coefficients of R and for the degree of R are inaccurate. Our second contribution is an output sensitive modular algorithm for computing the monic resultant in ℚ[y]. The advantage of this algorithm is that it is faster still when the resultant has a large integer content. Both of our algorithms are necessarily probabilistic.The paper includes a number of resultant problems that motivate the need to consider such algorithms. We have implemented our algorithms in Maple. We have also implemented Collins' algorithm and the subresultant algorithm in Maple for comparison. The timings we obtain demonstrate that a good speedup is obtained.

Let L be an algebraic function field in k ≥ 0 parameters t;1;, ..., t;k;. Let f;1;, f;2; be non-zero polynomials in L[x]. We give two algorithms for computing their gcd. The first, a modular GCD algorithm, is an extension of the modular GCD algorithm of Brown for Z[x;1;,...,x;n;] and Encarnacion for Q(α)[x] to function fields. It is uses rational number and rational function reconstruction and trial division. The second, a fraction-free algorithm, is a modification of the Moreno Maza and Rioboo algorithm for computing gcds over triangular sets. The modification reduces coefficient growth in L to be linear. We show how to extend the modular GCD algorithm to work when the minimal polynomial for L is not irreducible. We give an empirical comparison of the two algorithms using implementations in Maple.

Let n/d ∈ Q, m be a positive integer and let u = n/d mod m. Thus $u$ is the image of a rational number modulo m. The rational reconstruction problem is; given u and m find n/d. A solution was first given by Wang in 1981. Wang's algorithm outputs n/d when m > 2 M2 where M = max(|n|,d). Because of the wide application of this algorithm in computer algebra, several authors have investigated its practical efficiency and asymptotic time complexity.In this paper we present a new solution which is almost optimal in the following sense; with controllable high probability, our algorithm will output n/d when m is a modest number of bits longer than 2 |n| d. This means that in a modular algorithm where m is a product of primes, the modular algorithm will need one or two primes more than the minimum necessary to reconstruct n/d; thus if |n| ⇐ d or d ⇐ |n| the new algorithm saves up to half the number of primes. Further, our algorithm will fail with high probability when m < 2 |n| d.

We consider the problem of computing the monic gcd of two polynomials over a number field L = ℚ(α1,…,αn). Encarnacion, Langemyr and McCallum have already shown how Brown's modular GCD algorithm for polynomials over ℚ can be modified to work for ℚ(α).Our first contribution is an extension of Encarnacion's modular GCD algorithm to the case n > 1 without converting to a single field extension. Our second contribution is a proof that it is not necessary to test if p divides the discriminant. This simplifies the algorithm; it is correct without this test.Our third contribution is the design of a data structure for representing multivariate polynomials over number fields with multiple field extensions. We have a complete implementation of the modular GCD algorithm using it. We provide details of some practical improvements.

In this paper we present algorithms for simplifying ratios of trigonometric polynomials and algorithms for dividing, factoring and computing greatest common divisors of trigonometric polynomials, that is, polynomials in sin(x) and cos(x). 1.

We study the design and implementation of the dense modular GCD algorithm of Brown applied to bivariate polynomial GCDs over the integers and number fields. We present an improved design of Brown's algorithm and compare it asymptotically with Brown's original algorithm, with GCD-HEU, the heuristic GCD algorithm, and with the EEZGCD algorithm. We also make an empirical comparison based on Maple implementations of the algorithms. Our findings show that a careful implementation of our improved version of Brown's algorithm is much better than the other algorithms in theory and in practice.

In this paper we st,udy the generic setting of the modular GCD algorithm.We develop the algorithm for multivariate polynomials over Euclidean domains which have a spc:&l kind of remainder function.Details for the parameterixation and generic Maple code are given.Applying this grncric algorithm to a GCD problem in Z/(~) [t][z] where 1~ is small yields an improved asymptotic performance over t.he usual approach, and a very practical algorithm for polynomials over small finite fields.

We describe the design of a package for creating efficient numeric code. The package provides the user with tools for creating and manipulating programs, in this case Maple programs, converting the programs into C and Fortran, and compiling and executing the programs from inside Maple. The tools for manipulating programs include automatic differentiation, code optimization, and the complexity analysis of a program. An application to an optimization problem from computer vision which requires a gradient computation is given. 1

In 1980 Schwartz gave a fast probabilistic method which tests if a matrix of polynomials over Z is singular or not. The method is based on the idea of signature functions which are mappings of mathematical expressions into finite rings. In Schwartz's paper, they were polynomials over Z into GF(p). Because computation in GF(p) is very fast compared with computing with polynomials, Schwartz's method yields an enormous speedup both in theory and in practice. Therefore it is desirable to extend the class of expressions for which we can find effective signature functions. In the mid 80's Gonnet extended the class of expressions, for which signature functions could be found, to include a restricted class of elementary functions and integer roots. In this paper we present and compare methods for constructing signature functions for expressions containing algebraic numbers. Some experimental results are given.

Many scientific applications require computation of the derivatives of a function f : l?" -Etm as well as the function values off itself.AH computer algebra systems can dtierentiate functions represented by formulae.But not all functions can be described by formulae.And formulae are not always the most effective means for representing functions and derivatives.In this paper we describe the algorithms used by the Maple [2] routine GRADIEHT that accepts as input a Maple procedure for the computation off and outputs a new Maple procedure that computes the gradient of f.The design of the GRADIElfT routine is such that it is also trivial to generate Maple procedures for the computation Jacobians and Hessians.