Finite element superconvergence on Shishkin mesh for 2-D convection-diffusion problems

In this work, the bilinear finite element method on a Shishkin mesh for convection-diffusion problems is analyzed in the two-dimensional setting. A superconvergence rate in a discrete -weighted energy norm is established under certain regularity assumptions. This convergence rate is uniformly valid with respect to the singular perturbation parameter . Numerical tests indicate that the rate is sharp for the boundary layer terms. As a by-product, an -uniform convergence of the same order is obtained for the -norm. Furthermore, under the same regularity assumption, an -uniform convergence of order in the norm is proved for some mesh points in the boundary layer region.

     

Littlewood polynomials with high order zeros

Let be the minimal length of a polynomial with coefficients divisible by . Byrnes noted that for each , and asked whether in fact . Boyd showed that for all , but . He further showed that , and that is one of the 5 numbers , or . Here we prove that . Similarly, let be the maximal power of dividing some polynomial of degree with coefficients. Boyd was able to find for . In this paper we determine for .

     

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 .

     

A solution to certain polynomial equations with applications to nonlinear fitting

We present a combinatorial method for solving a certain system of polynomial equations of Vandermonde type in variables by reducing it to the problem of solving two special linear systems of size and rooting a single univariate polynomial of degree . Over , all solutions can be found with fixed precision using, up to polylogarithmic factors, bitwise operations in the worst case. Furthermore, if the data is well conditioned, then this can be reduced to bit operations, up to polylogarithmic factors. As an application, we show how this can be used to fit data to a complex exponential sum with terms in the same, nearly optimal, time.

     

On quadratic fields with large 3-rank

Davenport and Heilbronn defined a bijection between classes of binary cubic forms and classes of cubic fields, which has been used to tabulate the latter. We give a simpler proof of their theorem then analyze and improve the table-building algorithm. It computes the multiplicities of the general cubic discriminants (real or imaginary) up to in time and space , or more generally in time and space for a freely chosen positive . A variant computes the -ranks of all quadratic fields of discriminant up to with the same time complexity, but using only units of storage. As an application we obtain the first real quadratic fields with , and prove that is the smallest imaginary quadratic field with -rank equal to .

     

Linear algebra algorithms for divisors on an algebraic curve

We use an embedding of the symmetric th power of any algebraic curve of genus into a Grassmannian space to give algorithms for working with divisors on , using only linear algebra in vector spaces of dimension , and matrices of size . When the base field is finite, or if has a rational point over , these give algorithms for working on the Jacobian of that require field operations, arising from the Gaussian elimination. Our point of view is strongly geometric, and our representation of points on the Jacobian is fairly simple to deal with; in particular, none of our algorithms involves arithmetic with polynomials. We note that our algorithms have the same asymptotic complexity for general curves as the more algebraic algorithms in Florian Hess' 1999 Ph.D. thesis, which works with function fields as extensions of . However, for special classes of curves, Hess' algorithms are asymptotically more efficient than ours, generalizing other known efficient algorithms for special classes of curves, such as hyperelliptic curves (Cantor 1987), superelliptic curves (Galbraith, Paulus, and Smart 2002), and curves (Harasawa and Suzuki 2000); in all those cases, one can attain a complexity of .

     

Optimal logarithmic energy points on the unit sphere

We study minimum energy point charges on the unit sphere in , , that interact according to the logarithmic potential , where is the Euclidean distance between points. Such optimal -point configurations are uniformly distributed as . We quantify this result by estimating the spherical cap discrepancy of optimal energy configurations. The estimate is of order . Essential is an improvement of the lower bound of the optimal logarithmic energy which yields the second term in the asymptotical expansion of the optimal energy. Previously, this was known for the unit sphere in only. Furthermore, we present an upper bound for the error of integration for an equally-weighted numerical integration rule with the nodes forming an optimal logarithmic energy configuration. For polynomials of degree at most this bound is as . For continuous functions of satisfying a Lipschitz condition with constant the bound is as .

     

Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields

We examine the problem of factoring the th cyclotomic polynomial, over , and distinct primes. Given the traces of the roots of we construct the coefficients of in time . We demonstrate a deterministic algorithm for factoring in time when has precisely two irreducible factors. Finally, we present a deterministic algorithm for computing the sum of the irreducible factors of in time .

     

Analysis of a bilinear finite element for shallow shells. II: Consistency error

We consider a bilinear reduced-strain finite element of the MITC family for a shallow Reissner-Naghdi type shell. We estimate the consistency error of the element in both membrane- and bending-dominated states of deformation. We prove that in the membrane-dominated case, under severe assumptions on the domain, the finite element mesh and the regularity of the solution, an error bound can be obtained if the contribution of transverse shear is neglected. Here is the thickness of the shell, the mesh spacing, and a smoothness parameter. In the bending-dominated case, the uniformly optimal bound is achievable but requires that membrane and transverse shear strains are of order as . In this case we also show that under sufficient regularity assumptions the asymptotic consistency error has the bound .

     

Finite SAGBI bases for polynomial invariants of conjugates of alternating groups

