Fast algorithms for discrete polynomial transforms

Consider the Vandermonde-like matrix , where the polynomials satisfy a three-term recurrence relation. If are the Chebyshev polynomials , then coincides with . This paper presents a new fast algorithm for the computation of the matrix-vector product in arithmetical operations. The algorithm divides into a fast transform which replaces with and a subsequent fast cosine transform. The first and central part of the algorithm is realized by a straightforward cascade summation based on properties of associated polynomials and by fast polynomial multiplications. Numerical tests demonstrate that our fast polynomial transform realizes with almost the same precision as the Clenshaw algorithm, but is much faster for .

     

An algorithm for evaluation of discrete logarithms in some nonprime finite fields

In this paper we propose an algorithm for evaluation of logarithms in the finite fields , where the number has a small primitive factor . The heuristic estimate of the complexity of the algorithm is equal to
, where grows to , and is limited by a polynomial in . The evaluation of logarithms is founded on a new congruence of the kind of D. Coppersmith, , which has a great deal of solutions-pairs of polynomials of small degrees.

     

Computing

Let denote the Von Mangoldt function and . We describe an elementary method for computing isolated values of . The complexity of the algorithm is time and space. A table of values of for up to is included, and some times of computation are given.

     

Perturbing polynomials with all their roots on the unit circle

Given a monic real polynomial with all its roots on the unit circle, we ask to what extent one can perturb its middle coefficient and still have a polynomial with all its roots on the unit circle. We show that the set of possible perturbations forms a closed interval of length at most , with achieved only for polynomials of the form with in . The problem can also be formulated in terms of perturbing the constant coefficient of a polynomial having all its roots in . If we restrict to integer coefficients, then the polynomials in question are products of cyclotomics. We show that in this case there are no perturbations of length that do not arise from a perturbation of length . We also investigate the connection between slightly perturbed products of cyclotomic polynomials and polynomials with small Mahler measure. We describe an algorithm for searching for polynomials with small Mahler measure by perturbing the middle coefficients of products of cyclotomic polynomials. We show that the complexity of this algorithm is , where is the degree, and we report on the polynomials found by this algorithm through degree 64.

     

A comparison of regularizations for an ill-posed problem

We consider numerical methods for a ``quasi-boundary value' regularization of the backward parabolic problem given by

where is positive self-adjoint and unbounded. The regularization, due to Clark and Oppenheimer, perturbs the final value by adding , where is a small parameter. We show how this leads very naturally to a reformulation of the problem as a second-kind Fredholm integral equation, which can be very easily approximated using methods previously developed by Ames and Epperson. Error estimates and examples are provided. We also compare the regularization used here with that from Ames and Epperson.

We consider numerical methods for a ``quasi-boundary value' regularization of the backward parabolic problem given by

where is positive self-adjoint and unbounded. The regularization, due to Clark and Oppenheimer, perturbs the final value by adding , where is a small parameter. We show how this leads very naturally to a reformulation of the problem as a second-kind Fredholm integral equation, which can be very easily approximated using methods previously developed by Ames and Epperson. Error estimates and examples are provided. We also compare the regularization used here with that from Ames and Epperson.

     

Bounds for eigenvalues and condition numbers in the -version of the finite element method

In this paper, we present a theory for bounding the minimum eigenvalues, maximum eigenvalues, and condition numbers of stiffness matrices arising from the -version of finite element analysis. Bounds are derived for the eigenvalues and the condition numbers, which are valid for stiffness matrices based on a set of general basis functions that can be used in the -version. For a set of hierarchical basis functions satisfying the usual local support condition that has been popularly used in the -version, explicit bounds are derived for the minimum eigenvalues, maximum eigenvalues, and condition numbers of stiffness matrices. We prove that the condition numbers of the stiffness matrices grow like , where is the number of dimensions. Our results disprove a conjecture of Olsen and Douglas in which the authors assert that ``regardless of the choice of basis, the condition numbers grow like or faster". Numerical results are also presented which verify that our theoretical bounds are correct.

     

Vector subdivision schemes and multiple wavelets

We consider solutions of a system of refinement equations written in the form

where the vector of functions is in and is a finitely supported sequence of matrices called the refinement mask. Associated with the mask is a linear operator defined on by . This paper is concerned with the convergence of the subdivision scheme associated with , i.e., the convergence of the sequence in the -norm.

Our main result characterizes the convergence of a subdivision scheme associated with the mask in terms of the joint spectral radius of two finite matrices derived from the mask. Along the way, properties of the joint spectral radius and its relation to the subdivision scheme are discussed. In particular, the -convergence of the subdivision scheme is characterized in terms of the spectral radius of the transition operator restricted to a certain invariant subspace. We analyze convergence of the subdivision scheme explicitly for several interesting classes of vector refinement equations.

Finally, the theory of vector subdivision schemes is used to characterize orthonormality of multiple refinable functions. This leads us to construct a class of continuous orthogonal double wavelets with symmetry.

     

Nonexistence conditions of a solution for the congruence

We obtain nonexistence conditions of a solution for of the congruence , where , and are integers, and is a prime power. We give nonexistence conditions of the form for , , , , , and of the form for , , , . Furthermore, we complete some tables concerned with Waring's problem in -adic fields that were computed by Hardy and Littlewood.

     

Random Fibonacci sequences and the number

For the familiar Fibonacci sequence (defined by , and for ), increases exponentially with at a rate given by the golden ratio . But for a simple modification with both additions and subtractions - the random Fibonacci sequences defined by , and for , , where each sign is independent and either or - with probability - it is not even obvious if should increase with . Our main result is that

