On Meinardus' examples for the conjugate gradient method

The conjugate gradient (CG) method is widely used to solve a positive definite linear system of order . It is well known that the relative residual of the th approximate solution by CG (with the initial approximation ) is bounded above by

   with

where is 's spectral condition number. In 1963, Meinardus (Numer. Math., 5 (1963), pp. 14-23) gave an example to achieve this bound for but without saying anything about all other . This very example can be used to show that the bound is sharp for any given by constructing examples to attain the bound, but such examples depend on and for them the th residual is exactly zero. Therefore it would be interesting to know if there is any example on which the CG relative residuals are comparable to the bound for all . There are two contributions in this paper:

1. A closed formula for the CG residuals for all on Meinardus' example is obtained, and in particular it implies that the bound is always within a factor of of the actual residuals;
2. A complete characterization of extreme positive linear systems for which the th CG residual achieves the bound is also presented.

     

Convergence of classes of high-order semi-Lagrangian schemes for the Vlasov-Poisson system

In this paper we present some classes of high-order semi-Lagran- gian schemes for solving the periodic one-dimensional Vlasov-Poisson system in phase-space on uniform grids. We prove that the distribution function and the electric field converge in the norm with a rate of

where is the degree of the polynomial reconstruction, and and are respectively the time and the phase-space discretization parameters.

     

Explicit values of multi-dimensional Kloosterman sums for prime powers, II

For any integer fix , and let denote the group of reduced residues modulo . Let , a power of a prime . The hyper-Kloosterman sums of dimension are defined for by

where denotes the multiplicative inverse of modulo .

Salie evaluated in the classical setting for even , and for odd with . Later, Smith provided formulas that simplified the computation of in these cases for . Recently, Cochrane, Liu and Zheng computed upper bounds for in the general case , stopping short of their explicit evaluation. Here I complete the computation they initiated to obtain explicit values for the Kloosterman sums for , relying on basic properties of some simple specialized exponential sums. The treatment here is more elementary than the author's previous determination of these Kloosterman sums using character theory and -adic methods. At the least, it provides an alternative, independent evaluation of the Kloosterman sums.

     

Detecting perfect powers by factoring into coprimes

This paper presents an algorithm that, given an integer , finds the largest integer such that is a th power. A previous algorithm by the first author took time where ; more precisely, time ; conjecturally, time . The new algorithm takes time . It relies on relatively complicated subroutines--specifically, on the first author's fast algorithm to factor integers into coprimes--but it allows a proof of the bound without much background; the previous proof of relied on transcendental number theory.

The computation of is the first step, and occasionally the bottleneck, in many number-theoretic algorithms: the Agrawal-Kayal-Saxena primality test, for example, and the number-field sieve for integer factorization.

     

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.

     

A counterexample concerning the -projector onto linear spline spaces

For the -orthogonal projection onto spaces of linear splines over simplicial partitions in polyhedral domains in , , we show that in contrast to the one-dimensional case, where independently of the nature of the partition, in higher dimensions the -norm of cannot be bounded uniformly with respect to the partition. This fact is folklore among specialists in finite element methods and approximation theory but seemingly has never been formally proved.

     

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.

     

Uniform error estimates in the finite element method for a singularly perturbed reaction-diffusion problem

Consider the problem with homogeneous Neumann boundary condition in a bounded smooth domain in . The whole range is treated. The Galerkin finite element method is used on a globally quasi-uniform mesh of size ; the mesh is fixed and independent of .

A precise analysis of how the error at each point depends on and is presented. As an application, first order error estimates in , which are uniform with respect to , are given.

     

Practical solution of the Diophantine equation

Let be an odd prime and , positive integers. In this note we prove that the problem of the determination of the integer solutions to the equation can be easily reduced to the resolution of the unit equation over . The solutions of the latter equation are given by Wildanger's algorithm.

     

On splitting methods for Schrödinger-Poisson and cubic nonlinear Schrödinger equations

We give an error analysis of Strang-type splitting integrators for nonlinear Schrödinger equations. For Schrödinger-Poisson equations with an -regular solution, a first-order error bound in the norm is shown and used to derive a second-order error bound in the norm. For the cubic Schrödinger equation with an -regular solution, first-order convergence in the norm is used to obtain second-order convergence in the norm. Basic tools in the error analysis are Lie-commutator bounds for estimating the local error and -conditional stability for error propagation, where for the Schrödinger-Poisson system and for the cubic Schrödinger equation.

     