It is well-known, that the ring of polynomial invariants of the alternating group has no finite SAGBI basis with respect to the lexicographical order for any number of variables . This note proves the existence of a nonsingular matrix such that the ring of polynomial invariants , where denotes the conjugate of with respect to , has a finite SAGBI basis for any .     

Explicit primality criteria for

Deterministic polynomial time primality criteria for have been known since the work of Lucas in 1876-1878. Little is known, however, about the existence of deterministic polynomial time primality tests for numbers of the more general form , where is any fixed prime. When (p-1)/2$"> we show that it is always possible to produce a Lucas-like deterministic test for the primality of which requires that only modular multiplications be performed modulo , as long as we can find a prime of the form such that is not divisible by . We also show that for all with such a can be found very readily, and that the most difficult case in which to find a appears, somewhat surprisingly, to be that for . Some explanation is provided as to why this case is so difficult.

     

Analysis of PSLQ, an integer relation finding algorithm

Let be either the real, complex, or quaternion number system and let be the corresponding integers. Let be a vector in . The vector has an integer relation if there exists a vector , , such that . In this paper we define the parameterized integer relation construction algorithm PSLQ, where the parameter can be freely chosen in a certain interval. Beginning with an arbitrary vector , iterations of PSLQ will produce lower bounds on the norm of any possible relation for . Thus PSLQ can be used to prove that there are no relations for of norm less than a given size. Let be the smallest norm of any relation for . For the real and complex case and each fixed parameter in a certain interval, we prove that PSLQ constructs a relation in less than iterations.

     

Asymptotically fast group operations on Jacobians of general curves

Let be a curve of genus over a field . We describe probabilistic algorithms for addition and inversion of the classes of rational divisors in the Jacobian of . After a precomputation, which is done only once for the curve , the algorithms use only linear algebra in vector spaces of dimension at most , and so take field operations in , using Gaussian elimination. Using fast algorithms for the linear algebra, one can improve this time to . This represents a significant improvement over the previous record of field operations (also after a precomputation) for general curves of genus .

     

Strong tractability of multivariate integration using quasi-Monte Carlo algorithms

We study quasi-Monte Carlo algorithms based on low discrepancy sequences for multivariate integration. We consider the problem of how the minimal number of function evaluations needed to reduce the worst-case error from its initial error by a factor of depends on and the dimension . Strong tractability means that it does not depend on and is bounded by a polynomial in . The least possible value of the power of is called the -exponent of strong tractability. Sloan and Wozniakowski established a necessary and sufficient condition of strong tractability in weighted Sobolev spaces, and showed that the -exponent of strong tractability is between 1 and 2. However, their proof is not constructive.

In this paper we prove in a constructive way that multivariate integration in some weighted Sobolev spaces is strongly tractable with -exponent equal to 1, which is the best possible value under a stronger assumption than Sloan and Wozniakowski's assumption. We show that quasi-Monte Carlo algorithms using Niederreiter's -sequences and Sobol sequences achieve the optimal convergence order for any 0$"> independent of the dimension with a worst case deterministic guarantee (where is the number of function evaluations). This implies that strong tractability with the best -exponent can be achieved in appropriate weighted Sobolev spaces by using Niederreiter's -sequences and Sobol sequences.

     

Speeding Fermat's factoring method

A factoring method is presented which, heuristically, splits composite in steps. There are two ideas: an integer approximation to provides an algorithm in which is represented as the difference of two rational squares; observing that if a prime divides a square, then divides that square, a heuristic speed-up to steps is achieved. The method is well-suited for use with small computers: the storage required is negligible, and one never needs to work with numbers larger than itself.

     

Reducing the construction cost of the component-by-component construction of good lattice rules

The construction of randomly shifted rank- lattice rules, where the number of points is a prime number, has recently been developed by Sloan, Kuo and Joe for integration of functions in weighted Sobolev spaces and was extended by Kuo and Joe and by Dick to composite numbers. To construct -dimensional rules, the shifts were generated randomly and the generating vectors were constructed component-by-component at a cost of operations. Here we consider the situation where is the product of two distinct prime numbers and . We still generate the shifts randomly but we modify the algorithm so that the cost of constructing the, now two, generating vectors component-by-component is only operations. This reduction in cost allows, in practice, construction of rules with millions of points. The rules constructed again achieve a worst-case strong tractability error bound, with a rate of convergence for 0$">.

     

The Lucas-Pratt primality tree

In 1876, E. Lucas showed that a quick proof of primality for a prime could be attained through the prime factorization of and a primitive root for . V. Pratt's proof that PRIMES is in NP, done via Lucas's theorem, showed that a certificate of primality for a prime could be obtained in modular multiplications with integers at most . We show that for all constants , the number of modular multiplications necessary to obtain this certificate is greater than for a set of primes with relative asymptotic density 1.

     

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.

     

A priori error estimates for Galerkin approximations to porous medium and fast diffusion equations

Galerkin approximations to solutions of a Cauchy-Dirichlet problem governed by the generalized porous medium equation

on bounded convex domains are considered. The range of the parameter includes the fast diffusion case . Using an Euler finite difference approximation in time, the semi-discrete solution is shown to converge to the exact solution in norm with an error controlled by for and for . For the fully discrete problem, a global convergence rate of in norm is shown for the range . For , a rate of is shown in norm.

     

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.