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.

     

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 .

     

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.

     

On the computation of all extensions of a -adic field of a given degree

Let be a -adic field. It is well-known that has only finitely many extensions of a given finite degree. Krasner has given formulae for the number of extensions of a given degree and discriminant. Following his work, we present an algorithm for the computation of generating polynomials for all extensions of a given degree and discriminant.

     

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 .

     

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.

     

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.

     

Convergence of gauge method for incompressible flow

A new formulation, a gauge formulation of the incompressible Navier-Stokes equations in terms of an auxiliary field and a gauge variable , , was proposed recently by E and Liu. This paper provides a theoretical analysis of their formulation and verifies the computational advantages. We discuss the implicit gauge method, which uses backward Euler or Crank-Nicolson in time discretization. However, the boundary conditions for the auxiliary field are implemented explicitly (vertical extrapolation). The resulting momentum equation is decoupled from the kinematic equation, and the computational cost is reduced to solving a standard heat and Poisson equation. Moreover, such explicit boundary conditions for the auxiliary field will be shown to be unconditionally stable for Stokes equations. For the full nonlinear Navier-Stokes equations the time stepping constraint is reduced to the standard CFL constraint . We also prove first order convergence of the gauge method when we use MAC grids as our spatial discretization. The optimal error estimate for the velocity field is also obtained.

     

Noether's problem and and its subgroups

We study Noether's problem for various subgroups of the normalizer of a group generated by an -cycle in , the symmetric group of degree , in three aspects according to the way they act on rational function fields, i.e., , and . We prove that it has affirmative answers for those containing properly and derive a -generic polynomial with four parameters for each . On the other hand, it is known in connection to the negative answer to the same problem for that there does not exist a -generic polynomial for . This leads us to the question whether and how one can describe, for a given field of characteristic zero, the set of -extensions . One of the main results of this paper gives an answer to this question.

     

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.

     

Some properties of the gamma and psi functions, with applications

In this paper, some monotoneity and concavity properties of the gamma, beta and psi functions are obtained, from which several asymptotically sharp inequalities follow. Applying these properties, the authors improve some well-known results for the volume of the unit ball , the surface area of the unit sphere , and some related constants.

     

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 .

     

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.

     

The Whitney extension problem and Lipschitz selections of set-valued mappings in jet-spaces

We study a variant of the Whitney extension problem (1934) for the space . We identify with a space of Lipschitz mappings from into the space of polynomial fields on equipped with a certain metric. This identification allows us to reformulate the Whitney problem for as a Lipschitz selection problem for set-valued mappings into a certain family of subsets of . We prove a Helly-type criterion for the existence of Lipschitz selections for such set-valued mappings defined on finite sets. With the help of this criterion, we improve estimates for finiteness numbers in finiteness theorems for due to C. Fefferman.

     

On polynomial products in nilpotent and solvable Lie groups

We are dealing with Lie groups which are diffeomorphic to , for some . After identifying with , the multiplication on can be seen as a map . We show that if is a polynomial map in one of the two (sets of) variables or , then is solvable. Moreover, if one knows that is polynomial in one of the variables, the group is nilpotent if and only if is polynomial in both its variables.

     

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 .

     

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 , , .

     

Approximating the exponential from a Lie algebra to a Lie group

Consider a differential equation with and , where is a Lie algebra of the matricial Lie group . Every can be mapped to by the matrix exponential map with .

Most numerical methods for solving ordinary differential equations (ODEs) on Lie groups are based on the idea of representing the approximation of the exact solution , , by means of exact exponentials of suitable elements of the Lie algebra, applied to the initial value . This ensures that .

When the exponential is difficult to compute exactly, as is the case when the dimension is large, an approximation of plays an important role in the numerical solution of ODEs on Lie groups. In some cases rational or polynomial approximants are unsuitable and we consider alternative techniques, whereby is approximated by a product of simpler exponentials.

In this paper we present some ideas based on the use of the Strang splitting for the approximation of matrix exponentials. Several cases of and are considered, in tandem with general theory. Order conditions are discussed, and a number of numerical experiments conclude the paper.

     

Sharply localized pointwise and estimates for finite element methods for quasilinear problems

We establish pointwise and estimates for finite element methods for a class of second-order quasilinear elliptic problems defined on domains in . These estimates are localized in that they indicate that the pointwise dependence of the error on global norms of the solution is of higher order. Our pointwise estimates are similar to and rely on results and analysis techniques of Schatz for linear problems. We also extend estimates of Schatz and Wahlbin for pointwise differences in pointwise errors to quasilinear problems. Finally, we establish estimates for the error in , where is a subdomain. These negative norm estimates are novel for linear as well as for nonlinear problems. Our analysis heavily exploits the fact that Galerkin error relationships for quasilinear problems may be viewed as perturbed linear error relationships, thus allowing easy application of properly formulated results for linear problems.

     

An analysis of the Rayleigh-Ritz method for approximating eigenspaces

This paper concerns the Rayleigh-Ritz method for computing an approximation to an eigenspace of a general matrix from a subspace that contains an approximation to . The method produces a pair that purports to approximate a pair , where is a basis for and . In this paper we consider the convergence of as the sine of the angle between and approaches zero. It is shown that under a natural hypothesis--called the uniform separation condition--the Ritz pairs converge to the eigenpair . When one is concerned with eigenvalues and eigenvectors, one can compute certain refined Ritz vectors whose convergence is guaranteed, even when the uniform separation condition is not satisfied. An attractive feature of the analysis is that it does not assume that has distinct eigenvalues or is diagonalizable.