The generalized triangular decomposition

Given a complex matrix , we consider the decomposition , where is upper triangular and and have orthonormal columns. Special instances of this decomposition include the singular value decomposition (SVD) and the Schur decomposition where is an upper triangular matrix with the eigenvalues of on the diagonal. We show that any diagonal for can be achieved that satisfies Weyl's multiplicative majorization conditions:

where is the rank of , is the -th largest singular value of , and is the -th largest (in magnitude) diagonal element of . Given a vector which satisfies Weyl's conditions, we call the decomposition , where is upper triangular with prescribed diagonal , the generalized triangular decomposition (GTD). A direct (nonrecursive) algorithm is developed for computing the GTD. This algorithm starts with the SVD and applies a series of permutations and Givens rotations to obtain the GTD. The numerical stability of the GTD update step is established. The GTD can be used to optimize the power utilization of a communication channel, while taking into account quality of service requirements for subchannels. Another application of the GTD is to inverse eigenvalue problems where the goal is to construct matrices with prescribed eigenvalues and singular values.

     

Jacobi sums and new families of irreducible polynomials of Gaussian periods

Let 2$">, an -th primitive root of 1, mod a prime number, a primitive root modulo and . We study the Jacobi sums , , where is the least nonnegative integer such that mod . We exhibit a set of properties that characterize these sums, some congruences they satisfy, and a MAPLE program to calculate them. Then we use those results to show how one can construct families , , of irreducible polynomials of Gaussian periods, , of degree , where is a suitable set of primes mod . We exhibit examples of such families for several small values of , and give a MAPLE program to construct more of them.

     

Computation of relative class numbers of CM-fields by using Hecke -functions

We develop an efficient technique for computing values at of Hecke -functions. We apply this technique to the computation of relative class numbers of non-abelian CM-fields which are abelian extensions of some totally real subfield . We note that the smaller the degree of the more efficient our technique is. In particular, our technique is very efficient whenever instead of simply choosing (the maximal totally real subfield of ) we can choose real quadratic. We finally give examples of computations of relative class numbers of several dihedral CM-fields of large degrees and of several quaternion octic CM-fields with large discriminants.

     

Computing the multiplicative group of residue class rings

Let be a global field with maximal order and let be an ideal of . We present algorithms for the computation of the multiplicative group of the residue class ring and the discrete logarithm therein based on the explicit representation of the group of principal units. We show how these algorithms can be combined with other methods in order to obtain more efficient algorithms. They are applied to the computation of the ray class group modulo , where denotes a formal product of real infinite places, and also to the computation of conductors of ideal class groups and of discriminants and genera of class fields.

     

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 strong tractability of weighted multivariate integration

We prove that for every dimension and every number of points, there exists a point-set whose -weighted unanchored discrepancy is bounded from above by independently of provided that the sequence has for some (even arbitrarily large) . Here is a positive number that could be chosen arbitrarily close to zero and depends on but not on or . This result yields strong tractability of the corresponding integration problems including approximation of weighted integrals over unbounded domains such as . It also supplements the results that provide an upper bound of the form when .

     

The irreducibility of some level 1 Hecke polynomials

Let be the characteristic polynomial of the Hecke operator acting on the space of level 1 cusp forms . We show that is irreducible and has full Galois group over  for and ,  prime.

     

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 .

     

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.

     

Error estimates for semi-discrete gauge methods for the Navier-Stokes equations

The gauge formulation of the Navier-Stokes equations for incompressible fluids is a new projection method. It splits the velocity in terms of auxiliary (nonphysical) variables and and replaces the momentum equation by a heat-like equation for and the incompressibility constraint by a diffusion equation for . This paper studies two time-discrete algorithms based on this splitting and the backward Euler method for with explicit boundary conditions and shows their stability and rates of convergence for both velocity and pressure. The analyses are variational and hinge on realistic regularity requirements on the exact solution and data. Both Neumann and Dirichlet boundary conditions are, in principle, admissible for but a compatibility restriction for the latter is uncovered which limits its applicability.

     

Efficient CM-constructions of elliptic curves over finite fields

We present an algorithm that, on input of an integer together with its prime factorization, constructs a finite field and an elliptic curve over for which has order . Although it is unproved that this can be done for all , a heuristic analysis shows that the algorithm has an expected run time that is polynomial in , where is the number of distinct prime factors of . In the cryptographically relevant case where is prime, an expected run time can be achieved. We illustrate the efficiency of the algorithm by constructing elliptic curves with point groups of order and nextprime.

     

Wavelet bases in

Some years ago, compactly supported divergence-free wavelets were constructed which also gave rise to a stable (biorthogonal) wavelet splitting of . These bases have successfully been used both in the analysis and numerical treatment of the Stokes and Navier-Stokes equations. In this paper, we construct stable wavelet bases for the stream function spaces . Moreover, -free vector wavelets are constructed and analysed. The relationship between and are expressed in terms of these wavelets. We obtain discrete (orthogonal) Hodge decompositions.

