The only stable normal forms of affine systems under feedback are linear

We consider the problem of existence of structurally stable normal forms of affine control systems with m inputs and n-dimensional state space, equipped with C^∞-Whitney topology and acted on by the static state feedback group. It is proved that structurally stable normal forms exist only if m = n or m =1 and n = 2, and are linear. There are no stable normal forms in any other range of dimensions (m, n).     

Fast Parallel Algorithms for Solving Triangular Systems of Linear Equations on the Hypercube

This paper presents efficient hypercube algorithms for solving triangular systems of linear equations by using various matrix partitioning and mapping schemes. Recently, several parallel algorithms have been developed for this problem. In these algorithms, the triangular solver is treated as the second stage of Gauss elimination. Thus, the triangular matrix is distributed by columns (or rows) in a wrap fashion since it is likely that the matrix is distributed this way after an LU decomposition has been done on the matrix. However, the efficiency of the algorithms is low. Our motivation is to develop various data partitioning and mapping schemes for hypercube algorithms by treating the triangular solver as an independent problem. Theoretically, the computation time of our best algorithm is ((12p + 1)n² + 36p³ − 28p²)/(24p²), and an upper bound on the communication time is 2αp log p (log n − log p) + 2α(log n − log p − 1) log p + (cn/p − 2c)(2 log p − 1) + log p(cn − c − α), where α is the (communication startup time)/(one entry scanning time), c is a constant, n is the order of the triangular system and p is the number of nodes in the hypercube. Experimental results show that the algorithm is efficient. The efficiency of the algorithm is 0.945 when p = 2, n = 513, and 0.93 when p = 8, n = 1025.     

Existence of triple positive solutions of two-point right focal boundary value problems on time scales

We consider the following boundary value problem, (−1)ⁿ⁻¹y^Δn(t)=(−1)^p+1F(t,y(σⁿ⁻¹(t))),t[a,b]∩T, y^Δn(a)=0,0≤i≤p−1, y^Δn(σ(b))=0,p≤i≤n−1,where n ≥ 2, 1 ≤ p ≤ n - 1 is fixed and T is a time scale. By applying fixed-point theorems for operators on a cone, existence criteria are developed for triple positive solutions of the boundary value problem. We also include examples to illustrate the usefulness of the results obtained.     

Distributions having bases which generate finite dimensional Lie algebras

Let X¹,…, X^k be real analytic vector fields on an n-dimensional manifold M, k < n, which are linearly independent at a point p ε M and which, together with their Lie products at p, span the tangent space TM_p. Then X¹,…, X^k form a local basis for a real analytic k-dimensional distribution x→D^k(x)=span{X¹(x),…,X^k(x)}. We study the question of when D^k admits a basis which generates a nilpotent, or solvable (or finite dimensional) Lie algebra. If this is the case the study of affine control systems, or partial differential operators, described via X¹,…, X^k can often be greatly simplified.     

Mutually Unbiased Bases and the Complementarity Polytope

A complete set of N + 1 mutually unbiased bases (MUBs) forms a convex polytope in the N² − 1 dimensional space of N × N Hermitian matrices of unit trace. As a geometrical object such a polytope exists for all values of N, while it is unknown whether it can be made to lie within the body of density matrices unless N = p^k, where p is prime. We investigate the polytope in order to see if some values of N are geometrically singled out. One such feature is found: It is possible to select N² facets in such a way that their centers form a regular simplex if and only if there exists an affine plane of order N. Affine planes of order N are known to exist if N = p^k; perhaps they do not exist otherwise. However, the link to the existence of MUBs — if any — remains to be found.     

Feedback equivalence of constant linear systems

Two constant linear systems are said to be feedback equivalent if one can be transformed into the other via an element of the “feedback group”, which acts by state space feedback and by change of basis in the state and input spaces. Let C_n,m be the space of n-dimensional completely reachable systems with m-dimensional input (pairs of matrices, n × n and n × m). The action of the feedback group partitions the space C_n,m into finitely many orbits (equivalence classes), and the closure of each orbit is a union of orbits. If one views orbit closure as ‘deformation’, then orbit closure may be considered in terms of perturbations or system failure. In this paper we determine: (1) a classification of the orbits, and (2) the orbits contained in the closure of a given orbit. Both of these problems have been solved previously (see [1,4,6,3]); here we present simple proofs and point out a connection between this problem and the analogous problem for nilpotent matrices.     

On singularities of flat affine systems with n states and n−1 controls

