Search

We present a new algorithm for performing linear Hensel lifting of bivariate polynomials over a finite field Fpwith pelements. It lifts nmonic, univariate polynomials to recover the factors of a polynomial A(x, y) ∈ Fp[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 cost from [EQUATION] to [EQUATION]. Experimental results show that our algorithm works efficiently for large degree polynomials.

Suppose that we seek to factor a multivariate polynomial a ε R = Z[x1, ..., xn] and a = fg with f, g in R. The multivariate Hensel lifting algorithm (MHL) developed by Wang [1] uses a prime number p and an ideal I = 〈x2 − α2, ..., xn − αn〉 of Zp[x1, ..., xn] where α2, α3, ..., αn ε Zp is an evaluation point chosen by the algorithm.

I am not a surfer. But when my 12-year-old niece was visiting from Connecticut a couple years ago she wanted to try her hand at surfing. I arranged a lesson […]

The principal data structure Maple uses to represent polynomials and general mathematical expressions involving functions like sin x, e2x, y'(x),(n/k) etc., is known to the Maple developers as the sum-of-products data structure. Gaston Gonnet, as the primary author of the Maple kernel, designed and implemented this data structure in the early 1980s. As part of the process of simplifying a mathematical formula, he represented every Maple object and every sub-object uniquely in memory. This makes testing for equality of expressions very fast. In this article, on occasion of Gonnet's retirement, we present details of his design, its pros and cons, and changes we and others have made to it over the years. One of the cons of the sum-of-products data structure is it is not as efficient at multiplying multivariate polynomials as other special purpose computer algebra systems. We describe a new data structure called POLY that we added to Maple 17 (released in 2013) to improve performance for polynomials in Maple, and recent work done for Maple 18 (released in 2014).

In [3] the following polynomial evaluation problem arises. Let A be a sparse polynomial with s terms in Zp[x0,x1,...,xn]. Suppose we seek evaluations of A into t bivariate images in Zp[x0,x1], for some t ≪ s. We do not know a priori the exact number of images t needed. This will be determined by using a trial value T for t, and increasing T as required.

We employ two techniques to dramatically improve Maple's performance on the Fermat benchmarks for simplifying rational expressions. First, we factor expanded polynomials to ensure that gcds are identified and cancelled automatically. Second, we replace all expanded polynomials by new variables and normalize the result. To undo the substitutions, we use a C routine for sparse multivariate division by a set of polynomials. The resulting times for the first Fermat benchmark are a factor of 17x faster than Fermat and 39x faster than Magma.

We are interested in specific structured matrices obtained from [5] which arise from combinatorial problems.

We demonstrate how a new data structure for sparse distributed polynomials in the Maple kernel significantly accelerates a large subset of Maple library routines. The POLY data structure and its associated kernel operations (degree, coeff, subs, has, diff, eval, ...) are programmed for high scalability, allowing polynomials to have hundreds of millions of terms, and very low overhead, increasing parallel speedup in existing routines and improving the performance of high level Maple library routines.

In this article the author explains how computer programming skills can boost the efficiency and creativity of scientists and engineers. He presents the story of his friend who works in oceanography and mechanical engineering but spends 95% of his time in front of the computer writing programs to collate and analyze data collected in the field. He also cites several reasons to learn computer programming including discovering more creative solutions, working 10 times faster, and communicating effectively with programmers.

We demonstrate new routines for sparse multivariate polynomial multiplication and division over the integers that we have integrated into Maple 14 through the expand and divide commands. These routines are currently the fastest available, and the multiplication routine is parallelized with superlinear speedup. The performance of Maple is significantly improved. We describe our polynomial data structure and compare it with Maple's. Then we present benchmarks comparing Maple 14 with Maple 13, Magma, Mathematica, Singular, Pari, and Trip.

This paper describes how computer algebra systems can be used to help students understand mathematical algorithms. Since one can write programs in these systems, one way to help the students is to show them complete programs and try to show them what the programs do. However, programs are like black boxes; you see what goes in and what comes out. To understand the program you need to show the steps that it makes because most students need to see a worked example in detail in order to see what an algorithm is doing before they understand how it works. Another problem with programs is that programs force you to be explicit about details; you must formulate the termination conditions, estimate degree bounds, specify domains of variables, etc. These details often get in the way of illustrating the basic algorithm.

We show that if the first case of Fermat's Last Theorem is false for prime exponent $ p$ divides $ {q^p} - q$ . As a corollary we state the theorem of the title.

We have developed a library for sparse polynomial arithmetic to supplement Maple's internal routines. Along the way we identified three common sources of inefficiency in existing implementations.