Tropical differential equations

Tropical differential equations are introduced and an algorithm is designed which tests solvability of a system of tropical linear differential equations within the complexity polynomial in the size of the system and in the absolute values of its coefficients. Moreover, we show that there exists a minimal solution, and the algorithm constructs it (in case of solvability). This extends a similar complexity bound established for tropical linear systems. In case of tropical linear differential systems in one variable a polynomial complexity algorithm for testing its solvability is designed.We prove also that the problem of solvability of a system of tropical non-linear differential equations in one variable is NP-hard, and this problem for arbitrary number of variables belongs to NP. Similar to tropical algebraic equations, a tropical differential equation expresses the (necessary) condition on the dominant term in the issue of solvability of a differential equation in power series.     

Characterization and computation of control invariant sets for linear impulsive control systems

Impulsive control systems are suitable to describe and control a venue of real-life problems, going from disease treatment to aerospace guidance. The main characteristic of such systems is that they evolve freely in-between impulsive actions, which makes it difficult to guarantee its permanence in a given state-space region. In this work, we develop a method for characterizing and computing approximations to the maximal control invariant sets for linear impulsive control systems, which can be explicitly used to formulate a set-based model predictive controller. We approach this task using a tractable and non-conservative characterization of the admissible state sets, namely the states whose free response remains within given constraints, emerging from a spectrahedron representation of such sets for systems with rational eigenvalues. The so-obtained impulsive control invariant set is then explicitly used as a terminal set of a predictive controller, which guarantees the feasibly asymptotic convergence to a target set containing the invariant set. Necessary conditions under which an arbitrary target set contains an impulsive control invariant set (and moreover, an impulsive control equilibrium set) are also provided, while the controller performance are tested by means of two simulation examples.     

Eléments finis stochastiques en élasticité linéaireA stochastic finite element method in linear mechanics

The stochastic finite element method presented in this Note consists in representing in a probabilistic form the response of a linear mechanical system whose material properties and loading are random. Each input random variable is expanded into a Hermite polynomial series in standard normal random variables. The response (e.g., the nodal displacement vector) is expanded onto the so-called polynomial chaos. The coefficients of the expansion are obtained by a Galerkin-type method in the space of probability. To cite this article: B. Sudret et al., C. R. Mecanique 332 (2004).     

Conical Kakeya and Nikodym sets in finite fields

A Kakeya set contains a line in each direction. Dvir proved a lower bound on the size of any Kakeya set in a finite field using the polynomial method. We prove analogues of Dvir's result for non-degenerate conics, that is, parabolae and hyperbolae (but not ellipses which do not have a direction). We also study so-called conical Nikodym sets where a small variation of the proof provides a lower bound on their sizes. (Here ellipses are included.)Note that the bound on conical Kakeya sets has been known before, however, without an explicitly given constant which is included in our result and close to being best possible.     

The polynomial reconstruction problem: The first 50 years

The problem of reconstructing the characteristic polynomial of a graph of order at least 3 from the collection of characteristic polynomials of its vertex-deleted subgraphs was posed by Cvetkovi? in 1973 as a spectral counter part to the well-known Ulam's reconstruction conjecture. Over the last 50 years, this problem has received notable attention, many positive results have been obtained, but in the general case the problem is still unresolved. In particular, no counter example is found in literature. In this expository paper we survey classical and some more recent results concerning the polynomial reconstruction problem, discuss some related problems, variations and generalizations.     

Uniform stability of semilinear wave equations with arbitrary local memory effects versus frictional dampings

This paper is concerned with the mixed initial–boundary value problem for semilinear wave equations with complementary frictional dampings and memory effects. We successfully establish uniform exponential and polynomial decay rates for the solutions to this initial–boundary value problem under much weak conditions concerning memory effects. More specifically, we obtain the exponential and polynomial decay rates after removing the fundamental condition that the memory-effect region includes a part of the system boundary, while the condition is a necessity in the previous literature; moreover, for the polynomial decay rates we only assume minimal conditions on the memory kernel function g, without the usual assumption of $g^{\prime }$ controlled by g.     

A fitting algorithm for real coefficient polynomial rooting

A new algorithm for computing all roots of polynomials with real coefficients is introduced. The principle behind the new algorithm is a fitting of the convolution of two subsequences onto a given polynomial coefficient sequence. This concept is used in the initial stage of the algorithm for a recursive slicing of a given polynomial into degree-2 subpolynomials from which initial root estimates are computed in closed form. This concept is further used in a post-fitting stage where the initial root estimates are refined to high numerical accuracy. A reduction of absolute root errors by a factor of 100 compared to the famous Companion matrix eigenvalue method based on the unsymmetric QR algorithm is not uncommon. Detailed computer experiments validate our claims.     

Scheduling Problems and Mixed Graph Colorings

Some scheduling problems induce a mixed graph coloring, i.e., an assignment of positive integers (colors) to vertices of a mixed graph such that, if two vertices are joined by an edge, then their colors have to be different, and if two vertices are joined by an arc, then the color of the startvertex has to be not greater than the color of the endvertex. We discuss some algorithms for coloring the vertices of a mixed graph with a small number t of colors and present computational results for calculating the chromatic number, i.e., the minimal possible value of such a t . We also study the chromatic polynomial of a mixed graph which may be used for calculating the number of feasible schedules.