Coding the principal character formula for affine Kac-Moody lie algebras

In this paper, an algorithm for computing the principal character for affine Lie algebras is discussed and presented. The principal characters discovered using this program are given and/or proven. Results include level 2 and 3 character formulas in and the sole existence of the Rogers-Ramanujan products in , , , , , , .     

Modified Taylor reproducing formulas and h-p clouds

We study two different approximations of a multivariate function by operators of the form , where is an -reproducing partition of unity and are modified Taylor polynomials of degree expanded at . The first approximation was introduced by Xuli (2003) in the univariate case and generalized for convex domains by Guessab et al. (2005). The second one was introduced by Duarte (1995) and proved in the univariate case. In this paper, we first relax the Guessab's convexity assumption and we prove Duarte's reproduction formula in the multivariate case. Then, we introduce two related reproducing quasi-interpolation operators in Sobolev spaces. A weighted error estimate and Jackson's type inequalities for h-p cloud function spaces are obtained. Last, numerical examples are analyzed to show the approximative power of the method.

     

An -local discontinuous Galerkin method for some quasilinear elliptic boundary value problems of nonmonotone type

In this paper, an -local discontinuous Galerkin method is applied to a class of quasilinear elliptic boundary value problems which are of nonmonotone type. On -quasiuniform meshes, using the Brouwer fixed point theorem, it is shown that the discrete problem has a solution, and then using Lipschitz continuity of the discrete solution map, uniqueness is also proved. A priori error estimates in broken norm and norm which are optimal in , suboptimal in are derived. These results are exactly the same as in the case of linear elliptic boundary value problems. Numerical experiments are provided to illustrate the theoretical results.

     

Modular exponentiation via the explicit Chinese remainder theorem

Fix pairwise coprime positive integers . We propose representing integers modulo , where is any positive integer up to roughly , as vectors . We use this representation to obtain a new result on the parallel complexity of modular exponentiation: there is an algorithm for the Common CRCW PRAM that, given positive integers , , and in binary, of total bit length , computes in time using processors. For comparison, a parallelization of the standard binary algorithm takes superlinear time; Adleman and Kompella gave an expected time algorithm using processors; von zur Gathen gave an NC algorithm for the highly special case that is polynomially smooth.

     

Computing the structure of a finite abelian group

We present an algorithm that computes the structure of a finite abelian group from a generating system . The algorithm executes group operations and stores group elements.

     

Divisors in residue classes, constructively

Let be integers satisfying , , , and let . Lenstra showed that the number of integer divisors of equivalent to is upper bounded by . We re-examine this problem, showing how to explicitly construct all such divisors, and incidentally improve this bound to .

     

Continued fractions in local fields, II

The present paper is a continuation of an earlier work by the author. We propose some new definitions of -adic continued fractions. At the end of the paper we give numerical examples illustrating these definitions. It turns out that for every if then has a periodic continued fraction expansion. The same is not true in for some larger values of

     

Heuristics for class numbers and lambda invariants

Let be an imaginary quadratic field and let be the associated real quadratic field. Starting from the Cohen-Lenstra heuristics and Scholz's theorem, we make predictions for the behaviors of the 3-parts of the class groups of these two fields as varies. We deduce heuristic predictions for the behavior of the Iwasawa -invariant for the cyclotomic -extension of and test them computationally.

     

A nonconforming combination of the finite element and volume methods with an anisotropic mesh refinement for a singularly perturbed convection-diffusion equation

In this paper we formulate and analyze a discretization method for a 2D linear singularly perturbed convection-diffusion problem with a singular perturbation parameter . The method is based on a nonconforming combination of the conventional Galerkin piecewise linear triangular finite element method and an exponentially fitted finite volume method, and on a mixture of triangular and rectangular elements. It is shown that the method is stable with respect to a semi-discrete energy norm and the approximation error in the semi-discrete energy norm is bounded by with independent of the mesh parameter , the diffusion coefficient and the exact solution of the problem.

     

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.