L'Approximation diophantienne simultanée et l'optimisation discrète

Étant donnée une fonction bornée (supérieurement ou inférieurement) $f:\mathbb{N}^k \To \Real$ par une expression mathématique, le problème de trouver les points extrémaux de $f$ sur chaque ensemble fini $S \subset \mathbb{N}^k$ est bien défini du point de vu classique. Du point de vue de la théorie de la calculabilité néanmoins il faut éviter les cas pathologiques où ce problème a une complexité de Kolmogorov infinie. La principale restriction consiste à définir l'ordre, parce que la comparaison entre les nombres réels n'est pas décidable. On résout ce problème grâce à une structure qui contient deux algorithmes, un algorithme d'analyse réelle récursive pour évaluer la fonction-coût en arithmétique à précision infinie et un autre algorithme qui transforme chaque valeur de cette fonction en un vecteur d'un espace, qui en général est de dimension infinie. On développe trois cas particuliers de cette structure, un de eux correspondant à la méthode d'approximation de Rauzy. Finalement, on établit une comparaison entre les meilleures approximations diophantiennes simultanées obtenues par la méthode de Rauzy (selon l'interprétation donnée ici) et une autre méthode, appelée tétraédrique, que l'on introduit à partir de l'espace vectoriel engendré par les logarithmes de nombres premiers.

Gröbnerbasen in Ore-Algebren

In dieser Arbeit werden grundlegende Algorithmen für Ore-Algebren in Mathematica realisiert. Dabei entsteht eine Plattform um die speziellen Beschränkungen und Möglichkeiten dieser Algebren insbesondere im Zusammenhang mit Gröbnerbasen an praktischen Beispielen auszuloten. Im Gegensatz zu den existierenden Paketen wird dabei explizit die Struktur der Ore-Algebra benutzt. Kandri-Rody und Weispfenning untersuchten 1990 Verallgemeinerungen von Gröbnerbasen auf Algebren ordnungserhaltender Art (``algebras of solvable type''). Diese verhalten sich so, dass Buchbergers Algorithmus stets eine Gröbnerbasis findet. Es wird ein Beispiel gezeigt, an dem klar wird, dass es mehr Ore-Algebren ordnungserhaltender Art gibt als die in der Literatur stets betrachteten Operator-Algebren. Für Ore-Algebren ordnungserhaltender Art werden Algorithmen zu Gröbnerbasen implementiert. Anschließend wird der Gröbner-Walk für Ore-Algebren untersucht. Der Gröbner-Walk im kommutativen Fall wird mit einem instruktiven Beispiel vorgestellt. Dann wird zum nichtkommutativen Fall übergegangen. Es wird gezeigt, dass die Eigenschaft ordnungserhaltender Art zu sein, auf der Strecke zwischen zwei Ordnungen erhalten bleibt. Eine leichte Modifikation des Walks für Ore-Algebren wird implementiert, die im Erfolgsfall die Basis konvertiert und ansonsten abbricht. Es werden Beispiele angegeben, in denen der modifizierte Walk funktioniert sowie ein Beispiel analysiert, in dem er versagt.

Numerical Methods for Non-Stationary Stokes Flow

We consider a first order implicit time stepping procedure (Euler scheme) for the non-stationary Stokes equations in smoothly bounded domains of R3. Using energy estimates we can prove optimal convergence properties in the Sobolev spaces Hm(G) (m = 0;1;2) uniformly in time, provided that the solution of the Stokes equations has a certain degree of regularity. For the solution of the resulting Stokes resolvent boundary value problems we use a representation in form of hydrodynamical volume and boundary layer potentials, where the unknown source densities of the latter can be determined from uniquely solvable boundary integral equations’ systems. For the numerical computation of the potentials and the solution of the boundary integral equations a boundary element method of collocation type is used. Some simulations of a model problem are carried out and illustrate the efficiency of the method.

On optimal computation of MPLS label binding for multipoint-to-point connections

Most network operators have considered reducing Label Switched Routers (LSR) label spaces (i.e. the number of labels that can be used) as a means of simplifying management of underlaying Virtual Private Networks (VPNs) and, hence, reducing operational expenditure (OPEX). This letter discusses the problem of reducing the label spaces in Multiprotocol Label Switched (MPLS) networks using label merging - better known as MultiPoint-to-Point (MP2P) connections. Because of its origins in IP, MP2P connections have been considered to have tree- shapes with Label Switched Paths (LSP) as branches. Due to this fact, previous works by many authors affirm that the problem of minimizing the label space using MP2P in MPLS - the Merging Problem - cannot be solved optimally with a polynomial algorithm (NP-complete), since it involves a hard- decision problem. However, in this letter, the Merging Problem is analyzed, from the perspective of MPLS, and it is deduced that tree-shapes in MP2P connections are irrelevant. By overriding this tree-shape consideration, it is possible to perform label merging in polynomial time. Based on how MPLS signaling works, this letter proposes an algorithm to compute the minimum number of labels using label merging: the Full Label Merging algorithm. As conclusion, we reclassify the Merging Problem as Polynomial-solvable, instead of NP-complete. In addition, simulation experiments confirm that without the tree-branch selection problem, more labels can be reduced