Our construction works independently of the space dimension, but in terms of general assumptions on the underlying wavelet systems in that are used as building blocks. We give concrete examples of such bases for tensor product and certain more general domains . As an application, we obtain wavelet multilevel preconditioners in and .

     

Newton-Cotes integration for approximating Stieltjes (generalized Euler) constants

In the Laurent expansion

of the Riemann-Hurwitz zeta function, the coefficients are known as Stieltjes, or generalized Euler, constants. [When , (the Riemann zeta function), and .] We present a new approach to high-precision approximation of . Plots of our results reveal much structure in the growth of the generalized Euler constants. Our results when for , and when for (for such as 53/100, 1/2, etc.) suggest that published bounds on the growth of the Stieltjes constants can be much improved, and lead to several conjectures. Defining , we conjecture that is attained: for any given , for some (and similarly that, given and , is within of for infinitely many ). In addition we conjecture that satisfies for 1$">. We also conjecture that , a special case of a more general conjecture relating the values of and for . Finally, it is known that for . Using this to define for all real 0$">, we conjecture that for nonintegral , is precisely times the -th (Weyl) fractional derivative at of the entire function . We also conjecture that , now defined for all real arguments 0$">, is smooth. Our numerical method uses Newton-Cotes integration formulae for very high-degree interpolating polynomials; it differs in implementation from, but compares in error bounding to, Euler-Maclaurin summation based methods.

     

Period of the power generator and small values of Carmichael's function

Consider the pseudorandom number generator where we are given the modulus , the initial value and the exponent . One case of particular interest is when the modulus is of the form , where are different primes of the same magnitude. It is known from work of the first and third authors that for moduli , if the period of the sequence exceeds , then the sequence is uniformly distributed. We show rigorously that for almost all choices of it is the case that for almost all choices of , the period of the power generator exceeds . And so, in this case, the power generator is uniformly distributed.

We also give some other cryptographic applications, namely, to ruling-out the cycling attack on the RSA cryptosystem and to so-called time-release crypto.

The principal tool is an estimate related to the Carmichael function , the size of the largest cyclic subgroup of the multiplicative group of residues modulo . In particular, we show that for any , we have for all integers with , apart from at most exceptions.

     

Comparison theorems of Kolmogorov type and exact values of -widths on Hardy-Sobolev classes

Let be a strip in complex plane. denotes those -periodic, real-valued functions on which are analytic in the strip and satisfy the condition , . Osipenko and Wilderotter obtained the exact values of the Kolmogorov, linear, Gel'fand, and information -widths of in , , and 2-widths of in , , .

In this paper we continue their work. Firstly, we establish a comparison theorem of Kolmogorov type on , from which we get an inequality of Landau-Kolmogorov type. Secondly, we apply these results to determine the exact values of the Gel'fand -width of in , . Finally, we calculate the exact values of Kolmogorov -width, linear -width, and information -width of in , , .

     

Inversion of circulant matrices over

In this paper we consider the problem of inverting an circulant matrix with entries over . We show that the algorithm for inverting circulants, based on the reduction to diagonal form by means of FFT, has some drawbacks when working over . We present three different algorithms which do not use this approach. Our algorithms require different degrees of knowledge of and , and their costs range, roughly, from to operations over . Moreover, for each algorithm we give the cost in terms of bit operations. We also present an algorithm for the inversion of finitely generated bi-infinite Toeplitz matrices. The problems considered in this paper have applications to the theory of linear cellular automata.

     

A computational approach to Hilbert modular group fixed points

Some useful information is known about the fundamental domain for certain Hilbert modular groups. The six nonequivalent points with nontrivial isotropy in the fundamental domains under the action of the modular group for , , and have been determined previously by Gundlach. In finding these points, use was made of the exact size of the isotropy groups. Here we show that the fixed points and the isotropy groups can be found without such knowledge by use of a computer scan. We consider the cases and . A computer algebra system and a C compiler were essential in perfoming the computations.

     

Zeta functions of a class of elliptic curves over a rational function field of characteristic two

We show how to calculate the zeta functions and the orders of Tate-Shafarevich groups of the elliptic curves with equation over the rational function field , where is a power of 2. In the range , , odd of degree , the largest values obtained for are (one case), (one case) and (three cases). We observe and discuss a remarkable pattern for the distributions of signs in the functional equation and of fudge factors at places of bad reduction. These imply strong restrictions on the precise form of the Langlands correspondence for GL over local or global fields of characteristic two.

     

Class numbers of real cyclotomic fields of prime conductor

The class numbers of the real cyclotomic fields are notoriously hard to compute. Indeed, the number is not known for a single prime . In this paper we present a table of the orders of certain subgroups of the class groups of the real cyclotomic fields for the primes . It is quite likely that these subgroups are in fact equal to the class groups themselves, but there is at present no hope of proving this rigorously. In the last section of the paper we argue --on the basis of the Cohen-Lenstra heuristics-- that the probability that our table is actually a table of class numbers , is at least .