Numerical Simulation of Decaying Turbulence in an Adaptive Wavelet Basis

The present note is concerned with the numerical simulation of two-dimensional homogeneous decaying turbulence. We employ a Galerkin-type discretization in an adaptive basis of orthogonal wavelets. Therewith the solution is represented by means of a reduced basis being adapted at each time step. This is one of the first times that wavelet decomposition of a turbulent flow field has been used not only for a posteriori analysis but directly for the computation of the flow in a reduced basis. A classical Fourier method furnishesa suitable reference solution.     

Positivity of cubic polynomials on intervals and positive spline interpolation

A criterion for the positivity of a cubic polynomial on a given interval is derived. By means of this result a necessary and sufficient condition is given under which cubicC ¹-spline interpolants are nonnegative. Further, since such interpolants are not uniquely determined, for selecting one of them the geometric curvature is minimized. The arising optimization problem is solved numerically via dualization.     

Solvable absolute Galois groups are metabelian

We show that solvable absolute Galois groups have an abelian normal subgroup such that the quotient is the direct product of two finite cyclic and a torsion-free procyclic group. In particular, solvable absolute Galois groups are metabelian. Moreover, any field with solvable absolute Galois group G admits a non-trivial henselian valuation, unless each Sylow-subgroup of G is either procyclic or isomorphic to Z ₂⋊Z/2Z. A complete classification of solvable absolute Galois groups (up to isomorphism) is given. Oblatum 22-IV-1998 & 1-IX-2000?Published online: 30 October 2000     

A partition-based relaxation for Steiner trees

The Steiner tree problem is a classical NP-hard optimization problem with a wide range of practical applications. In an instance of this problem, we are given an undirected graph G = (V, E), a set of terminals \({R\subseteq V}\) , and non-negative costs c _e for all edges \({e \in E}\) . Any tree that contains all terminals is called a Steiner tree; the goal is to find a minimum-cost Steiner tree. The vertices \({V \backslash R}\) are called Steiner vertices. The best approximation algorithm known for the Steiner tree problem is a greedy algorithm due to Robins and Zelikovsky (SIAM J Discrete Math 19(1):122–134, 2005); it achieves a performance guarantee of \({1+\frac{\ln 3}{2}\approx 1.55}\) . The best known linear programming (LP)-based algorithm, on the other hand, is due to Goemans and Bertsimas (Math Program 60:145–166, 1993) and achieves an approximation ratio of 2?2/|R|. In this paper we establish a link between greedy and LP-based approaches by showing that Robins and Zelikovsky’s algorithm can be viewed as an iterated primal-dual algorithm with respect to a novel LP relaxation. The LP used in the first iteration is stronger than the well-known bidirected cut relaxation. An instance is b-quasi-bipartite if each connected component of \({G \backslash R}\) has at most b vertices. We show that Robins’ and Zelikovsky’s algorithm has an approximation ratio better than \({1+\frac{\ln 3}{2}}\) for such instances, and we prove that the integrality gap of our LP is between \({\frac{8}{7}}\) and \({\frac{2b+1}{b+1}}\) .     

The combination technique and some generalisations

The combination technique has repeatedly been shown to be an effective tool for the approximation with sparse grid spaces. Little is known about the reasons of this effectiveness and in some cases the combination technique can even break down. It is known, however, that the combination technique produces an exact result in the case of a projection into a sparse grid space if the involved partial projections commute.

The performance of the combination technique is analysed using a projection framework and the C/S decomposition. Error bounds are given in terms of angles between the spanning subspaces or the projections onto these subspaces. Based on this analysis modified combination coefficients are derived which are optimal in a certain sense and which can substantially extend the applicability and performance of the combination technique.     

Stability criteria for positive linear discrete-time systems

Positivity - We prove new characterisations of exponential stability for positive linear discrete-time systems in ordered Banach spaces, in terms of small-gain conditions. Such conditions have...     

Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set  of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time  . The results are based on problem kernelization and a new “geometric ( -separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.”