We study the set of intrinsic singularities of flat affine systems with n?1 controls and n states using the notion of Lie‐Bäcklund atlas, previously introduced by the authors. For this purpose, we prove two easily computable sufficient conditions to construct flat outputs as a set of independent first integrals of distributions of vector fields: the first one in a generic case, namely, in a neighborhood of a point where the n?1 control vector fields are independent and the second one at a degenerate point where p?1 control vector fields are dependent of the n?p others, with p>1. After introducing the Γ‐accessibility rank condition, we show that the set of intrinsic singularities includes the set of points where the system does not satisfy this rank condition and is included in the set where a distribution of vector fields introduced in the generic case is singular. We conclude this analysis by three examples of apparent singularities of flat systems in generic and nongeneric degenerate cases.     

Variable structure exponential stabilization of chained systems based on the extended nonholonomic integrator

In this paper, a new variable structure control strategy for exponentially stabilizing chained systems is presented based on the extended nonholonomic integrator model, the discontinuous coordinate transformation and the “reaching law method” in variable structure control design. The proposed approach converts the stabilization problem of an n-dimensional chained system into the pole-assignment problem of an (n−3)-dimensional linear time-invariant system and consequently simplifies the stabilization controller design of nonholonomic chained systems.     

A note on reduced order stabilizing output feedback controllers

In this paper we show that if a certain class of nonlinear systems is globally asymptotically stabilizable through an n-dimensional output feedback controller then it can be always stabilized through an (n − p)-dimensional output feedback controller, where p is the number of outputs and n is the dimension of the state space. This result gives an alternative construction of reduced order controllers for linear systems, and recovers in a more general framework the concept of dirty derivative, used in the framework of rigid and elastic joint robots, and gives an alternative procedure for designing reduced-order controllers for nonlinear systems considered in the existing literature.     

One-step t-fault diagnosis for hypermesh optical interconnection multiprocessor systems

To maintain high reliability and availability, system-level diagnosis should be considered for the multiprocessor systems. The self-diagnosis problem of hypermesh, emerging potential optical interconnection networks for multiprocessor systems, is solved in this paper. We derive that the precise one-step diagnosability of kⁿ-hypermesh is n(k − 1). Based on the principle of cycle decomposition, a one-step t-fault diagnosis algorithm for kⁿ-hypermesh which runs in O(kⁿn(k − 1)) time also is described.     

On the stability of the information state system

The purpose of this paper is to present some preliminary results on the stability of the information state system. The information state system underlies the (infinite dimensional) dynamics of an H_∞ controller for a nonlinear system. Thus it is important to understand its stability and the structure of its equilibrium points. We analyse the important case corresponding to the mixed sensitivity problem. We prove the existence of an equilibrium information state, convergence under very general conditions to such an equilibrium state p_e and uniqueness of this state (up to an irrelevant constant). In this case the equilibrium p_e is usually singular in the sense that it takes on the value − ∞ except on a low dimensional subset of its domain.This meshes with the article [9] which analysed the effect of using p_e to initialize the information state controller and gave explicit formulas which in many cases produce a dramatic reduction in the amount of computation required to implement the controller. What this article suggests is that indeed p_e is the only equilibrium initialization possible.     

Differential flatness of two one-forms in arbitrary number of variables

Given a differentially flat system of ODEs, flat outputs that depend only on original variables but not on their derivatives are called zero-flat outputs and systems possessing such outputs are called zero-flat. In this paper we present a theory of zero-flatness for a system of two one-forms in arbitrary number of variables (t,x¹,…,x^N). Our approach splits the task of finding zero-flat outputs into two parts. First part involves solving for distributions that satisfy a set of algebraic conditions. The second part involves finding an integrable distribution from the solution set of the first part. Typically this part involves solving PDEs. Our results are also applicable in determining if a control affine system in n states and n−2 controls has flat outputs that depend only on states. We illustrate our method by examples.     

Optimal Algorithms for the Coverability, the Subword, the Containment, and the Equivalence Problems for Commutative Semigroups

In this paper, we present decision procedures for the coverability, the subword, the containment, and the equivalence problems for commutative semigroups. These procedures require at most space 2^c·n, where n is the size of the problem instance, and c is some problem independent constant. Furthermore, we show that the exponential space hardness of the above problems follows from the work of Mayr and Meyer. Thus, the presented algorithms are space optimal. Our results close the gap between the 2^{c′·n·log n} space upper bound, shown by Rackoff for the coverability problem and shown by Huynh for the containment and the equivalence problems, and the exponential space lower bound resulting from the corresponding bound for the uniform word problem established by Mayr and Meyer.     

A further result on the oscillation of delay difference equations

In this paper, we are concerned with the delay difference equations of the form

(*)

y_n+1 − y_n + p_ny_n−k = 0, N = 0, 1, 2, …,

(*)where p_n ≥ 0 and k is a positive integer. We prove by using a new technique that