A well-posed integral equation formulation for three-dimensional rough surface scattering

We consider the problem of scattering of time-harmonic acoustic waves by an unbounded sound-soft rough surface. Recently, a Brakhage Werner type integral equation formulation of this problem has been proposed, based on an ansatz as a combined single- and double-layer potential, but replacing the usual fundamental solution of the Helmholtz equation with an appropriate half-space Green's function. Moreover, it has been shown in the three-dimensional case that this integral equation is uniquely solvable in the space L-2 (Gamma) when the scattering surface G does not differ too much from a plane. In this paper, we show that this integral equation is uniquely solvable with no restriction on the surface elevation or slope. Moreover, we construct explicit bounds on the inverse of the associated boundary integral operator, as a function of the wave number, the parameter coupling the single- and double-layer potentials, and the maximum surface slope. These bounds show that the norm of the inverse operator is bounded uniformly in the wave number, kappa, for kappa > 0, if the coupling parameter h is chosen proportional to the wave number. In the case when G is a plane, we show that the choice eta = kappa/2 is nearly optimal in terms of minimizing the condition number.

On integral equation and least squares methods for scattering by diffraction gratings

In this paper we consider the scattering of a plane acoustic or electromagnetic wave by a one-dimensional, periodic rough surface. We restrict the discussion to the case when the boundary is sound soft in the acoustic case, perfectly reflecting with TE polarization in the EM case, so that the total field vanishes on the boundary. We propose a uniquely solvable first kind integral equation formulation of the problem, which amounts to a requirement that the normal derivative of the Green's representation formula for the total field vanish on a horizontal line below the scattering surface. We then discuss the numerical solution by Galerkin's method of this (ill-posed) integral equation. We point out that, with two particular choices of the trial and test spaces, we recover the so-called SC (spectral-coordinate) and SS (spectral-spectral) numerical schemes of DeSanto et al., Waves Random Media, 8, 315-414 1998. We next propose a new Galerkin scheme, a modification of the SS method that we term the SS* method, which is an instance of the well-known dual least squares Galerkin method. We show that the SS* method is always well-defined and is optimally convergent as the size of the approximation space increases. Moreover, we make a connection with the classical least squares method, in which the coefficients in the Rayleigh expansion of the solution are determined by enforcing the boundary condition in a least squares sense, pointing out that the linear system to be solved in the SS* method is identical to that in the least squares method. Using this connection we show that (reflecting the ill-posed nature of the integral equation solved) the condition number of the linear system in the SS* and least squares methods approaches infinity as the approximation space increases in size. We also provide theoretical error bounds on the condition number and on the errors induced in the numerical solution computed as a result of ill-conditioning. Numerical results confirm the convergence of the SS* method and illustrate the ill-conditioning that arises.

Acoustic scattering by mildly rough unbounded surfaces in three dimensions

For a nonlocally perturbed half- space we consider the scattering of time-harmonic acoustic waves. A second kind boundary integral equation formulation is proposed for the sound-soft case, based on a standard ansatz as a combined single-and double-layer potential but replacing the usual fundamental solution of the Helmholtz equation with an appropriate half- space Green's function. Due to the unboundedness of the surface, the integral operators are noncompact. In contrast to the two-dimensional case, the integral operators are also strongly singular, due to the slow decay at infinity of the fundamental solution of the three-dimensional Helmholtz equation. In the case when the surface is sufficiently smooth ( Lyapunov) we show that the integral operators are nevertheless bounded as operators on L-2(Gamma) and on L-2(Gamma G) boolean AND BC(Gamma) and that the operators depend continuously in norm on the wave number and on G. We further show that for mild roughness, i.e., a surface G which does not differ too much from a plane, the boundary integral equation is uniquely solvable in the space L-2(Gamma) boolean AND BC(Gamma) and the scattering problem has a unique solution which satisfies a limiting absorption principle in the case of real wave number.

Duality, observability, and controllability for linear time-varying descriptor systems

A characterization of observability for linear time-varying descriptor systemsE(t)x(t)+F(t)x(t)=B(t)u(t), y(t)=C(t)x(t) was recently developed. NeitherE norC were required to have constant rank. This paper defines a dual system, and a type of controllability so that observability of the original system is equivalent to controllability of the dual system. Criteria for observability and controllability are given in terms of arrays of derivatives of the original coefficients. In addition, the duality results of this paper lead to an improvement on a previous fundamental structure result for solvable systems of the formE(t)x(t)+F(t)x(t)=f(tt).

Scattering by rough surfaces: the Dirichlet problem for the Helmholtz equation in a non-locally perturbed half-plane