with probability . Finding the number involves the theory of random matrix products, Stern-Brocot division of the real line, a fractal measure, a computer calculation, and a rounding error analysis to validate the computer calculation.

     

On the modular curves

Let denote an elliptic curve over and the modular curve classifying the elliptic curves over such that the representations of in the 7-torsion points of and of are symplectically isomorphic. In case is given by a Weierstraß equation such that the invariant is a square, we exhibit here nontrivial points of . From this we deduce an infinite family of curves for which has at least four nontrivial points.

     

On the convergence of certain Gauss-type quadrature formulas for unbounded intervals

We consider the convergence of Gauss-type quadrature formulas for the integral , where is a weight function on the half line . The -point Gauss-type quadrature formulas are constructed such that they are exact in the set of Laurent polynomials }, where is a sequence of integers satisfying and . It is proved that under certain Carleman-type conditions for the weight and when or goes to , then convergence holds for all functions for which is integrable on . Some numerical experiments compare the convergence of these quadrature formulas with the convergence of the classical Gauss quadrature formulas for the half line.

     

New Fibonacci and Lucas primes

Extending previous searches for prime Fibonacci and Lucas numbers, all probable prime Fibonacci numbers have been determined for and all probable prime Lucas numbers have been determined for . A rigorous proof of primality is given for and for numbers with , , , , , , , , the prime having 3020 digits. Primitive parts and of composite numbers and have also been tested for probable primality. Actual primality has been established for many of them, including 22 with more than 1000 digits. In a Supplement to the paper, factorizations of numbers and are given for as far as they have been completed, adding information to existing factor tables covering .

     

Computing automorphisms of abelian number fields

Let be an abelian number field of degree . Most algorithms for computing the lattice of subfields of require the computation of all the conjugates of . This is usually achieved by factoring the minimal polynomial of over . In practice, the existing algorithms for factoring polynomials over algebraic number fields can handle only problems of moderate size. In this paper we describe a fast probabilistic algorithm for computing the conjugates of , which is based on -adic techniques. Given and a rational prime which does not divide the discriminant of , the algorithm computes the Frobenius automorphism of in time polynomial in the size of and in the size of . By repeatedly applying the algorithm to randomly chosen primes it is possible to compute all the conjugates of .

     

Families of irreducible polynomials of Gaussian periods and matrices of cyclotomic numbers

Given an odd prime we show a way to construct large families of polynomials , , where is a set of primes of the form mod and is the irreducible polynomial of the Gaussian periods of degree in . Examples of these families when are worked in detail. We also show, given an integer and a prime mod , how to represent by matrices the Gaussian periods of degree in , and how to calculate in a simple way, with the help of a computer, irreducible polynomials for elements of .

     

The number of primes is finite

For a positive integer let and let . The number of primes of the form is finite, because if , then is divisible by . The heuristic argument is given by which there exists a prime such that for all large ; a computer check however shows that this prime has to be greater than . The conjecture that the numbers are squarefree is not true because .

     

Solving polynomials by radicals with roots of unity in minimum depth

Let be an algebraic number field. Let be a root of a polynomial which is solvable by radicals. Let be the splitting field of over . Let be a natural number divisible by the discriminant of the maximal abelian subextension of , as well as the exponent of , the Galois group of over . We show that an optimal nested radical with roots of unity for can be effectively constructed from the derived series of the solvable Galois group of over .

     

Upper bounds for the prime divisors of Wendt's determinant

Let be an even integer, . The resultant of the polynomials and is known as Wendt's determinant of order . We prove that among the prime divisors of only those which divide or can be larger than , where and is the th Lucas number, except when and . Using this estimate we derive criteria for the nonsolvability of Fermat's congruence.

     

Normal bases via general Gauss periods

Gauss periods have been used successfully as a tool for constructing normal bases in finite fields. Starting from a primitive th root of unity, one obtains under certain conditions a normal basis for over , where is a prime and for some integer . We generalize this construction by allowing arbitrary integers with , and find in many cases smaller values of than is possible with the previously known approach.

     

Locking-free finite elements for the Reissner-Mindlin plate

Two new families of Reissner-Mindlin triangular finite elements are analyzed. One family, generalizing an element proposed by Zienkiewicz and Lefebvre, approximates (for the transverse displacement by continuous piecewise polynomials of degree , the rotation by continuous piecewise polynomials of degree plus bubble functions of degree , and projects the shear stress into the space of discontinuous piecewise polynomials of degree . The second family is similar to the first, but uses degree rather than degree continuous piecewise polynomials to approximate the rotation. We prove that for , the errors in the derivatives of the transverse displacement are bounded by and the errors in the rotation and its derivatives are bounded by and , respectively, for the first family, and by and , respectively, for the second family (with independent of the mesh size and plate thickness . These estimates are of optimal order for the second family, and so it is locking-free. For the first family, while the estimates for the derivatives of the transverse displacement are of optimal order, there is a deterioration of order in the approximation of the rotation and its derivatives for small, demonstrating locking of order . Numerical experiments using the lowest order elements of each family are presented to show their performance and the sharpness of the estimates. Additional experiments show the negative effects of eliminating the projection of the shear stress.

     

The Postage Stamp Problem: An algorithm to determine the

Given an integral ``stamp" basis with and a positive integer , we define the -range as

. For given and , the extremal basis has the largest possible extremal -range

We give an algorithm to determine the -range. We prove some properties of the -range formula, and we conjecture its form for the extremal -range. We consider parameter bases , where the basis elements are given functions of . For we conjecture the extremal parameter bases for .