Decoupling of square singular systems via proportional statefeedback

Necessary and sufficient conditions for the decoupling of a solvable square singular system Ex˙(t)=Ax(t)+Bu(t ) with output y(t)=Dx(t), through an admissible control law of the form u(t)=Kx(t)+Hr(t) where H is a square nonsingular matrix. It has been shown that for a given singular system that satisfies these conditions, a propagational state feedback exists for which the system's transfer function is a diagonal, nonsingular, and proper rational matrix. The proofs of the main results are constructive and provide a procedure for computing an appropriate proportional state feedback     

Control of interconnected nonlinear dynamical systems: the platoonproblem

The problem to be solved involves a highway automation project. The overall system consists of N vehicles (the platoon). Each vehicle is driven by the same input u and the state of the kth vehicle affects the dynamics of the (k+1)th vehicle. Furthermore, the dynamics of each vehicle is affected by its (local) state-feedback controller. Under very general conditions, it is shown that for sufficiently slowly varying inputs, decentralized controllers can be designed so that the platoon maintains its cohesion     

Two-dimensional convolution on a pyramid computer

An algorithm for convolving a k×k window of weighting coefficients with an n×n image matrix on a pyramid computer of O(n²) processors in time O(logn+k²), excluding the time to load the image matrix, is presented. If k=Ω (√log n), which is typical in practice, the algorithm has a processor-time product O(n ² k²) which is optimal with respect to the usual sequential algorithm. A feature of the algorithm is that the mechanism for controlling the transmission and distribution of data in each processor is finite state, independent of the values of n and k. Thus, for convolving two {0, 1}-valued matrices using Boolean operations rather than the typical sum and product operations, the processors of the pyramid computer are finite-state     

The stability of a family of polynomials can be deduced from afinite number 0(k3) of frequency checks

