Stable polyhedra in parameter space

A typical uncertainty structure of a characteristic polynomial is P(s)=A(s)Q(s)+B(s) with A(s) and B(s) fixed and Q(s) uncertain. In robust controller design Q(s) may be a controller numerator or denominator polynomial; an example is the PID controller with Q(s)=K_I+K_Ps+K_Ds². In robustness analysis Q(s) may describe a plant uncertainty. For fixed imaginary part of Q(jω), it is shown that Hurwitz stability boundaries in the parameter space of the even part of Q(jω) are hyperplanes and the stability regions are convex polyhedra. A dual result holds for fixed real part of Q(jω). Also σ-stability with the real parts of all roots of P(s) smaller than σ is treated.Under the above conditions, the roots of P(s) can cross the imaginary axis only at a finite number of discrete “singular” frequencies. Each singular frequency generates a hyperplane as stability boundary. An application is robust controller design by simultaneous stabilization of several representatives of A(s) and B(s) by a PID controller. Geometrically, the intersection of convex polygons must be calculated and represented tomographically for a grid on K_P.     

An Efficient Algorithm for the k-Pairwise Disjoint Paths Problem in Hypercubes

A graph G(V, E) (|V|⩾2k) satisfies property A_k if, given k pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) of V(G), there are k mutually node-disjoint paths, one connecting s_i and t_i for each i, 1⩽i⩽k. A necessary condition for any graph to satisfy A_k is that it is (2k−1)-connected. Hypercubes are important interconnection topologies for parallel computation and communication networks. It has been known that hypercubes of dimension n (which are n-connected) satisfy A_⌈n/2⌉. In this paper we give an algorithm which, given k=⌈n/2⌉ pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) in the n-dimensional hypercube, finds the k disjoint paths of length at most n+⌈log n⌉+1 in O(n² log* n) time.     

Truncations of infinite matrices and algebraic series associated with some of grammars

We consider an algebraic system over $\text{R}$[x] of the form X = a₀(x)X^k+ a_k1(x)X+a_k(x), where a₀(x) and a_k(x) are in x$\text{R}$[x] and a_k?1(x) is in x$\text{R}$. Let A be the infinite incidence matrix associated with the algebraic system. Then we prove that the eigenvalues of northwest corner truncations of A are dense in some algebraic curves.Using this we get a result on positive algebraic series. We consider the case that the coefficients of a₁(x)(i = 0,…,k?1, k) are positive. The algebraic series generated by the algebraic system may be viewed as a function in the complex variable x. Then by the above fact we prove that the radius of convergence of the function equals the least positive zero of the modified discriminant of the system.As an application to context free languages we show a procedure for calculating the entropy of some one counter languages. Other applications to Dyck languages and the Lukasiewicz language are also described.     

Efficient evaluation of specific queries in constraint databases

Let F₁,…,Fs∈R[X₁,…,Xn] be polynomials of degree at most d, and suppose that F₁,…,Fs are represented by a division free arithmetic circuit of non-scalar complexity size L. Let A be the arrangement of Rn defined by F₁,…,Fs.For any point x∈Rn, we consider the task of determining the signs of the values F₁(x),…,Fs(x) (sign condition query) and the task of determining the connected component of A to which x belongs (point location query). By an extremely simple reduction to the well-known case where the polynomials F₁,…,Fs are affine linear (i.e., polynomials of degree one), we show first that there exists a database of (possibly enormous) size sO(L+n) which allows the evaluation of the sign condition query using only (Ln)^O(1)log(s) arithmetic operations. The key point of this paper is the proof that this upper bound is almost optimal.By the way, we show that the point location query can be evaluated using dO(n)log(s) arithmetic operations. Based on a different argument, analogous complexity upper-bounds are exhibited with respect to the bit-model in case that F₁,…,Fs belong to Z[X₁,…,Xn] and satisfy a certain natural genericity condition. Mutatis mutandis our upper-bound results may be applied to the sparse and dense representations of F₁,…,Fs.     

A proof of the Gilbert-Pollak conjecture on the Steiner ratio

LetP be a set ofn points on the euclidean plane. LetL _s(P) andL _m (P) denote the lengths of the Steiner minimum tree and the minimum spanning tree onP, respectively. In 1968, Gilbert and Pollak conjectured that for anyP,L _s (P)≥(√3/2)L _m (P). We provide a proof for their conjecture in this paper.     

Structural synthesis of multivariable controllers