guarantees that all solutions of equation (*) oscillate, which improves many previous well-known results. In particular, our theorems also fit the case where Σⁿ⁻¹_i=n−kp_i ≤ k^k+1/(k + 1)^k+1. In addition, we present a nonoscillation sufficient condition for equation (*).     

An efficient alignment algorithm for masked sequences

We consider the alignment problem where sequences may have masked regions. The bases in masked regions are either unspecified or unknown, and they will be denoted by N. We present an efficient algorithm that finds an optimal local alignment by skipping such masked regions of sequences. Our algorithm works for both the affine gap penalty model and the linear gap penalty model. The time complexity of our algorithm is O((n−T)(m−S)+vm+wn) time, where n and m are the lengths of given sequences A and B, T and S are the numbers of base N in A and B, and v and w are the numbers of masked regions in A and B, respectively.     

How to Recognize Zero

An elementary point is a point in complexnspace, which is an isolated, nonsingular solution ofnequations innvariables, each equation being either of the formp = 0, wherepis a polynomial in [x₁,…,x_n], or of the formx_j − e^x_i = 0. An elementary number is the polynomial image of an elementary point. In this article a semi algorithm is given to decide whether or not a given elementary number is zero. It is proved that this semi algorithm is an algorithm, i.e. that it always terminates, unless it is given a problem containing a counterexample to Schanuel’s conjecture.     

Further oscillation criteria for delay partial difference equations

This paper is concerned with the partial difference equation A_m+1,n+A_m,n+1−A_m,n+p_m,nA_m−k,n−l=0,m,n=0,1,2,…,, where k and l are two positive integers, {p_m,n} is a real double sequence. Some new oscillation criteria for this equation are obtained.     

Algorithms for path medi-centers of a tree

We consider the problem of finding an optimal location of a path on a tree, using combinations of minisum and minimax criteria (which are respectively maximal distance and average distance from the path to customers situated at the vertices). The case of linear combination of the two criteria and the case where one criterion is optimized subject to a restriction on the value of the other are considered and linear-time algorithms for these problems are presented. It is proved that the representation of the set of Pareto-optimal paths in the space of criteria has cardinality not greater than n−1, where n is the number of vertices of the tree, and can be obtained in O(n log n) time, although the number of Pareto-optimal paths can be O(n²)     

A classification of generic families of control-affine systems and their bifurcations

We study control-affine systems with n − 1 inputs evolving on an n-dimensional manifold for which the distribution spanned by the control vector fields is involutive and of constant rank (equivalently, they may be considered as 1-dimensional systems with n − 1 inputs entering nonlinearly). We provide a complete classification of such generic systems and their one-parameter families. We show that a generic family for n > 2 is equivalent (with respect to feedback or orbital feedback transformations) to one of nine canonical forms which differ from those for n = 2 by quadratic terms only. We also describe all generic bifurcations of 1-parameter families of systems of the above form.     

Controlling the data space of tree structured computations

We study the problem of scheduling a parallel computation so as to minimize the maximum number of data items extant at any point in the execution. Computations are expressed as directed graphs, where nodes represent primitive operations and arcs represent data dependences. The result of an operation is extant after the operation executes and until all immediate successors have begun execution. Our goal is to schedule computations so as to minimize both the maximum space required for extant data and the overall completion time.The classical problem of multiprocessor scheduling with precedence constraints is a special case of our problem, obtained by disregarding the data-space constraint. This special case is NP-complete for general graphs; a time-optimal multiprocessor scheduling algorithm is known only for the class of arbitrary trees. For this same class of arbitrary trees we present a multiprocesssor scheduling algorithm where the completion time is optimal within a constant factor, while the data-space size exceeds the optimal by a factor not greater than the number of processors.For an arbitrary n-node precedence tree T of in-degree Δ, we present:

(1)an algorithm for evaluating the lower bound on the size of data space required for executing T, regardless of the completion time or number of processors;

(2)a proof that the lower bound of Part 1 may be as large as (Δ−1)lgn but not larger;

(3)a single-processor schedule that executes T in time that equals the optimal, while creating the data space of size equal to the lower bound of Part 1;

(4)an ω-processor schedule that executes T in time not exceeding three times the optimal, while creating the data space of size that exceeds the lower bound of Part 1 by a factor not greater than ω.

(5)a proof that for every number of processors ω and for every 0<ε1, there exist infinitely many trees such that every ω-processor schedule that executes any of these trees in time not exceeding (2−ε) times the optimal requires a token space as large as that created by the schedule of Part 4, while the schedule of Part 4 executes every such tree in optimal time.

The family of complete binary trees provides an example where our schedule achieves an exponential improvement in the size of the data space, compared to that of the classical time-optimal schedule.