Let φ(s,a)=φ₀(s,a)+ a₁φ₁(s)+a₂ φ₂(s)+ . . .+a_kφ _k(s)=φ₀(s)-q(s, a) be a family of real polynomials in s, with coefficients that depend linearly on parameters a_i which are confined in a k-dimensional hypercube Ω_a . Let φ₀(s) be stable of degree n and the φ_i(s) polynomials (i⩾1) of degree less than n. A Nyquist argument shows that the family φ(s) is stable if and only if the complex number φ₀(jω) lies outside the set of complex points -q(jω,Ω_a) for every real ω. In a previous paper (Automat. Contr. Conf., Atlanta, GA, 1988) the authors have shown that -q(jω,Ω_a ), the so-called `-q locus', is a 2k convex parpolygon. The regularity of this figure simplifies the stability test. In the present paper they again exploit this shape and show that to test for stability only a finite number of frequency checks need to be done; this number is polynomial in k, 0(k³), and these critical frequencies correspond to the real nonnegative roots of some polynomials     

On the gap between the structural controllability of time-varyingand time-invariant systems

Structural controllability of time-invariant and time-varying systems when the input control sequences have a restricted length k is compared. The dimensions of controllable space coincide in the following three special cases: the input sequences have length k=2; the input sequences have k=n, where n is the size of the system (i.e., the ultimate controllability is the same in both cases); and for every length of input sequences provided that the system has a single input only. It is proved that there may appear a gap for every input length k such that 2< k⩽n/2. The case when n/2<k<n is left open     

Network communication in edge-colored graphs: gossiping

A mechanism for scheduling communications in a network in which individuals exchange information periodically according to a fixed schedule is presented. A proper k edge-coloring of the network is considered to be a schedule of allowed communications such that an edge of color i can be used only at times i modulo k. Within this communication scheduling mechanism, the information exchange problem known as gossiping is considered. It is proved that there is a proper k edge-coloring such that gossip can be completed in a path of n edges in a certain time for n⩾k⩾1. Gossip can not be completed in such a path any earlier under any proper k edge-coloring. In any tree of bounded degree Δ and diameter d, gossip can be completed under a proper Δ edge-coloring in time (Δ-1)d +1. In a k edge-colored cycle of n vertices, other time requirements of gossip are determined     

A sufficient condition for simultaneous stabilization

The condition under which it is possible to find a single controller that stabilizes k single-input single-output linear time-invariant systems p_i(s) (i=1,. . .,k) is investigated. The concept of avoidance in the complex plane is introduced and used to derive a sufficient condition for k systems to be simultaneously stabilizable. A method for constructing a simultaneous stabilizing controller is also provided and is illustrated by an example     

A probabilistic limit on the virtual size of replicated disksystems

Recently, there has been considerable interest in parallel disk drive systems, in which full or partial replication of the stored data is used for both fault tolerance and enhanced performance. The performance-enhancement derives both from the ability to do parallel reads, and from the reduction of seek time which results from being able to assign a read to whichever drive will produce the shortest seek. Although earlier work implied that for a k-drive system, mean seek distance for read converges to 0 as k→α, a refined analysis is presented which shows that this limit is actually nonzero. It is further shown that the system behaves probabilistically as if k were small, no matter how large the physical value of k is     

Order-determination theorems and system identification

Theorems for order-determination without a priori knowledge of upper bounds on the order in MIMO dynamic systems are developed. Also, deterministic procedures are introduced to determine orders and estimate parameters simultaneously by recursively computing the order-determining quantity S_n(a,b,k), which plays a crucial role in order-determination procedures, and the least-squares estimate &thetas;_n(a,b) of &thetas;(p,q), with p and q denoting the true orders     

Parallel median splitting and k-splitting with applicationto merging and sorting

Multiple-instruction multiple-data (MIMD) algorithms that use multiple processors to do median splitting, k-splitting and parallel splitting into t equal sections are presented. Both concurrent read, exclusive write (CREW) and exclusive read, exclusive write (EREW) versions of the algorithms are given. It is shown that a k-splitting problem can be easily converted into a median-splitting problem. Methods for finding multiple split points quickly and application of k-splitting to merging and sorting are discussed     

On time mapping of uniform dependence algorithms into lowerdimensional processor arrays

Most existing methods of mapping algorithms into processor arrays are restricted to the case where n-dimensional algorithms, or algorithms with n nested loops, are mapped into (n-1)-dimensional arrays. However, in practice, it is interesting to map n-dimensional algorithms into (k-1)-dimensional arrays where k<n. A computational conflict occurs if two or more computations of an algorithm are mapped into the same execution time. Based on the Hermite normal form of the mapping matrix, necessary and sufficient conditions are derived to identify mapping without computational conflicts. These conditions are used to find time mappings of n-dimensional algorithms into (k-1)-dimensional arrays, k<n , without computational conflicts. For some applications, the mapping is time-optimal     

Out-of-roundness problem revisited

The properties and computation of the minimum radial separation (MRS) standard for out-of-roundness are discussed. Another standard out-of-roundness measurement called the minimum area difference (MAD) center is introduced. Although the two centers have different characteristics, the approach to finding both centers shares many commonalities. An O(n log n+k) time algorithm which is used to compute the MRS center is presented. It also computes the MAD center of a simple polygon G, where n is the number of vertices of G, and k is the number of intersection points of the medial axis and the farthest-neighbor Voronoi diagram of G. The relationship between MRS and MAD is discussed     

An efficient algorithm for mutual exclusion using queue migrationin computer networks

A nonsymmetric deadlock-free mutual exclusion algorithm for computer networks is presented. The algorithm requires O(m ) messages to synchronize m modes in a lightly loaded system, and the performance approaches a constant k dependent on m as the workload increases. In a medium to heavily loaded system, it outperforms other proposed algorithms and its performance is independent of network topology     

Optimal resilient distributed algorithms for ring election

The problem of electing a leader in a dynamic ring in which processors are permitted to fail and recover during election is discussed. It is shown that &thetas;(n log n+k_r) messages, counting only messages sent by functional processors, are necessary and sufficient for dynamic ring election, where k_r is the number of processor recoveries experienced     

An approach for pole assignment in singular systems

Pole assignment in a singular system Edx/dt=Ax+Bu is discussed. It is shown that the problem of assigning the roots of det(sE-(A +BF)) by applying a proportional feedback u=Fx+r in a given singular system is equivalent to the problem of pole assignment of an appropriate regular system. An immediate application of this result is that procedures and computational algorithms that were originally developed for assigning eigenvalues in regular systems become useful tools for pole assignment in singular systems. The approach provides a useful tool for the combined problem of eliminating impulsive behavior and stabilizing a singular system     

An efficient digital search algorithm by using a double-arraystructure

An efficient digital search algorithm that is based on an internal array structure called a double array, which combines the fast access of a matrix form with the compactness of a list form, is presented. Each arc of a digital search tree, called a DS-tree, can be computed from the double array in 0(1) time; that is to say, the worst-case time complexity for retrieving a key becomes 0(k) for the length k of that key. The double array is modified to make the size compact while maintaining fast access, and algorithms for retrieval, insertion, and deletion are presented. If the size of the double array is n+cm, where n is the number of nodes of the DS-tree, m is the number of input symbols, and c is a constant particular to each double array, then it is theoretically proved that the worst-case times of deletion and insertion are proportional to cm and cm², respectively, and are independent of n. Experimental results of building the double array incrementally for various sets of keys show that c has an extremely small value, ranging from 0.17 to 1.13     

A top-down processor allocation scheme for hypercube computers

An efficient processor allocation policy is presented for hypercube computers. The allocation policy is called free list since it maintains a list of free subcubes available in the system. An incoming request of dimension k (2^k nodes) is allocated by finding a free subcube of dimension k or by decomposing an available subcube of dimension greater than k. This free list policy uses a top-down allocation rule in contrast to the bottom-up approach used by the previous bit-map allocation algorithms. This allocation scheme is compared to the buddy, gray code (GC), and modified buddy allocation policies reported for the hypercubes. It is shown that the free list policy is optimal in a static environment, as are the other policies, and it also gives better subcube recognition ability compared to the previous schemes in a dynamic environment. The performance of this policy, in terms of parameters such as average delay, system utilization, and time complexity, is compared to the other schemes to demonstrate its effectiveness. The extension of the algorithm for parallel implementation, noncubic allocation, and inclusion/exclusion allocation is also given     

Least-squares output estimation with multirate sampling

A least-squares output estimation algorithm is presented for applications where the output is sampled at a slower rate than the input. Given the sequence {u(kT), y(kJT )k=1,2,...}, where J is a positive integer and T is the basic sampling period, it is proven that the output estimation error converges to zero for instants at or between the output measurement instants. The assumptions required are essentially the same as for the case with equal sampling rates, i.e., for J=1. Simulation examples show excellent output estimation, based on measured y(kJT) with J=8     

Stabilization by reduced-order controllers

A recent result by A. Linnemann (Syst. Contr. Lett., vol.11, p.27-32, 1988) gives conditions under which a continuous-time single-loop plant of order n can be stabilized by a reduced-order controller. Specifically, if the Euclidean algorithm is applied to the numerator and denominator polynomials of the transfer function and one of the remainders is a kth-order Hurwitz polynomial, then a stabilizing controller of order n-k-1 exists. The author provides an alternative proof of this result     

The minimal dimension of stable faces required to guaranteestability of a matrix polytope

Considers the problem of determining whether each point in a polytope n×n matrices is stable. The approach is to check stability of certain faces of the polytope. For n⩾3, the authors show that stability of each point in every (2n-4)-dimensional face guarantees stability of the entire polytope. Furthermore, they prove that, for any k⩽n², there exists a k-dimensional polytope containing a strictly unstable point and such that all its subpolytopes of dimension min {k-1,2n-5} are stable