In this paper the problem of achieving a desired transfer function matrix H_d(s) between external inputs and controlled outputs in a linear multivariable system by connecting proper, stabilizing controllers between measured outputs and control inputs is solved in both transfer function and state space settings. The class H_d of achievable transfer functions is directly and constructively characterized via the theory of transfer function valuations. For each H_d(s)ϵH_d, the class of synthesizing controllers is determined. Similar valuation conditions are given for the asymptotic tracking and disturbance rejection problem in which H_d(s) is only partially specified. These results extend and complement earlier results. The state space geometric solution of the problem of achieving a desired H_d(s) is obtained by formulating it as an equivalent output feedback disturbance rejection problem. A constructive solvability condition in terms of a pair of measurement and control invariant subspaces is given. This requires a nontrivial generalization of the notion of (C, A, B) pairs. An H_d(s) is shown to be admissible if and only if it induces an appropriate pair of invariant subspaces. The signal flow structure and certain factorizability conditions for a robust synthesis of the output feedback disturbance rejection problem are also given which extend earlier results on robust state feedback disturbance rejection. It is shown that every compensator corresponds to a state feedback control law implemented by an unknown input observer. The results of this paper are expected to be useful in the development of parameter optimization or other computer aided design algorithms where response specifications are to be traded against other design criteria such as sensitivity or stability margins since they explicitly characterize the algebraic variety H_d in which the response transfer function may lie.     

An approximation method for high-order fractional derivatives of algebraically singular functions

The fractional derivative D^qf(s) (0≤s≤1) of a given function f(s) with a positive non-integer q is defined in terms of an indefinite integral. We propose a uniform approximation scheme to D^qf(s) for algebraically singular functions f(s)=s^αg(s) (α>−1) with smooth functions g(s). The present method consists of interpolating g(s) at sample points t_j in [0,1] by a finite sum of the Chebyshev polynomials. We demonstrate that for the non-negative integer m such that m<q<m+1, the use of high-order derivatives g⁽ⁱ⁾(0) and g⁽ⁱ⁾(1) (0≤i≤m) at both ends of [0,1] as well as g(t_j), t_j∈[0,1] in interpolating g(s), is essential to uniformly approximate D^q{s^αg(s)} for 0≤s≤1 when α≥q−m−1. Some numerical examples in the simplest case 1<q<2 are included.     

On Steiner minimal trees withL p distance

LetL _p be the plane with the distanced _p (A ₁ ,A ₂ ) = (¦x ₁ ?x ₂¦ ^p + ¦y₁ ?y ₂¦^p)^/1p wherex _i andy _i are the cartesian coordinates of the pointA _i . LetP be a finite set of points inL _p . We consider Steiner minimal trees onP. It is proved that, for 1 <p < ∞, each Steiner point is of degree exactly three. Define the Steiner ratio ? _p to be inf{L _s (P)/L _m (P)¦P?L _p } whereL _s (P) andL _m (P) are lengths of the Steiner minimal tree and the minimal spanning tree onP, respectively. Hwang showed ?₁ = 2/3. Chung and Graham proved ?₂ > 0.842. We prove in this paper that ?{∞} = 2/3 and √(√2/2)?₁?₂ ≤ ?_p ≤ √3/2 for anyp.     

Some characterizations of finitely specifiable implicational dependency families

Let r be a relation for the relation scheme R(A₁,A₂,…,A_n); then we define Dom(r) to be Dom_r(A₁)×Dom_r(A₂)×…×Dom_r(A_n), where Dom_r(A_i) for each i is the set of all ith coordinates of tuples of r. A relation s is said to be a substructure of the relation r if and only if Dom(s)∩r = s.The following theorems analogous to Tarski-Fraisse-Vaught's characterizations of universal classes are proved: (i) An implicational dependency family (ID-family) F over the relation scheme R is finitely specifiable if and only if there exists a finite number of relations r₁,r₂,…,r_m for R such that r ∈ F if and only if no r_i is isomorphic to a substructure of r. (ii) F is finitely specifiable if and only if there exists a natural number k such that r ∈ F whenever F contains all substructures of r with at most k elements.We shall use these characterizations to obtain a new proof for Hull's (1984) characterization of finitely specifiable ID-families.     

Scalable 2D Convex Hull and Triangulation Algorithms for Coarse Grained Multicomputers

In this paper we describe scalable parallel algorithms for building the convex hull and a triangulation ofncoplanar points. These algorithms are designed for thecoarse grained multicomputermodel:pprocessors withO(n/p)⪢O(1) local memory each, connected to some arbitrary interconnection network. They scale over a large range of values ofnandp, assuming only thatn⩾p^1+ε(ε>0) and require timeO((T_sequential/p)+T_s(n, p)), whereT_s(n, p) refers to the time of a global sort ofndata on approcessor machine. Furthermore, they involve only a constant number of global communication rounds. Since computing either 2D convex hull or triangulation requires timeT_sequential=Θ(n log n) these algorithms either run in optimal time,Θ((n log n)/p), or in sort time,T_s(n, p), for the interconnection network in question. These results become optimal whenT_sequential/pdominatesT_s(n, p) or for interconnection networks like the mesh for which optimal sorting algorithms exist.     

On decoupling the H-optimal sensitivity problem for products of plants

In this note we show how to solve the H^∞-optimal sensitivity problem for a SISO plant P(s) = P₁(s)P₂(s), given the solutions for P₁(s), P₂(s). This allows us to solve the problem for systems of the form e^−hsP₀(s), where P₀(s) is the transfer function of a stable, LTI, finite dimensional system.     