We consider the Dirichlet boundary value problem for the Helmholtz equation in a non-locally perturbed half-plane, this problem arising in electromagnetic scattering by one-dimensional rough, perfectly conducting surfaces. We propose a new boundary integral equation formulation for this problem, utilizing the Green's function for an impedance half-plane in place of the standard fundamental solution. We show, at least for surfaces not differing too much from the flat boundary, that the integral equation is uniquely solvable in the space of bounded and continuous functions, and hence that, for a variety of incident fields including an incident plane wave, the boundary value problem for the scattered field has a unique solution satisfying the limiting absorption principle. Finally, a result of continuous dependence of the solution on the boundary shape is obtained.

A novel approach for distributed application scheduling based on prediction of communication events

The evolution of commodity computing lead to the possibility of efficient usage of interconnected machines to solve computationally-intensive tasks, which were previously solvable only by using expensive supercomputers. This, however, required new methods for process scheduling and distribution, considering the network latency, communication cost, heterogeneous environments and distributed computing constraints. An efficient distribution of processes over such environments requires an adequate scheduling strategy, as the cost of inefficient process allocation is unacceptably high. Therefore, a knowledge and prediction of application behavior is essential to perform effective scheduling. In this paper, we overview the evolution of scheduling approaches, focusing on distributed environments. We also evaluate the current approaches for process behavior extraction and prediction, aiming at selecting an adequate technique for online prediction of application execution. Based on this evaluation, we propose a novel model for application behavior prediction, considering chaotic properties of such behavior and the automatic detection of critical execution points. The proposed model is applied and evaluated for process scheduling in cluster and grid computing environments. The obtained results demonstrate that prediction of the process behavior is essential for efficient scheduling in large-scale and heterogeneous distributed environments, outperforming conventional scheduling policies by a factor of 10, and even more in some cases. Furthermore, the proposed approach proves to be efficient for online predictions due to its low computational cost and good precision. (C) 2009 Elsevier B.V. All rights reserved.

ON INTEGRABLE CODIMENSION ONE ANOSOV ACTIONS OF R(k)

In this paper, we consider codimension one Anosov actions of R(k), k >= 1, on closed connected orientable manifolds of dimension n vertical bar k with n >= 3. We show that the fundamental group of the ambient manifold is solvable if and only if the weak foliation of codimension one is transversely affine. We also study the situation where one 1-parameter subgroup of R(k) admits a cross-section, and compare this to the case where the whole action is transverse to a fibration over a manifold of dimension n. As a byproduct, generalizing a Theorem by Ghys in the case k = 1, we show that, under some assumptions about the smoothness of the sub-bundle E(ss) circle plus E(uu), and in the case where the action preserves the volume, it is topologically equivalent to a suspension of a linear Anosov action of Z(k) on T(n).

Cellular automaton model for molecular traffic jams

We consider the time evolution of an exactly solvable cellular automaton with random initial conditions both in the large-scale hydrodynamic limit and on the microscopic level. This model is a version of the totally asymmetric simple exclusion process with sublattice parallel update and thus may serve as a model for studying traffic jams in systems of self-driven particles. We study the emergence of shocks from the microscopic dynamics of the model. In particular, we introduce shock measures whose time evolution we can compute explicitly, both in the thermodynamic limit and for open boundaries where a boundary-induced phase transition driven by the motion of a shock occurs. The motion of the shock, which results from the collective dynamics of the exclusion particles, is a random walk with an internal degree of freedom that determines the jump direction. This type of hopping dynamics is reminiscent of some transport phenomena in biological systems.

Local solvability for a class of evolution equations

Motivated by the celebrated example of Y. Kannai of a linear partial differential operator which is hypoelliptic but not locally solvable, we consider it class of evolution operators with real-analytic coefficients and study their local solvability both in L(2) and in the weak sense. In order to do so we are led to propose a generalization of the Nirenberg-Treves condition (psi) which is suitable to our study. (C) 2009 Published by Elsevier Inc.

COMMUTATIVE FINITE-DIMENSIONAL ALGEBRAS SATISFYING x(x(xy))=0 ARE NILPOTENT

We investigate the structure of commutative non-associative algebras satisfying the identity x(x(xy)) = 0. Recently, Correa and Hentzel proved that every commutative algebra satisfying above identity over a field of characteristic not equal 2 is solvable. We prove that every commutative finite-dimensional algebra u over a field F of characteristic not equal 2, 3 which satisfies the identity x(x(xy)) = 0 is nilpotent. Furthermore, we obtain new identities and properties for this class of algebras.

BASS CYCLIC UNITS AS FACTORS IN A FREE GROUP IN INTEGRAL GROUP RING UNITS

Marciniak and Sehgal showed that if u is a non-trivial bicyclic unit of an integral group ring then there is a bicyclic unit v such that u and v generate a non-abelian free group. A similar result does not hold for Bass cyclic units of infinite order based on non-central elements as some of them have finite order modulo the center. We prove a theorem that suggests that this is the only limitation to obtain a non-abelian free group from a given Bass cyclic unit. More precisely, we prove that if u is a Bass cyclic unit of an integral group ring ZG of a solvable and finite group G, such that u has infinite order modulo the center of U(ZG) and it is based on an element of prime order, then there is a non-abelian free group generated by a power of u and a power of a unit in ZG which is either a Bass cyclic unit or a bicyclic unit.