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.

     

Multigrid and multilevel methods for nonconforming elements

In this paper we study theoretical properties of multigrid algorithms and multilevel preconditioners for discretizations of second-order elliptic problems using nonconforming rotated finite elements in two space dimensions. In particular, for the case of square partitions and the Laplacian we derive properties of the associated intergrid transfer operators which allow us to prove convergence of the -cycle with any number of smoothing steps and close-to-optimal condition number estimates for -cycle preconditioners. This is in contrast to most of the other nonconforming finite element discretizations where only results for -cycles with a sufficiently large number of smoothing steps and variable -cycle multigrid preconditioners are available. Some numerical tests, including also a comparison with a preconditioner obtained by switching from the nonconforming rotated discretization to a discretization by conforming bilinear elements on the same partition, illustrate the theory.

     

Pointwise error estimates and asymptotic error expansion inequalities for the finite element method on irregular grids: Part I. Global estimates

This part contains new pointwise error estimates for the finite element method for second order elliptic boundary value problems on smooth bounded domains in . In a sense to be discussed below these sharpen known quasi-optimal and estimates for the error on irregular quasi-uniform meshes in that they indicate a more local dependence of the error at a point on the derivatives of the solution . We note that in general the higher order finite element spaces exhibit more local behavior than lower order spaces. As a consequence of these estimates new types of error expansions will be derived which are in the form of inequalities. These expansion inequalities are valid for large classes of finite elements defined on irregular grids in and have applications to superconvergence and extrapolation and a posteriori estimates. Part II of this series will contain local estimates applicable to non-smooth problems.

     

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.

     

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.

     

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 .

     

On -amicable pairs

Let denote Euler's totient function, i.e., the number of positive integers and prime to . We study pairs of positive integers with such that for some integer . We call these numbers -amicable pairs with multiplier , analogously to Carmichael's multiply amicable pairs for the -function (which sums all the divisors of ).

We have computed all the -amicable pairs with larger member and found pairs for which the greatest common divisor is squarefree. With any such pair infinitely many other -amicable pairs can be associated. Among these pairs there are so-called primitive -amicable pairs. We present a table of the primitive -amicable pairs for which the larger member does not exceed . Next, -amicable pairs with a given prime structure are studied. It is proved that a relatively prime -amicable pair has at least twelve distinct prime factors and that, with the exception of the pair , if one member of a -amicable pair has two distinct prime factors, then the other has at least four distinct prime factors. Finally, analogies with construction methods for the classical amicable numbers are shown; application of these methods yields another 79 primitive -amicable pairs with larger member , the largest pair consisting of two 46-digit numbers.

     

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.

     

An algorithm for constructing a basis for -spline modules over polynomial rings

Let be a polyhedral complex embedded in the euclidean space and , , denote the set of all -splines on . Then is an -module where is the ring of polynomials in several variables. In this paper we state and prove the existence of an algorithm to write down a free basis for the above -module in terms of obvious linear forms defining common faces of members of . This is done for the case when consists of a finite number of parallelopipeds properly joined amongst themselves along the above linear forms.

     

On the Diophantine equation

If and are positive integers with and , then the equation of the title possesses at most one solution in positive integers and , with the possible exceptions of satisfying , and . The proof of this result relies on a variety of diophantine approximation techniques including those of rational approximation to hypergeometric functions, the theory of linear forms in logarithms and recent computational methods related to lattice-basis reduction. Additionally, we compare and contrast a number of these last mentioned techniques.

     

Minus class groups of the fields of the -th roots of unity

We show that for any prime number the minus class group of the field of the -th roots of unity admits a finite free resolution of length 1 as a module over the ring . Here denotes complex conjugation in . Moreover, for the primes we show that the minus class group is cyclic as a module over this ring. For these primes we also determine the structure of the minus class group.

     

Finding finite -sequences faster

A -sequence is a sequence of positive integers such that the sums , , are different. When is a power of a prime and is a primitive element in then there are -sequences of size with , which were discovered by R. C. Bose and S. Chowla.

In Theorem 2.1 I will give a faster alternative to the definition. In Theorem 2.2 I will prove that multiplying a sequence by integers relatively prime to the modulus is equivalent to varying . Theorem 3.1 is my main result. It contains a fast method to find primitive quadratic polynomials over when is an odd prime. For fields of characteristic 2 there is a similar, but different, criterion, which I will consider in ``Primitive quadratics reflected in -sequences', to appear in Portugaliae Mathematica (1999).

     

On divisibility of the class number

In this paper, criteria of divisibility of the class number of the real cyclotomic field of a prime conductor and of a prime degree by primes the order modulo of which is , are given. A corollary of these criteria is the possibility to make a computational proof that a given does not divide for any (conductor) such that both are primes. Note that on the basis of Schinzel's hypothesis there are infinitely many such primes .

     

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.

     

Multilevel Additive Schwarz Method for the Version of the Galerkin Boundary Element Method

We study a multilevel additive Schwarz method for the - version of the Galerkin boundary element method with geometrically graded meshes. Both hypersingular and weakly singular integral equations of the first kind are considered. As it is well known the - version with geometric meshes converges exponentially fast in the energy norm. However, the condition number of the Galerkin matrix in this case blows up exponentially in the number of unknowns . We prove that the condition number of the multilevel additive Schwarz operator behaves like . As a direct consequence of this we also give the results for the -level preconditioner and also for the - version with quasi-uniform meshes. Numerical results supporting our theory are presented.

     

Subquadratic-time factoring of polynomials over finite fields

New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree over a finite field of constant cardinality in time . Previous algorithms required time . The new algorithms rely on fast matrix multiplication techniques. More generally, to factor a polynomial of degree over the finite field with elements, the algorithms use arithmetic operations in .

The new ``baby step/giant step' techniques used in our algorithms also yield new fast practical algorithms at super-quadratic asymptotic running time, and subquadratic-time methods for manipulating normal bases of finite fields.

     

Factoring elementary groups of prime cube order into subsets

Let be a prime and let be the -fold direct product of the cyclic group of order . Rédei conjectured if is the direct product of subsets and , each of which contains the identity element of , then either or does not generate all of . The paper verifies Rédei's conjecture for .

     

Asymptotic upper bounds for the coefficients in the Chebyshev series expansion for a general order integral of a function

The usual way to determine the asymptotic behavior of the Chebyshev coefficients for a function is to apply the method of steepest descent to the integral representation of the coefficients. However, the procedure is usually laborious. We prove an asymptotic upper bound on the Chebyshev coefficients for the integral of a function. The tightness of this upper bound is then analyzed for the case , the first integral of a function. It is shown that for geometrically converging Chebyshev series the theorem gives the tightest upper bound possible as . For functions that are singular at the endpoints of the Chebyshev interval, , the theorem is weakened. Two examples are given. In the first example, we apply the method of steepest descent to directly determine (laboriously!) the asymptotic Chebyshev coefficients for a function whose asymptotics have not been given previously in the literature: a Gaussian with a maximum at an endpoint of the expansion interval. We then easily obtain the asymptotic behavior of its first integral, the error function, through the application of the theorem. The second example shows the theorem is weakened for functions that are regular except at . We conjecture that it is only for this class of functions that the theorem gives a poor upper bound.

     

A space efficient algorithm for group structure computation

We present a new algorithm for computing the structure of a finite abelian group, which has to store only a fixed, small number of group elements, independent of the group order. We estimate the computational complexity by counting the group operations such as multiplications and equality checks. Under some plausible assumptions, we prove that the expected run time is (with denoting the group order), and we explicitly determine the -constants. We implemented our algorithm for ideal class groups of imaginary quadratic orders and present experimental results.