A generalization of the Schützenberger product of finite monoids

For each n?1, an n-ary product ? on finite monoids is constructed. This product has the following property: Let Σ be a finite alphabet and Σ¹ the free monoid generated by Σ. For i = 1, …,n, let A_i be a recognizable subset of Σ¹, M(A_i) the syntactic monoid of A_n and M(A₁?A_n) the syntactic monoid of the concatenation product A₁?A_n. Then M(A₁?A_n)< ? (M(A₁),…,M(A_n)). The case n = 2 was studied by Schützenberger. As an application of the generalized product, I prove the theorem of Brzozowski and Knast that the dot-depth hierarchy of star-free sets is infinite.     

Exact asymptotics of large deviations of stationary Ornstein-Uhlenbeck processes for L p-functionals, p > 0

We prove a general result on the exact asymptotics of the probability $P\left\{ {\int\limits_0^1 {\left| {\eta _\gamma (t)} \right|^p dt > u^p } } \right\}$ as u → ∞, where p > 0, for a stationary Ornstein-Uhlenbeck process η _γ(t), i.e., a Gaussian Markov process with zero mean and with the covariance function Eη_γ(t)η_γ(s), t, s ∈ ?, γ > 0. We use the Laplace method for Gaussian measures in Banach spaces. Evaluation of constants is reduced to solving an extreme value problem for the rate function and studying the spectrum of a second-order differential operator of the Sturm-Liouville type. For p = 1 and p = 2, explicit formulas for the asymptotics are given.     

Positive solutions of singular Dirichlet and periodic boundary value problems

Let A and T be positive numbers. The singular differential equation (r(x)x′)′ = μq(t)f(t, x) is considered. Here r > 0 on (0, A] may be singular at x = 0, and f(t, x) ≤ 0 may be singular at x = 0 and x = A. Effective sufficient conditions imposed on r, μ, q, and f are given for the existence of a solution x to the above equation satisfying either the Dirichlet conditions x(0) = x(T) = 0 or the periodic conditions x(0) = x(T), x′(0) = x′(T), and, in addition, 0 < x < A on (0, T).     

A sixth-order extrapolation method for special nonlinear fourth-order boundary value problems

A sixth-order convergent finite difference method is developed for the numerical solution of the special nonlinear fourth-order boundary value problem y^(iv)(x) = f(x, y), a < x < b, y(a) = A₀, y″(a) = B₀, y(b) = A₁ y′(b) = B₁, the simple-simple beam problem.The method is based on a second-order convergent method which is used on three grids, sixth-order convergence being obtained by taking a linear combination of the (second-order) numerical results calculated using the three individual grids.Special formulas are proposed for application to points of the discretization adjacent to the boundaries x = a and x= b, the first two terms of the local truncation errors of these formulas being the same as those of the second-order method used at the other points of each grid.Modifications to these two formulas are obtained for problems with boundary conditions of the form y(a) = A₀, y′(a) = C₀, y(b) = A₁, y′(b) = C₁, the clamped-clamped beam problem.The general boundary value problem, for which the differential equation is y^(iv)(x) = f(x, y, y′, y″, y‴), is also considered.     

Cycles embedding in exchanged hypercubes

The exchanged hypercube EH(s,t), proposed by Loh et al., is obtained by systematically removing links from a binary hypercube. This paper investigates important properties related to embedding cycles into the exchanged hypercube EH(s,t). The authors show that EH(1,t) and EH(2,2) are not bipancyclic, but EH(s,t) (2?s?t) except EH(2,2) is bipancyclic and EH(s,t) (3?s?t) is vertex-bipancyclic. Moreover, every edge of EH(s,t) (2?s?t) lies on an even l-cycle where 8?l?²s+t+1.     

Partitions of the set of selected unknowns in linear differential–algebraic systems

As was shown earlier, for a linear differential–algebraic system A ₁ y′ + A ₀ y = 0 with a selected part of unknowns (entries of a column vector y), it is possible to construct a differential system ?′ = B ?, where the column vector ? is formed by some entries of y, and a linear algebraic system by means of which the selected entries that are not contained in ? can be expressed in terms of the selected entries included in ?. In the paper, sizes of the differential and algebraic systems obtained are studied. Conditions are established under the fulfillment of which the size of the algebraic system is determined unambiguously and the size of the differential system is minimal.     

Multiplier design for extended strict positive realness and its applications

Given a stable square plant G ₁(s), based on linear matrix inequality (LMI) method, necessary and sufficient conditions are presented for the existence of a stable multiplier G ₂(s) such that G ₁(s)G ₂(s) is extended strictly positive real (ESPR). Furthemore, for uncertain plants, the corresponding problems are considered and solved. An application to the study of dichotomy for pendulum-like systems is also presented. Examples are given to illustrate the results.